TechCodeview

Paieškos algoritmai yra viena iš svarbiausių dirbtinio intelekto sričių. Šioje temoje bus paaiškinta viskas apie AI paieškos algoritmus.

Problemų sprendimo agentai:

Dirbtiniame intelekte paieškos metodai yra universalūs problemų sprendimo metodai. Racionalūs agentai arba Problemų sprendimo agentai AI dažniausiai naudojo šias paieškos strategijas ar algoritmus, kad išspręstų konkrečią problemą ir gautų geriausią rezultatą. Problemas sprendžiantys agentai yra agentai, pagrįsti tikslu ir naudoja atominį vaizdavimą. Šioje temoje išmoksime įvairių problemų sprendimo paieškos algoritmų.

Paieškos algoritmų terminai:

Paieška:Paieška yra žingsnis po žingsnio procedūra, skirta išspręsti paieškos problemą tam tikroje paieškos erdvėje. Paieškos problemą gali sukelti trys pagrindiniai veiksniai:
Ieškoti erdvėje:Paieškos erdvė yra galimų sprendimų, kuriuos gali turėti sistema, rinkinys.Pradžios būsena:Tai būsena, nuo kurios prasideda agentas paieška .Įvarčio testas:Tai funkcija, kuri stebi esamą būseną ir grąžina, ar tikslo būsena pasiekta, ar ne.
Paieškos medis:Paieškos problemos medžio vaizdavimas vadinamas Paieškos medžiu. Paieškos medžio šaknis yra šakninis mazgas, atitinkantis pradinę būseną.Veiksmai:Jis suteikia agentui visų galimų veiksmų aprašymą.Perėjimo modelis:Kiekvieno veiksmo aprašymas gali būti pateiktas kaip pereinamasis modelis.Kelio kaina:Tai funkcija, kuri kiekvienam keliui priskiria skaitinę kainą.Sprendimas:Tai veiksmų seka, kuri veda nuo pradžios mazgo iki tikslo mazgo.Optimalus sprendimas:Jei sprendimas turi mažiausią kainą iš visų sprendimų.

Paieškos algoritmų savybės:

Toliau pateikiamos keturios pagrindinės paieškos algoritmų savybės, leidžiančios palyginti šių algoritmų efektyvumą:

žiemos miego tarmė

Išsamumas: Paieškos algoritmas laikomas baigtu, jei jis garantuoja, kad bus pateiktas sprendimas, jei yra bent koks nors sprendimas bet kuriai atsitiktinei įvesties atveju.

Optimalumas: Jei algoritmui rastas sprendimas garantuotai yra geriausias sprendimas (mažiausia kelio kaina) tarp visų kitų sprendimų, tai toks sprendimas laikomas optimaliu.

Laiko sudėtingumas: Laiko sudėtingumas yra laiko matas, per kurį algoritmas turi atlikti savo užduotį.

Erdvės sudėtingumas: Tai yra maksimali saugyklos vieta, reikalinga bet kuriuo paieškos momentu, atsižvelgiant į problemos sudėtingumą.

Paieškos algoritmų tipai

Remiantis paieškos problemomis, paieškos algoritmus galime suskirstyti į neinformuotos (aklosios paieškos) ir informuotos paieškos (heuristinės paieškos) algoritmus.

Neinformuota / akla paieška:

Neinformuotoje paieškoje nėra jokių srities žinių, tokių kaip artumas, tikslo vieta. Jis veikia žiauriai, nes apima tik informaciją apie tai, kaip pereiti medį ir kaip nustatyti lapų ir tikslo mazgus. Neinformuota paieška taiko būdą, kuriuo paieškos medyje ieškoma be jokios informacijos apie paieškos erdvę, pvz., pradinės būsenos operatorių ir tikslo testo, todėl ji dar vadinama akla paieška. Ji tiria kiekvieną medžio mazgą, kol pasiekia tikslo mazgą.

Jį galima suskirstyti į penkis pagrindinius tipus:

• Paieška pirmoje vietoje
• Vienoda išlaidų paieška
• Paieška pagal gylį
• Iteratyvi gilinanti paieška pirmiausia
• Dvikryptė paieška

Informuota paieška

Informuotos paieškos algoritmai naudoja domeno žinias. Informuotos paieškos metu galima rasti informacijos apie problemą, kuri gali padėti ieškoti. Informuotos paieškos strategijos gali rasti sprendimą efektyviau nei neinformuotos paieškos strategija. Informuota paieška taip pat vadinama euristine paieška.

Euristika yra būdas, kuris ne visada gali būti garantuotas geriausiems sprendimams, bet garantuotas, kad geras sprendimas bus rastas per protingą laiką.

java rūšiuoja sąrašą

Informuota paieška gali išspręsti daug sudėtingų problemų, kurių negalima išspręsti kitu būdu.

Informuotos paieškos algoritmų pavyzdys yra keliaujančio pardavėjo problema.

1. Godžios paieškos
2. A* Paieška