TechCodeview

Iskalni algoritmi so eno najpomembnejših področij umetne inteligence. Ta tema bo razložila vse o iskalnih algoritmih v AI.

Agenti za reševanje težav:

V umetni inteligenci so tehnike iskanja univerzalne metode za reševanje problemov. Racionalni agenti oz Agenti za reševanje problemov v umetni inteligenci večinoma uporablja te iskalne strategije ali algoritme za rešitev določenega problema in zagotavljanje najboljšega rezultata. Agenti za reševanje problemov so agenti, ki temeljijo na ciljih in uporabljajo atomsko predstavitev. V tej temi se bomo naučili različnih iskalnih algoritmov za reševanje problemov.

Terminologija iskalnega algoritma:

Iskanje:Iskanje je korak za korakom postopek za reševanje iskalnega problema v danem iskalnem prostoru. Težavo pri iskanju lahko povzročijo trije glavni dejavniki:
Iskanje prostora:Iskalni prostor predstavlja nabor možnih rešitev, ki jih sistem lahko ima.Začetno stanje:To je stanje, od koder se agent začne iskanje .Test cilja:Je funkcija, ki opazuje trenutno stanje in vrne, ali je ciljno stanje doseženo ali ne.
Iskalno drevo:Drevesna predstavitev iskalnega problema se imenuje Iskalno drevo. Koren iskalnega drevesa je korensko vozlišče, ki ustreza začetnemu stanju.Dejanja:Agentu daje opis vseh razpoložljivih dejanj.Prehodni model:Opis tega, kaj naredi posamezno dejanje, je mogoče predstaviti kot prehodni model.Cena poti:To je funkcija, ki vsaki poti dodeli številčno ceno.rešitev:To je akcijsko zaporedje, ki vodi od začetnega do ciljnega vozlišča.Optimalna rešitev:Če ima rešitev najnižjo ceno med vsemi rešitvami.

Lastnosti iskalnih algoritmov:

Sledijo štiri bistvene lastnosti iskalnih algoritmov za primerjavo učinkovitosti teh algoritmov:

Popolnost: Za iskalni algoritem pravimo, da je popoln, če zagotavlja, da bo vrnil rešitev, če obstaja vsaj kakšna rešitev za kateri koli naključni vnos.

Optimalnost: Če je najdena rešitev za algoritem zagotovljena kot najboljša rešitev (najnižja cena poti) med vsemi drugimi rešitvami, potem je taka rešitev za optimalna rešitev.

Časovna zapletenost: Časovna kompleksnost je merilo časa, v katerem algoritem opravi svojo nalogo.

Kompleksnost prostora: To je največji prostor za shranjevanje, potreben na kateri koli točki med iskanjem, kot je zapletenost problema.

Vrste iskalnih algoritmov

Glede na probleme iskanja lahko iskalne algoritme razvrstimo v algoritme neinformiranega (Blind search) iskanja in algoritme informiranega iskanja (Hevristično iskanje).

Neobveščeno/slepo iskanje:

Neinformirano iskanje ne vsebuje znanja o domeni, kot je bližina, lokacija cilja. Deluje na brutalni način, saj vključuje le informacije o tem, kako prečkati drevo in kako identificirati listna in ciljna vozlišča. Neobveščeno iskanje uporablja način, na katerega se iskalno drevo išče brez kakršnih koli informacij o iskalnem prostoru, kot so operaterji začetnega stanja in test za cilj, zato se imenuje tudi slepo iskanje. Pregleduje vsako vozlišče drevesa, dokler ne doseže ciljnega vozlišča.

Razdelimo ga lahko na pet glavnih vrst:

• Iskanje v širino
• Enotno iskanje stroškov
• Iskanje najprej v globino
• Iterativno poglabljanje v globino
• Dvosmerno iskanje

Informirano iskanje

Algoritmi informiranega iskanja uporabljajo znanje domene. Pri informiranem iskanju so na voljo informacije o problemu, ki lahko vodijo iskanje. Informirane iskalne strategije lahko najdejo rešitev učinkoviteje kot neinformirane iskalne strategije. Informirano iskanje se imenuje tudi hevristično iskanje.

Hevristika je način, ki morda ni vedno zajamčen za najboljše rešitve, vendar zajamčeno, da bo našel dobro rešitev v razumnem času.

Informirano iskanje lahko reši veliko kompleksnih problemov, ki jih ni mogoče rešiti drugače.

Primer informiranega iskalnega algoritma je problem trgovskega potnika.

1. Pohlepno iskanje
2. A* Iskanje