Tietoton haku on yleiskäyttöisten hakualgoritmien luokka, joka toimii raa'alla voimalla. Epätietoisilla hakualgoritmeilla ei ole muuta tietoa tilasta tai hakuavaruudesta kuin puun kulkemisesta, joten sitä kutsutaan myös sokeaksi hauksi.

Seuraavassa on erilaisia ​​tietämättömiä hakualgoritmeja:

Breadth-fir-haku Syvyys ensin haku Syvyysrajoitettu haku Iteratiivinen syventävä syvyyshaku Yhtenäinen kustannushaku Kaksisuuntainen haku

1. Breadth-first-haku:

• Leveyshaku on yleisin hakustrategia puun tai kaavion läpikäymiseen. Tämä algoritmi etsii leveyssuunnassa puusta tai graafista, joten sitä kutsutaan leveyshakuksi.
• BFS-algoritmi aloittaa haun puun juurisolmusta ja laajentaa kaikki seuraajasolmut nykyisellä tasolla ennen siirtymistä seuraavan tason solmuihin.
• Leveys ensin -hakualgoritmi on esimerkki yleiskuvaajan hakualgoritmista.
• Leveysensimmäinen haku toteutettu käyttämällä FIFO-jonotietorakennetta.

Edut:

• BFS tarjoaa ratkaisun, jos sellainen on olemassa.
• Jos tietylle ongelmalle on useampi kuin yksi ratkaisu, BFS tarjoaa minimiratkaisun, joka vaatii vähiten vaiheita.

Haitat:

• Se vaatii paljon muistia, koska jokainen puun taso on tallennettava muistiin seuraavan tason laajentamiseksi.
• BFS tarvitsee paljon aikaa, jos ratkaisu on kaukana juurisolmusta.

Esimerkki:

Alla olevassa puurakenteessa olemme näyttäneet puun läpikulkua käyttämällä BFS-algoritmia juurisolmusta S tavoitesolmuun K. BFS-hakualgoritmi kulkee kerroksittain, joten se seuraa polkua, joka näkyy pistenuolella ja kuljettu polku tulee olemaan:

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

Aika monimutkaisuus: BFS-algoritmin aikamonimutkaisuus voidaan saada BFS:ssä matalimpaan solmuun kuljetettujen solmujen lukumäärällä. Missä d = matalimman ratkaisun syvyys ja b on solmu jokaisessa tilassa.

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

Tilan monimutkaisuus: BFS-algoritmin avaruusmonimutkaisuus saadaan rajan muistin koosta, joka on O(b^d).

Täydellisyys: BFS on valmis, mikä tarkoittaa, että jos matalin tavoitesolmu on jossain äärellisessä syvyydessä, BFS löytää ratkaisun.

Optimaalisuus: BFS on optimaalinen, jos polun hinta on solmun syvyyden ei-laskeva funktio.

2. Syvyys ensin -haku

• Syvyys-ensimmäinen haku on rekursiivinen algoritmi puu- tai graafitietorakenteen läpikulkuun.
• Sitä kutsutaan syvyys-ensimmäiseksi hauksi, koska se alkaa juurisolmusta ja seuraa kutakin polkua sen suurimpaan syvyyssolmuun ennen siirtymistä seuraavaan polkuun.
• DFS käyttää pinotietorakennetta toteuttaessaan.
• DFS-algoritmin prosessi on samanlainen kuin BFS-algoritmin.

Huomautus: Backtracking on algoritmitekniikka kaikkien mahdollisten ratkaisujen löytämiseksi rekursion avulla.

Etu:

rom

• DFS vaatii hyvin vähemmän muistia, koska sen tarvitsee tallentaa vain pino polkua juurisolmusta nykyiseen solmuun.
• Tavoitesolmuun saavuttaminen vie vähemmän aikaa kuin BFS-algoritmi (jos se kulkee oikeaa polkua).

Haitta:

• On mahdollista, että monet osavaltiot toistuvat jatkuvasti, eikä ole takeita ratkaisun löytämisestä.
• DFS-algoritmi käy syvälle hakuun ja joskus se voi mennä äärettömään silmukkaan.

Esimerkki:

Alla olevassa hakupuussa olemme näyttäneet syvyys-ensimmäisen haun kulun, ja se noudattaa seuraavaa järjestystä:

Juurisolmu ---> Vasen solmu ----> oikea solmu.

Se aloittaa haun juurisolmusta S ja kulkee A:n, sitten B:n, sitten D:n ja E:n poikki. Kuljettuaan E:n se lähtee puusta taaksepäin, koska E:llä ei ole muuta seuraajaa ja silti tavoitesolmua ei löydy. Perääntymisen jälkeen se kulkee solmun C ja sitten G läpi, ja tässä se päättyy, kun se löysi tavoitesolmun.

