Tietoton etsintä (myös sokea etsintä , brute force method , eng. uninformed search, sokea etsintä, brute-force search ) on tilaavaruuden ratkaisujen etsimisstrategia , jossa ei käytetä lisätietoa tiloista, lukuun ottamatta niitä, jotka on esitetty tehtävän määrittely. Tiedonhaun menetelmä pystyy vain kehittämään seuraajia ja erottamaan kohdetilan ei-kohdetilasta [1] [2] [3] .
Breadth-first -haku ( BFS ) on tila-avaruusratkaisun hakustrategia, joka laajentaa ensin juurisolmun, sitten kaikki juurisolmun seuraajat, sitten näiden seuraajien seuraajat ja niin edelleen. Ennen kuin solmuja laajennetaan seuraavalle tasolle, kaikki hakupuun tietyllä syvyydellä olevat solmut laajennetaan.
Algoritmi on valmis. Jos kaikilla toimilla on sama hinta, leveys ensin -haku on optimaalinen.
Muodostettujen solmujen kokonaismäärä (aikakompleksisuus) on O( bd +1 ), missä b on haarautumiskerroin, d on hakusyvyys . Avaruuden kompleksisuus on myös O( b d +1 ) [1] .
Ensimmäinen leveyshaku -toteutus voi käyttää FIFO - jonoa . Alussa jono sisältää vain juurisolmun. Pääsilmukan jokaisessa iteraatiossa curr -solmu noudetaan jonon päästä . Jos solmu curr on kohdesolmu, haku pysähtyy, muuten curr -solmu puretaan ja kaikki sen seuraajat lisätään jonon loppuun [4] [5] .
funktio BFS ( v : Solmu ) : Boolen arvo ; aloita jono ( v ) ; kun jono ei ole tyhjä , aloita curr := dequeue () ; jos on_tavoite ( curr ) aloita BFS : = true ; poistua ; loppu ; merkki ( curr ) ; seuraaville seuraajille ( curr ) tee , jos sitä ei ole merkitty ( seuraava ) , aloita sitten enqueue ( seuraava ) ; loppu ; loppu ; BFS := false ; loppu ;
Kustannushaku (uniform-cost search, UCS ) on leveys-ensimmäisen hakualgoritmin yleistys, joka ottaa huomioon toimien kustannukset (tilakaavion reunat). Kustannuksiin perustuva haku laajentaa solmut nousevassa järjestyksessä juurisolmun lyhimmän polun hinnan mukaan. Algoritmin jokaisessa vaiheessa otetaan käyttöön solmu, jonka kustannukset ovat alhaisin g ( n ). Solmut tallennetaan prioriteettijonoon [6] .
Tämä algoritmi on täydellinen ja optimaalinen, jos vaiheiden kustannukset ovat ehdottomasti positiiviset. Jos kaikkien vaiheiden kustannukset ovat samat, kustannushaku on identtinen leveyshaun kanssa.
Kustannushakumenettely voi siirtyä äärettömään silmukkaan, jos siinä sattuu olemaan käyttöön solmu, jolla on nollakustannustoiminto, joka taas osoittaa samaan tilaan. On mahdollista taata haun täydellisyys ja optimaalisuus edellyttäen, että kaikkien toimien kustannukset ovat ehdottomasti positiiviset [1] .
Kustannusperusteinen haku vastaa loogisesti Dijkstran yhden lähteen lyhimmän polun algoritmia . Erityisesti molemmat algoritmit käyttävät samoja solmuja samassa järjestyksessä. Suurin ero liittyy solmujen läsnäoloon prioriteettijonossa: Dijkstran algoritmissa kaikki solmut lisätään jonoon alustuksen aikana, kun taas kustannusperusteisessa hakualgoritmissa solmut lisätään "lennossa" ( engl . . lennossa, laiskasti ) haun aikana. Tästä seuraa, että Dijkstran algoritmia voidaan soveltaa eksplisiittisiin graafisiin, kun taas UCS-algoritmia voidaan soveltaa sekä eksplisiittisiin että implisiittisiin graafisiin [7] .
Depth -first search ( DFS ) on tila-avaruuspäätösten hakustrategia, joka laajentaa aina hakupuun nykyisen reunan syvimmän solmun. Syvyys-ensimmäinen haku analysoi luettelon nykyisen solmun ensimmäisen seuraajan, sitten sen ensimmäisen seuraajan ja niin edelleen. Laajennetut solmut poistetaan reunalta, joten lisähaku "jatkuu" seuraavaksi matalimmasta solmusta, jota ei ole vielä tutkittu. seuraajat [1] .
Syvyys-ensimmäinen hakustrategia voidaan toteuttaa LIFO - pinon avulla tai rekursiivisella funktiolla [8] .
toiminto DFS ( v : solmu ; syvyys : kokonaisluku ) : Boolen ; aloita jos on_tavoite ( v ) then begin DFS := true ; poistua ; loppu ; seuraaville seuraajille ( v ) do if DFS ( seuraava , syvyys + 1 ) aloita sitten DFS : = true ; _ poistua ; loppu ; DFS := false ; loppu ;
Syvyysrajoitettu haku ( DLS ) on muunnelma syvyysensimmäisestä hausta, joka käyttää ennalta määritettyä syvyysrajaa l ratkaisemaan äärettömän polun ongelman.
Syvyysrajoitettu haku ei ole valmis, koska kohteelle l < d kohdetta ei löydy, eikä se ole optimaalinen kohteelle l > d . Sen aikakompleksisuus on O( bl ) ja avaruuskompleksisuus O( b · l ) [1] [ 9] .
Iteratiivisessa syventävässä hakualgoritmissa käytetään syvyysrajoitettua hakua.
funktio DLS ( v : Solmu ; syvyys , raja : kokonaisluku ) : Boolen ; begin if ( syvyys < raja ) then begin if is_goal ( v ) then begin DLS := true ; poistua ; loppu ; seuraaville seuraajille ( v ) aloita jos DLS ( seuraava , syvyys + 1 , raja ) ja aloita sitten DLS : = true ; _ poistua ; loppu ; loppu ; loppu ; DLS := false ; loppu ;
Syvyys-ensin haku iteratiivisella syventämisellä (iteratiivisen syventämisen syvyys-ensin haku, IDDFS , DFID ) on strategia, jonka avulla voit löytää parhaan syvyysrajan DLS-haulle. Tämä saavutetaan nostamalla asteittain rajaa l , kunnes tavoite löytyy.
Iteratiivinen syventävä haku yhdistää syvyyshaun (avaruuden kompleksisuus O( b · l )) ja leveyshaun (täydellisyys ja optimaalisuus äärellisille b ja ei-negatiivisille reunapainoille) edut.
Vaikka iteratiivinen syvähaku tuottaa samat tilat useita kertoja, useimmat solmut ovat hakupuun alaosassa, joten solmujen uudelleenlaajentamiseen käytetty aika voidaan yleensä jättää huomiotta. Algoritmin aikamonimutkaisuus on O( b l ) [1] [9] [10] .
toiminto IDDFS ( v : Solmu ) : Kokonaisluku ; var lim : Kokonaisluku ; alkaa lim := 0 ; kun taas ei DLS ( v , 0 , lim ) do lim := lim + 1 ; IDDFS := lim ; loppu ;
Leveys (tai syvyys) kaksisuuntainen haku on hienostunut leveys (tai syvyys) hakualgoritmi, jonka ideana on, että kaksi hakua voidaan suorittaa samanaikaisesti (eteenpäin, lähtötilasta ja vastakkaiseen suuntaan, alkaen kohde), pysähtyy, kun kaksi hakuprosessia kohtaavat keskellä.
Kaksisuuntainen haku voi perustua iteratiiviseen syventämisstrategiaan. Yksi iteraatio sisältää haun syvyyteen k eteenpäin ja kaksi hakua syvyyteen k ja k + 1 taaksepäin. Koska vain suoralla haulla syvyydeltä k löydetyt tilat tallennetaan muistiin, haun tilakompleksisuus määritellään O ( bd /2 ). Sen tarkistaminen kuuluuko taaksepäin etsimällä löydetty solmu eteenpäin suuntautuvan hakupuun reuna-alueelle voidaan suorittaa vakioajassa, joten kaksisuuntaisen haun aikamonimutkaisuus määritellään O ( b d /2 ) [1] [9] [ 11] .
| Kaavion hakualgoritmit | ||
|---|---|---|
| Tietämättömät menetelmät | ||
| Tietoon perustuvat menetelmät | ||
| Pikanäppäimet | ||
| Vähintään ulottuva puu | ||
| Muut | ||