Neinformēta meklēšana ir vispārējas nozīmes meklēšanas algoritmu klase, kas darbojas brutālā spēka veidā. Neinformētiem meklēšanas algoritmiem nav papildu informācijas par stāvokli vai meklēšanas telpu, izņemot to, kā šķērsot koku, tāpēc to sauc arī par aklo meklēšanu.

Tālāk ir norādīti dažādi neinformētas meklēšanas algoritmu veidi.

Meklēšana pirmajā vietā Meklēšana pēc dziļuma Dziļuma ierobežota meklēšana Iteratīvā padziļināšanas dziļuma meklēšana Vienota izmaksu meklēšana Divvirzienu meklēšana

1. Meklēšana vispirms:

• Meklēšana pēc platuma ir visizplatītākā meklēšanas stratēģija koka vai grafika šķērsošanai. Šis algoritms meklē platumu kokā vai grafikā, tāpēc to sauc par meklēšanu pēc platuma.
• BFS algoritms sāk meklēšanu no koka saknes mezgla un paplašina visus turpmākos mezglus pašreizējā līmenī, pirms pāriet uz nākamā līmeņa mezgliem.
• Meklēšanas algoritms pēc platuma ir vispārīga grafika meklēšanas algoritma piemērs.
• Pirmā meklēšana, kas ieviesta, izmantojot FIFO rindas datu struktūru.

Priekšrocības:

• BFS nodrošinās risinājumu, ja kāds risinājums pastāv.
• Ja konkrētai problēmai ir vairāki risinājumi, BFS nodrošinās minimālo risinājumu, kas prasa vismazāko darbību skaitu.

Trūkumi:

• Tas prasa daudz atmiņas, jo katrs koka līmenis ir jāsaglabā atmiņā, lai paplašinātu nākamo līmeni.
• BFS ir nepieciešams daudz laika, ja risinājums atrodas tālu no saknes mezgla.

Piemērs:

Zemāk esošajā koka struktūrā mēs esam parādījuši koka šķērsošanu, izmantojot BFS algoritmu no saknes mezgla S līdz mērķa mezglam K. BFS meklēšanas algoritms šķērso slāņus, tāpēc tas sekos ceļam, kas parādīts ar punktētu bultiņu, un šķērsotais ceļš būs:

 S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K 

Laika sarežģītība: BFS algoritma laika sarežģītību var iegūt pēc BFS šķērsoto mezglu skaita līdz seklākajam mezglam. Kur d = seklākā risinājuma dziļums un b ir mezgls katrā stāvoklī.

T (b) = 1+b²+b³+.......+ b^d= O (b^d)

Kosmosa sarežģītība: BFS algoritma telpas sarežģītību nosaka robežas atmiņas lielums, kas ir O (b^d).

Pilnīgums: BFS ir pabeigts, kas nozīmē, ja seklākais mērķa mezgls atrodas kādā ierobežotā dziļumā, tad BFS atradīs risinājumu.

Optimalitāte: BFS ir optimāla, ja ceļa izmaksas ir mezgla dziļuma nesamazinoša funkcija.

2. Meklēšana pēc dziļuma

• Meklēšana pēc dziļuma ir rekursīvs algoritms koka vai grafika datu struktūras šķērsošanai.
• To sauc par meklēšanu pēc dziļuma, jo tā sākas no saknes mezgla un seko katram ceļam līdz lielākajam dziļuma mezglam, pirms pāriet uz nākamo ceļu.
• DFS tās ieviešanai izmanto steka datu struktūru.
• DFS algoritma process ir līdzīgs BFS algoritmam.

Piezīme. Backtracking ir algoritma paņēmiens visu iespējamo risinājumu atrašanai, izmantojot rekursiju.

Priekšrocība:

• DFS prasa ļoti mazāk atmiņas, jo tai ir jāsaglabā tikai mezglu kaudze ceļā no saknes mezgla uz pašreizējo mezglu.
• Lai sasniegtu mērķa mezglu, nepieciešams mazāk laika nekā BFS algoritmam (ja tas šķērso pareizo ceļu).

Trūkums:

java char uz int

• Pastāv iespēja, ka daudzas valstis atkārtojas, un nav garantijas, ka tiks atrasts risinājums.
• DFS algoritms ir paredzēts dziļai meklēšanai, un dažreiz tas var nonākt bezgalīgā cilpā.

Piemērs:

Zemāk esošajā meklēšanas kokā mēs esam parādījuši dziļuma meklēšanas plūsmu, un tā notiks šādā secībā:

Saknes mezgls--->Kreisais mezgls ----> labais mezgls.

Tas sāks meklēšanu no saknes mezgla S un šķērsos A, pēc tam B, pēc tam D un E, pēc tam, kad ir šķērsojis E, tas atgriezīsies kokā, jo E nav cita pēcteča un joprojām mērķa mezgls netiek atrasts. Pēc atkāpšanās tas šķērsos mezglu C un pēc tam G, un šeit tas beigsies, kad ir atradis mērķa mezglu.