Täydellisyys: DFS-hakualgoritmi on valmis äärellisessä tila-avaruudessa, koska se laajentaa jokaista solmua rajoitetussa hakupuussa.

Aika monimutkaisuus: DFS:n aikamonimutkaisuus vastaa algoritmin kulkemaa solmua. Sen antaa:

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

Missä m = minkä tahansa solmun suurin syvyys ja tämä voi olla paljon suurempi kuin d (matalin ratkaisusyvyys)

Tilan monimutkaisuus: DFS-algoritmin täytyy tallentaa vain yksi polku juurisolmusta, joten DFS:n tilamonimutkaisuus vastaa reunajoukon kokoa, joka on O(bm) .

Optimaalinen: DFS-hakualgoritmi ei ole optimaalinen, koska se voi tuottaa suuren määrän vaiheita tai korkeita kustannuksia päästäksesi tavoitesolmuun.

3. Syvyysrajoitettu hakualgoritmi:

Syvyysrajoitettu hakualgoritmi on samanlainen kuin syvyys-ensimmäinen haku ennalta määrätyllä rajalla. Syvyysrajoitettu haku voi ratkaista äärettömän polun haitan Syvyys-ensimmäisessä haussa. Tässä algoritmissa syvyysrajalla oleva solmu käsittelee, koska sillä ei ole enää seuraajasolmuja.

Syvyysrajoitettu haku voidaan lopettaa kahdella epäonnistumisella:

• Vakiovikaarvo: Se osoittaa, että ongelmalle ei ole ratkaisua.
• Rajavirhearvo: Se ei määrittele ongelman ratkaisua tietyn syvyysrajan sisällä.

Edut:

Syvyysrajoitettu haku on muistitehokas.

Haitat:

• Syvyysrajoitetun haun haittana on myös epätäydellisyys.
• Se ei ehkä ole optimaalinen, jos ongelmalla on useampi kuin yksi ratkaisu.

Esimerkki:

Täydellisyys: DLS-hakualgoritmi on valmis, jos ratkaisu on syvyysrajan yläpuolella.

Aika monimutkaisuus: DLS-algoritmin aikamonimutkaisuus on O(b^ℓ) .

Tilan monimutkaisuus: DLS-algoritmin avaruusmonimutkaisuus on O (b�ℓ) .

Optimaalinen: Syvyysrajoitettu haku voidaan nähdä DFS:n erikoistapauksena, eikä se myöskään ole optimaalinen, vaikka ℓ>d.

4. Yhtenäisten kustannusten hakualgoritmi:

Uniform-cost-haku on hakualgoritmi, jota käytetään painotetun puun tai graafin läpikulkuun. Tämä algoritmi tulee käyttöön, kun jokaiselle reunalle on saatavilla eri hinta. Yhtenäisten kustannusten haun ensisijainen tavoite on löytää polku tavoitesolmuun, jolla on alhaisin kumulatiivinen kustannus. Uniform-cost-haku laajentaa solmuja niiden polkukustannusten mukaan juurisolmusta. Sitä voidaan käyttää minkä tahansa kaavion/puun ratkaisemiseen, missä optimaalinen hinta on kysyntää. Tasahintaisen hakualgoritmin toteuttaa prioriteettijono. Se antaa suurimman etusijan pienimmille kumulatiivisille kustannuksille. Yhtenäinen kustannushaku vastaa BFS-algoritmia, jos kaikkien reunojen polkukustannukset ovat samat.

Edut:

• Yhtenäinen kustannushaku on optimaalinen, koska jokaisessa tilassa valitaan edullisin polku.

Haitat:

• Se ei välitä hakuun liittyvien vaiheiden määrästä ja on huolissaan vain polun kustannuksista. Tämän vuoksi tämä algoritmi voi juuttua äärettömään silmukkaan.

Esimerkki:

Täydellisyys:

Yhtenäisten kustannusten haku on valmis, esimerkiksi jos ratkaisu on olemassa, UCS löytää sen.

Aika monimutkaisuus:

Anna C* on optimaalisen ratkaisun hinta , ja e on jokainen askel päästäksesi lähemmäksi tavoitesolmua. Tällöin askelmäärä on = C*/ε+1. Tässä olemme ottaneet +1, kun aloitamme tilasta 0 ja päätämme C*/ε.

Tästä syystä yhtenäisten kustannusten haun pahin aika monimutkaisuus on O(b^{1 + [C*/e]})/ .

Tilan monimutkaisuus:

Sama logiikka koskee tilan monimutkaisuutta, joten yhtenäisten kustannusten haun pahimman mahdollisen tilan monimutkaisuus on O(b^{1 + [C*/e]}) .

Optimaalinen:

Yhtenäisten kustannusten haku on aina optimaalinen, koska se valitsee vain polun, jolla on alhaisin polkuhinta.

5. Iteratiivinen syvyyssyvyyshaku:

Iteratiivinen syvennysalgoritmi on DFS- ja BFS-algoritmien yhdistelmä. Tämä hakualgoritmi löytää parhaan syvyysrajan ja tekee sen nostamalla rajaa vähitellen, kunnes tavoite löytyy.

Tämä algoritmi suorittaa syvyysensimmäisen haun tiettyyn 'syvyysrajaan' asti, ja se jatkaa syvyysrajan kasvattamista jokaisen iteraation jälkeen, kunnes tavoitesolmu löytyy.

Tämä hakualgoritmi yhdistää Breadth-first-haun nopean haun ja syvähaun muistitehokkuuden edut.

Iteratiivinen hakualgoritmi on hyödyllinen epätietoinen haku, kun hakutila on suuri ja tavoitesolmun syvyyttä ei tunneta.

Edut:

• Siinä yhdistyvät BFS- ja DFS-hakualgoritmien edut nopean haun ja muistin tehokkuuden suhteen.

Haitat:

• IDDFS:n suurin haittapuoli on, että se toistaa kaiken edellisen vaiheen työn.

Esimerkki:

Seuraava puurakenne näyttää iteratiivisen syvenevän syvyyshaun. IDDFS-algoritmi suorittaa erilaisia ​​iteraatioita, kunnes se ei löydä tavoitesolmua. Algoritmin suorittama iteraatio esitetään seuraavasti:

on yhtä kuin merkkijono javassa

1. iteraatio -----> A
2. iteraatio ----> A, B, C
3. iteraatio ------>A, B, D, E, C, F, G
4. iteraatio ------>A, B, D, H, I, E, C, F, K, G
Neljännessä iteraatiossa algoritmi löytää tavoitesolmun.

Täydellisyys:

Tämä algoritmi on valmis, jos haarautumiskerroin on äärellinen.

Aika monimutkaisuus:

Oletetaan, että b on haarautumiskerroin ja syvyys on d, niin pahimman tapauksen aikamonimutkaisuus on O(b^d) .

Tilan monimutkaisuus:

IDDFS:n avaruuden monimutkaisuus tulee olemaan O(bd) .

Optimaalinen:

IDDFS-algoritmi on optimaalinen, jos polun hinta on solmun syvyyden ei-laskeva funktio.

6. Kaksisuuntainen hakualgoritmi:

Kaksisuuntainen hakualgoritmi suorittaa kaksi samanaikaista hakua, joista toinen on lähtötila, jota kutsutaan eteenpäinhakuksi ja toinen tavoitesolmusta, jota kutsutaan taaksepäin hauksi, löytääkseen tavoitesolmun. Kaksisuuntainen haku korvaa yhden hakugraafin kahdella pienellä aligraafilla, joista toinen aloittaa haun alkupisteestä ja toinen aloittaa tavoitepisteestä. Haku pysähtyy, kun nämä kaksi kuvaajaa leikkaavat toisensa.

Kaksisuuntainen haku voi käyttää hakutekniikoita, kuten BFS, DFS, DLS jne.

Edut:

• Kaksisuuntainen haku on nopeaa.
• Kaksisuuntainen haku vaatii vähemmän muistia

Haitat:

• Kaksisuuntaisen hakupuun toteuttaminen on vaikeaa.
Kaksisuuntaisessa haussa tavoitetila tulee tietää etukäteen.

Esimerkki:

Alla olevassa hakupuussa käytetään kaksisuuntaista hakualgoritmia. Tämä algoritmi jakaa yhden kuvaajan/puun kahdeksi aligraafiksi. Se alkaa kulkea solmusta 1 eteenpäin ja alkaa tavoitesolmusta 16 taaksepäin.

Algoritmi päättyy solmuun 9, jossa kaksi hakua kohtaavat.

Täydellisyys: Kaksisuuntainen haku on valmis, jos käytämme BFS:ää molemmissa hauissa.

Aika monimutkaisuus: BFS:ää käyttävän kaksisuuntaisen haun aikamonimutkaisuus on O(b^d) .

Tilan monimutkaisuus: Kaksisuuntaisen haun avaruusmonimutkaisuus on O(b^d) .

Optimaalinen: Kaksisuuntainen haku on optimaalinen.