TechCodeview

Algoritmi pretraživanja jedno su od najvažnijih područja umjetne inteligencije. Ova će tema objasniti sve o algoritmima pretraživanja u AI.

Agenti za rješavanje problema:

U umjetnoj inteligenciji, tehnike pretraživanja univerzalne su metode rješavanja problema. Racionalni agenti ili Agenti za rješavanje problema u AI uglavnom koristi ove strategije pretraživanja ili algoritme za rješavanje određenog problema i pružanje najboljih rezultata. Agenti za rješavanje problema su agenti koji se temelje na cilju i koriste atomsku reprezentaciju. U ovoj temi naučit ćemo različite algoritme pretraživanja za rješavanje problema.

Terminologija algoritma pretraživanja:

Traži:Pretraživanje je postupak korak po korak za rješavanje problema pretraživanja u zadanom prostoru pretraživanja. Problem pretraživanja može imati tri glavna čimbenika:
Prostor za pretraživanje:Prostor pretraživanja predstavlja skup mogućih rješenja koje sustav može imati.Početno stanje:To je stanje u kojem agent počinje Potraga .Test cilja:To je funkcija koja promatra trenutno stanje i vraća je li ciljno stanje postignuto ili ne.
Stablo pretraživanja:Prikaz stabla problema pretraživanja naziva se stablo pretraživanja. Korijen stabla pretraživanja je korijenski čvor koji odgovara početnom stanju.Radnje:Daje opis svih dostupnih radnji agentu.Prijelazni model:Opis onoga što čini svaka radnja može se predstaviti kao prijelazni model.Cijena puta:To je funkcija koja svakoj stazi dodjeljuje numerički trošak.Riješenje:To je akcijski niz koji vodi od početnog čvora do ciljnog čvora.Optimalno rješenje:Ako rješenje ima najnižu cijenu među svim rješenjima.

Svojstva algoritama pretraživanja:

Slijede četiri bitna svojstva algoritama pretraživanja za usporedbu učinkovitosti ovih algoritama:

Potpunost: Za algoritam pretraživanja kaže se da je potpun ako jamči da će vratiti rješenje ako postoji barem bilo koje rješenje za bilo koji slučajni unos.

Optimalnost: Ako je pronađeno rješenje za algoritam zajamčeno najbolje rješenje (najniža cijena puta) među svim ostalim rješenjima, tada se takvo rješenje za smatra optimalnim rješenjem.

Vremenska složenost: Vremenska složenost je mjera vremena potrebnog algoritmu da izvrši svoj zadatak.

Složenost prostora: To je maksimalni prostor za pohranu potreban u bilo kojoj točki tijekom pretraživanja, kao i složenost problema.

Vrste algoritama pretraživanja

Na temelju problema pretraživanja možemo klasificirati algoritme pretraživanja u algoritme neinformiranog (Slijepo pretraživanje) i informiranog pretraživanja (Heurističko pretraživanje).

Neinformirana/slijepa pretraga:

Neinformirano pretraživanje ne sadrži nikakvo znanje o domeni kao što je blizina, lokacija cilja. Djeluje na grubi način jer uključuje samo informacije o tome kako prijeći stablo i kako identificirati listove i ciljne čvorove. Neinformirano pretraživanje primjenjuje način na koji se stablo pretraživanja pretražuje bez ikakvih informacija o prostoru pretraživanja kao što su operatori početnog stanja i test za cilj, pa se naziva i slijepo pretraživanje. Ispituje svaki čvor stabla dok ne postigne ciljni čvor.

Može se podijeliti u pet glavnih vrsta:

• Traži u širinu
• Jednoobrazna pretraga troškova
• Pretraživanje najprije u dubinu
• Iterativno produbljivanje prvo u dubinu
• Dvosmjerno pretraživanje

Informirana pretraga

Informirani algoritmi pretraživanja koriste znanje domene. U informiranoj pretrazi dostupne su informacije o problemu koje mogu voditi pretragu. Informirane strategije pretraživanja mogu učinkovitije pronaći rješenje od neinformirane strategije pretraživanja. Informirano pretraživanje naziva se i heurističko pretraživanje.

Heuristika je način za koji nije uvijek zajamčeno najbolje rješenje, ali je zajamčeno pronalaženje dobrog rješenja u razumnom vremenu.

Informirano pretraživanje može riješiti mnogo složeniji problem koji se ne može riješiti na drugi način.

Primjer informiranih algoritama pretraživanja je problem trgovačkog putnika.

1. Pohlepna pretraga
2. A* Traži