Pilnīgums: DFS meklēšanas algoritms ir pabeigts ierobežotā stāvokļa telpā, jo tas paplašinās katru mezglu ierobežotā meklēšanas kokā.

Laika sarežģītība: DFS laika sarežģītība būs līdzvērtīga mezglam, ko šķērso algoritms. To piešķir:

T(n)= 1+ n²+ n³+.........+ n^m=O(n^m)

Kur m = jebkura mezgla maksimālais dziļums, un tas var būt daudz lielāks par d (seklākais risinājuma dziļums)

Kosmosa sarežģītība: DFS algoritmam ir jāsaglabā tikai viens ceļš no saknes mezgla, tāpēc DFS telpas sarežģītība ir līdzvērtīga malu kopas lielumam, kas ir O(bm) .

Optimāli: DFS meklēšanas algoritms nav optimāls, jo tas var radīt lielu skaitu darbību vai augstas izmaksas, lai sasniegtu mērķa mezglu.

3. Ierobežotas dziļuma meklēšanas algoritms:

Ierobežota dziļuma meklēšanas algoritms ir līdzīgs dziļuma meklēšanai ar iepriekš noteiktu ierobežojumu. Dziļuma ierobežota meklēšana var atrisināt bezgalīgā ceļa trūkumu meklēšanā pēc dziļuma. Šajā algoritmā mezgls pie dziļuma robežas tiks apstrādāts, jo tam vairs nav pēcteču mezglu.

Dziļuma ierobežotu meklēšanu var pārtraukt ar diviem neveiksmes nosacījumiem:

• Standarta atteices vērtība: norāda, ka problēmai nav risinājuma.
• Robežvērtības atteices vērtība: tā nedefinē problēmas risinājumu noteiktā dziļuma robežās.

Priekšrocības:

Dziļuma ierobežota meklēšana ir efektīva atmiņai.

Trūkumi:

• Dziļuma ierobežotas meklēšanas trūkums ir arī nepilnīgums.
• Tas var nebūt optimāls, ja problēmai ir vairāki risinājumi.

Piemērs:

Pilnīgums: DLS meklēšanas algoritms ir pabeigts, ja risinājums pārsniedz dziļuma ierobežojumu.

Laika sarežģītība: DLS algoritma laika sarežģītība ir O(b^ℓ) .

Kosmosa sarežģītība: DLS algoritma kosmosa sarežģītība ir O (b�ℓ) .

Optimāli: Dziļuma ierobežotu meklēšanu var uzskatīt par īpašu DFS gadījumu, un tā arī nav optimāla, pat ja ℓ>d.

4. Vienotu izmaksu meklēšanas algoritms:

Vienotu izmaksu meklēšana ir meklēšanas algoritms, ko izmanto svērtā koka vai grafika šķērsošanai. Šis algoritms tiek izmantots, ja katrai malai ir pieejamas atšķirīgas izmaksas. Vienotas izmaksu meklēšanas galvenais mērķis ir atrast ceļu uz mērķa mezglu, kuram ir viszemākās kumulatīvās izmaksas. Vienotu izmaksu meklēšana paplašina mezglus atbilstoši to ceļa izmaksām no saknes mezgla. To var izmantot, lai atrisinātu jebkuru grafiku/koku, kur ir pieprasītas optimālās izmaksas. Vienotu izmaksu meklēšanas algoritmu īsteno prioritārā rinda. Tas dod maksimālu prioritāti zemākajām kumulatīvajām izmaksām. Vienota izmaksu meklēšana ir līdzvērtīga BFS algoritmam, ja ceļa izmaksas visām malām ir vienādas.

Priekšrocības:

• Vienota izmaksu meklēšana ir optimāla, jo katrā stāvoklī tiek izvēlēts ceļš ar viszemākajām izmaksām.

Trūkumi:

• Tam nerūp meklēšanā iesaistīto darbību skaits, un tas rūpējas tikai par ceļa izmaksām. Sakarā ar to šis algoritms var iestrēgt bezgalīgā cilpā.

Piemērs:

Pilnīgums:

Vienotu izmaksu meklēšana ir pabeigta, piemēram, ja ir risinājums, UCS to atradīs.

Laika sarežģītība:

Ļaujiet C* ir optimālā risinājuma izmaksas , un e ir katrs solis, lai tuvotos mērķa mezglam. Tad soļu skaits ir = C*/ε+1. Šeit mēs esam paņēmuši +1, jo mēs sākam no stāvokļa 0 un beidzam līdz C*/ε.

Līdz ar to Vienotās maksas meklēšana ir sliktākā laika sarežģītība O(b^{1 + [C*/e]})/ .

