Neinformuota paieška yra bendrosios paskirties paieškos algoritmų klasė, kuri veikia žiauriai jėga. Neinformuoti paieškos algoritmai neturi papildomos informacijos apie būseną ar paieškos erdvę, išskyrus tai, kaip pereiti medį, todėl ji dar vadinama akla paieška.
Toliau pateikiami įvairūs neinformuotų paieškos algoritmų tipai:
1. Paieška pagal plotį:
- Paieška pagal plotį yra labiausiai paplitusi paieškos strategija, skirta pereiti per medį ar diagramą. Šis algoritmas medyje arba grafike ieško plataus masto, todėl jis vadinamas paieška pagal plotį.
- BFS algoritmas pradeda paiešką nuo šakninio medžio mazgo ir išplečia visus tolesnius mazgus dabartiniame lygyje, prieš pereidamas prie kito lygio mazgų.
- Paieškos pagal plotį algoritmas yra bendrojo grafiko paieškos algoritmo pavyzdys.
- Pirmoji paieška, įgyvendinta naudojant FIFO eilės duomenų struktūrą.
Privalumai:
- BFS pateiks sprendimą, jei toks yra.
- Jei yra daugiau nei vienas problemos sprendimas, BFS pateiks minimalų sprendimą, kuriam reikia mažiausiai veiksmų.
Trūkumai:
- Tam reikia daug atminties, nes kiekvienas medžio lygis turi būti išsaugotas atmintyje, kad būtų išplėstas kitas lygis.
- BFS reikia daug laiko, jei sprendimas yra toli nuo šakninio mazgo.
Pavyzdys:
Žemiau esančioje medžio struktūroje parodėme medžio perėjimą naudojant BFS algoritmą nuo šakninio mazgo S iki tikslo mazgo K. BFS paieškos algoritmas eina sluoksniais, todėl jis seks taškine rodykle pavaizduotu keliu ir nueitas kelias bus:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
Laiko sudėtingumas: BFS algoritmo laiko sudėtingumą galima gauti pagal BFS perkeliamų mazgų skaičių iki sekliausio mazgo. Kur d = sekliausio tirpalo gylis, o b yra mazgas kiekvienoje būsenoje.
T (b) = 1+b2+b3+.......+ bd= O (bd)
Erdvės sudėtingumas: BFS algoritmo erdvinis sudėtingumas nustatomas pagal sienos atminties dydį, kuris yra O (bd).
Išsamumas: BFS yra baigtas, o tai reiškia, kad jei sekliausias tikslo mazgas yra baigtiniame gylyje, BFS ras sprendimą.
Optimalumas: BFS yra optimalus, jei kelio kaina yra nemažėjanti mazgo gylio funkcija.
2. Paieška pagal gylį
- Paieška pagal gylį yra rekursinis algoritmas, skirtas medžio arba grafiko duomenų struktūrai pereiti.
- Ji vadinama paieška pagal gylį, nes ji prasideda nuo šaknies mazgo ir seka kiekvieną kelią iki didžiausio gylio mazgo, prieš pereinant prie kito kelio.
- DFS įgyvendinimui naudoja kamino duomenų struktūrą.
- DFS algoritmo procesas yra panašus į BFS algoritmą.
Pastaba: Backtracking yra algoritmo metodas, leidžiantis rasti visus galimus sprendimus naudojant rekursiją.
Privalumas:
- DFS reikia labai mažiau atminties, nes jai tereikia saugoti mazgų krūvą kelyje nuo šakninio mazgo iki dabartinio mazgo.
- Tikslo mazgo pasiekimas trunka mažiau laiko nei BFS algoritmas (jei jis eina teisingu keliu).
Trūkumas:
- Yra tikimybė, kad daugelis valstybių pasikartos, ir nėra garantijos, kad pavyks rasti sprendimą.
- DFS algoritmas skirtas giliai paieškai ir kartais gali pereiti į begalinę kilpą.
Pavyzdys:
Žemiau esančiame paieškos medyje parodėme paieškos pagal gylį eigą ir ji bus tokia tvarka:
Šakninis mazgas ---> Kairysis mazgas ----> dešinysis mazgas.
Jis pradės ieškoti nuo šakninio mazgo S ir kirs A, tada B, tada D ir E, perėjęs E, jis sugrąžins medį, nes E neturi kito įpėdinio ir vis tiek tikslo mazgas nerastas. Po to, kai jis grįžta atgal, jis kirs mazgą C, o paskui G, ir čia jis baigsis, kai rado tikslo mazgą.
Išsamumas: DFS paieškos algoritmas baigtas baigtinės būsenos erdvėje, nes jis išplės kiekvieną riboto paieškos medžio mazgą.
Laiko sudėtingumas: DFS laiko sudėtingumas bus lygus mazgui, kurį kerta algoritmas. Jį suteikia:
T(n) = 1+ n2+ n3+.........+ nm=O(nm)
Kur m = didžiausias bet kurio mazgo gylis ir jis gali būti daug didesnis nei d (sekliausias tirpalo gylis)
Erdvės sudėtingumas: DFS algoritmas turi saugoti tik vieną kelią iš šakninio mazgo, todėl DFS erdvės sudėtingumas yra lygus pakraščio rinkinio dydžiui, kuris yra O(bm) .
Optimalus: DFS paieškos algoritmas nėra optimalus, nes norint pasiekti tikslo mazgą gali būti atlikta daug žingsnių arba didelės išlaidos.
3. Ribotos gylio paieškos algoritmas:
Riboto gylio paieškos algoritmas yra panašus į paiešką pagal gylį su iš anksto nustatyta riba. Riboto gylio paieška gali išspręsti begalinio kelio trūkumą atliekant paiešką pagal gylį. Pagal šį algoritmą gylio ribos mazgas bus traktuojamas, nes jis nebeturi tolesnių mazgų.
Riboto gylio paieška gali būti nutraukta esant dviem gedimo sąlygoms:
- Standartinė gedimo reikšmė: rodo, kad problema neturi sprendimo.
- Ribinės gedimo vertė: ji neapibrėžia problemos sprendimo tam tikroje gylio riboje.
Privalumai:
Riboto gylio paieška yra efektyvi atmintyje.
Trūkumai:
- Ribotos gilumos paieška taip pat turi trūkumą – neužbaigtumą.
- Jis gali būti neoptimalus, jei problema turi daugiau nei vieną sprendimą.
Pavyzdys:
Išsamumas: DLS paieškos algoritmas baigtas, jei sprendimas viršija gylio ribą.
Laiko sudėtingumas: DLS algoritmo laiko sudėtingumas yra O (bℓ) .
Erdvės sudėtingumas: DLS algoritmo erdvinis sudėtingumas yra O (b�ℓ) .
Optimalus: Riboto gylio paiešką galima vertinti kaip ypatingą DFS atvejį, ji taip pat nėra optimali, net jei ℓ>d.
4. Vienodos kainos paieškos algoritmas:
Vienodos kainos paieška yra paieškos algoritmas, naudojamas svertiniam medžiui ar grafikui pereiti. Šis algoritmas pradedamas veikti, kai kiekvienam kraštui yra skirtinga kaina. Pagrindinis vienodų sąnaudų paieškos tikslas yra rasti kelią į tikslo mazgą, kurio bendra kaina yra mažiausia. Vienodos kainos paieška išplečia mazgus pagal jų kelio sąnaudas iš šakninio mazgo. Jis gali būti naudojamas sprendžiant bet kokį grafiką / medį, kur reikia optimalių išlaidų. Vienodų sąnaudų paieškos algoritmas įgyvendinamas prioritetinėje eilėje. Tai suteikia didžiausią pirmenybę mažiausioms suminėms išlaidoms. Vienodos kainos paieška yra lygiavertė BFS algoritmui, jei visų kraštų kelio kaina yra vienoda.
Privalumai:
- Vienoda kaštų paieška yra optimali, nes kiekvienoje būsenoje pasirenkamas mažiausią kainą turintis kelias.
Trūkumai:
- Jai nerūpi ieškant atliekamų žingsnių skaičius ir rūpi tik kelio kaina. Dėl to šis algoritmas gali būti įstrigęs begalinėje kilpoje.
Pavyzdys:
Išsamumas:
Vienodos kainos paieška baigta, pvz., jei yra sprendimas, UCS jį suras.
Laiko sudėtingumas:
Leisk C* yra optimalaus sprendimo kaina , ir e yra kiekvienas žingsnis siekiant priartėti prie tikslo mazgo. Tada žingsnių skaičius yra = C*/ε+1. Čia mes paėmėme +1, nes pradedame nuo būsenos 0 ir baigiame iki C*/ε.
Taigi, blogiausiu atveju vienodos kainos paieškos sudėtingumas yra O (b1 + [C*/e])/ .
Erdvės sudėtingumas:
Ta pati logika taikoma erdvės sudėtingumui, todėl blogiausiu atveju vienodos kainos paieškos erdvės sudėtingumas yra O (b1 + [C*/e]) .
Optimalus:
minimalus algoritmas
Vienodos kainos paieška visada yra optimali, nes pasirenkamas tik kelias su mažiausia kelio kaina.
5. Iteratyvi gilinimo-pirmiausia paieška:
Iteracinis gilinimo algoritmas yra DFS ir BFS algoritmų derinys. Šis paieškos algoritmas nustato geriausią gylio ribą ir daro tai palaipsniui didindamas ribą, kol randamas tikslas.
Šis algoritmas atlieka giluminę paiešką iki tam tikros „gylio ribos“ ir po kiekvienos iteracijos didina gylio ribą, kol randamas tikslo mazgas.
Šis paieškos algoritmas sujungia greitos paieškos pagal plotį ir atminties efektyvumo pagal gylį paieškos pranašumus.
Iteratyvus paieškos algoritmas yra naudinga neinformuota paieška, kai paieškos erdvė yra didelė, o tikslo mazgo gylis nežinomas.
Privalumai:
- Jis sujungia BFS ir DFS paieškos algoritmo pranašumus greitos paieškos ir atminties efektyvumo požiūriu.
Trūkumai:
- Pagrindinis IDDFS trūkumas yra tas, kad jis pakartoja visus ankstesnio etapo darbus.
Pavyzdys:
Toliau pateikiama medžio struktūra rodo kartotinę gilėjančio gylio paiešką. IDDFS algoritmas atlieka įvairias iteracijas, kol neranda tikslo mazgo. Algoritmo atlikta iteracija pateikiama taip:
1-oji iteracija -----> A
2-oji iteracija ----> A, B, C
3-ioji iteracija ------> A, B, D, E, C, F, G
4-oji iteracija ------> A, B, D, H, I, E, C, F, K, G
Ketvirtoje iteracijoje algoritmas suras tikslo mazgą.
Išsamumas:
Šis algoritmas yra baigtas, jei šakojimosi koeficientas yra baigtinis.
Laiko sudėtingumas:
Tarkime, kad b yra šakojimosi koeficientas, o gylis yra d, tada blogiausio atvejo laiko sudėtingumas yra O (bd) .
Erdvės sudėtingumas:
IDDFS erdvės sudėtingumas bus toks O(bd) .
Optimalus:
IDDFS algoritmas yra optimalus, jei kelio kaina yra nemažėjanti mazgo gylio funkcija.
6. Dvikryptės paieškos algoritmas:
Dviejų krypčių paieškos algoritmas vienu metu atlieka dvi paieškas, kurių viena iš pradinės būsenos vadinama pirmyn, o kita iš tikslo mazgo vadinama paieška atgal, kad surastų tikslo mazgą. Dvikryptė paieška pakeičia vieną paieškos grafiką dviem mažais pografais, kuriuose viena pradedama nuo pradinės viršūnės, o kita pradedama nuo tikslo viršūnės. Paieška sustabdoma, kai šie du grafikai susikerta.
Dviejų krypčių paieška gali naudoti tokius paieškos būdus kaip BFS, DFS, DLS ir kt.
Privalumai:
- Dvikryptė paieška yra greita.
- Dvikrypčiai paieškai reikia mažiau atminties
Trūkumai:
- Dvikryptės paieškos medžio įgyvendinimas yra sudėtingas.
Pavyzdys:
Žemiau esančiame paieškos medyje taikomas dvikryptės paieškos algoritmas. Šis algoritmas padalija vieną grafiką/medį į du pografus. Jis pradeda važiuoti nuo 1 mazgo į priekį ir prasideda nuo tikslo mazgo 16 atgaline kryptimi.
Algoritmas baigiasi 9 mazge, kur susitinka dvi paieškos.
Išsamumas: Dvikryptė paieška baigta, jei abiejose paieškose naudojame BFS.
Laiko sudėtingumas: Dvikryptės paieškos naudojant BFS laiko sudėtingumas yra O (bd) .
Erdvės sudėtingumas: Dvikryptės paieškos erdvės sudėtingumas yra O (bd) .
Optimalus: Dvikryptė paieška yra optimali.