Kosmosa sarežģītība:

Tāda pati loģika attiecas uz telpas sarežģītību, tāpēc vissliktākā gadījuma kosmosa sarežģītība vienotās izmaksu meklēšanas gadījumā ir O(b^{1 + [C*/e]}) .

Optimāli:

Vienotu izmaksu meklēšana vienmēr ir optimāla, jo tā atlasa tikai ceļu ar viszemākajām ceļa izmaksām.

5. Iteratīvā padziļināšanas un dziļuma meklēšana:

Iteratīvais padziļināšanas algoritms ir DFS un BFS algoritmu kombinācija. Šis meklēšanas algoritms nosaka labāko dziļuma ierobežojumu un dara to, pakāpeniski palielinot ierobežojumu, līdz tiek atrasts mērķis.

Šis algoritms veic dziļuma meklēšanu līdz noteiktam “dziļuma ierobežojumam”, un tas turpina palielināt dziļuma ierobežojumu pēc katras iterācijas, līdz tiek atrasts mērķa mezgls.

Šis meklēšanas algoritms apvieno ātrās meklēšanas un pēc dziļuma meklēšanas atmiņas efektivitātes priekšrocības.

Iteratīvās meklēšanas algoritms ir noderīgs neinformētai meklēšanai, ja meklēšanas vieta ir liela un mērķa mezgla dziļums nav zināms.

Priekšrocības:

• Tas apvieno BFS un DFS meklēšanas algoritma priekšrocības ātras meklēšanas un atmiņas efektivitātes ziņā.

Trūkumi:

• Galvenais IDDFS trūkums ir tas, ka tas atkārto visu iepriekšējās fāzes darbu.

Piemērs:

Sekojošā koka struktūra parāda iteratīvo padziļināšanas dziļuma meklēšanu. IDDFS algoritms veic dažādas iterācijas, līdz neatrod mērķa mezglu. Algoritma veiktā iterācija ir norādīta šādi:

1. atkārtojums -----> A
2. iterācija ----> A, B, C
3. atkārtojums ------> A, B, D, E, C, F, G
4'th Iteration ------>A, B, D, H, I, E, C, F, K, G
Ceturtajā iterācijā algoritms atradīs mērķa mezglu.

izrakstīšanās ar git

Pilnīgums:

Šis algoritms ir pabeigts, ja sazarojuma faktors ir ierobežots.

Laika sarežģītība:

Pieņemsim, ka b ir sazarojuma faktors un dziļums ir d, tad sliktākā gadījuma laika sarežģītība ir O(b^d) .

Kosmosa sarežģītība:

IDDFS kosmosa sarežģītība būs O(bd) .

Optimāli:

IDDFS algoritms ir optimāls, ja ceļa izmaksas ir mezgla dziļuma nesamazinoša funkcija.

6. Divvirzienu meklēšanas algoritms:

Divvirzienu meklēšanas algoritms veic divus vienlaicīgus meklējumus, vienu no sākotnējā stāvokļa sauc par meklēšanu uz priekšu, bet otru no mērķa mezgla sauc par meklēšanu atpakaļ, lai atrastu mērķa mezglu. Divvirzienu meklēšana aizvieto vienu meklēšanas grafiku ar diviem maziem apakšgrafikiem, kuros viens sāk meklēšanu no sākotnējās virsotnes, bet otrs sāk no mērķa virsotnes. Meklēšana tiek pārtraukta, kad šie divi grafiki krustojas viens ar otru.

Divvirzienu meklēšanā var izmantot tādas meklēšanas metodes kā BFS, DFS, DLS utt.

Priekšrocības:

• Divvirzienu meklēšana ir ātra.
• Divvirzienu meklēšanai ir nepieciešams mazāk atmiņas

Trūkumi:

• Divvirzienu meklēšanas koka ieviešana ir sarežģīta.
Veicot divvirzienu meklēšanu, iepriekš jāzina mērķa stāvoklis.

Piemērs:

Zemāk esošajā meklēšanas kokā tiek izmantots divvirzienu meklēšanas algoritms. Šis algoritms sadala vienu grafiku/koku divos apakšgrafikos. Tas sāk šķērsot no 1. mezgla virzienā uz priekšu un sākas no mērķa mezgla 16 atpakaļ virzienā.

Algoritms beidzas 9. mezglā, kur satiekas divi meklējumi.

Pilnīgums: Divvirzienu meklēšana ir pabeigta, ja abos meklējumos izmantojam BFS.

Laika sarežģītība: Divvirzienu meklēšanas laika sarežģītība, izmantojot BFS, ir O(b^d) .

Kosmosa sarežģītība: Divvirzienu meklēšanas telpas sarežģītība ir O(b^d) .

Optimāli: Divvirzienu meklēšana ir optimāla.