Kaksisuuntainen haku

Kaksisuuntainen leveys- (tai syvyys)haku [1] [2] on hienostunut leveys- (tai syvyys- ) hakualgoritmi , jonka ideana on muodostaa hakuprosessi alkuperäisestä ( eteenpäinhaku ) ja viimeisestä kärjestä ( käänteinen haku ) kaaviosta .

Idea

Halutun polun löytäminen tarkoittaa polkujen määrittämistä alkupisteestä johonkin välikohtaan ja siitä loppupisteeseen. Toteutetaan tarkistamalla yksi tai molemmat prosessit, kun yhden hakupuun lehti vastaa toisen lehtiä, minkä jälkeen polut kyseiseen elementtiin poimitaan. Yhdistämällä polut saamme halutun polun. Jos kaksi hakua suoritetaan rinnakkain  , tämä säästää vielä enemmän aikaa halutun polun löytämiseen verrattuna yksisuuntaiseen hakuun.

Edut ja haitat

• Lisääntynyt suorituskyky;
• Tarvitset muistia hakupuun tallentamiseen, jotta voit tarkistaa, kuuluuko lehti toiseen puuhun.

Vaikeusaste

Koko algoritmin monimutkaisuus arvioidaan eteen- ja taaksepäin tehtyjen hakujen monimutkaisuuden summana, jäsenyyden tarkistus yhtä operaatiota vastaava, vakioaika (O (n)), pääsy hash-taulukkoon .

Operaatioiden lukumäärän laskeminen

Liian riippuvainen tietystä tilanteesta, jos haku ei ole n-aarinen puu .

Kasvavien operaatioiden asymptoottinen monimutkaisuus

• Jos tunnetaan vain tietyt alku- ja kohdeelementit, niin eteenpäin- ja taaksepäinhaun asymptoottinen aikamonimutkaisuus on yhtä suuri kuin , joten kokonaismäärä - + , joka on paljon pienempi kuin . Tilallinen asymptoottinen monimutkaisuus suoran sijasta , koska se on tallennettava muistiin.
• Jos tiedossa on tietty aloituselementti ja joukko elementtejä, kumpi on kohdeelementti.

Tilastollinen arviointi

Kaksisuuntainen haku, kun otetaan huomioon yksi aloitus- ja loppuelementti, voi parantaa yksisuuntaista leveyshakua, tyypillisesti kertoimella 2. Vaikein tapaus kaksisuuntaiselle haulle on sellainen ongelma, jossa vain implisiittinen kuvaus jostain (mahdollisesti hyvin suuresta) kohdetilojen joukosta annetaan tavoitteen tarkistamiseksi, esimerkiksi kaikki tilat, jotka vastaavat tavoitteen "Shakki" mattia. " shakissa . Käänteisessä haussa olisi tarpeen luoda kompaktit kuvaukset kaikista tiloista, jotka sallivat matin liikkeillä jne.; ja nämä kuvaukset olisi tarkistettava suoraan haun luomiin tiloihin. Ei ole olemassa yleistä tapaa ratkaista tällainen ongelma tehokkaasti.

Kaksisuuntainen hakualgoritmi

Algoritmi koostuu:

• suora haku, samanlainen kuin yksihaku;
• käänteinen haku;
• toiminnot sen määrittämiseksi, kuuluuko lehti toiseen hakupuuhun.

Toteutuksen monimutkaisuus

Toteutuksen monimutkaisuus piilee käänteisessä hakualgoritmissa.

Toteutusesimerkkejä

Käytännön sovellus

Katso myös

• Leveys ensimmäinen haku
• Ensimmäinen syvyyshaku

Muistiinpanot

1. ↑ Muu: kaksisuuntainen elementtihaku - suoritetaan kaksisuuntaisissa tai ympyräluetteloissa halutusta elementistä molempiin suuntiin.
2. ↑ [1]  (downlink) Tämä algoritmi on täydellinen ja optimaalinen (yhtenäisin askelkustannuksin), jos molemmat hakuprosessit ovat leveys-ensimmäisiä; muilta menetelmien yhdistelmiltä saattaa puuttua täydellisyyttä, optimaalisuutta tai molempia.

Linkit

• Polunhakualgoritmit osoitteessa pmg.org.ru
• Malleja ja menetelmiä ongelmien ratkaisemiseksi osoitteessa Mari El.ru
• C++-toteutus (aisearch.tgz) osoitteessa www.cs.cmu.edu

Kirjallisuus

• Stuart Russell ja Peter Norvig. Osa 2. Ongelmanratkaisu // Tekoäly (moderni lähestymistapa) = Artificial Intelligence (A Modern Approach). - 2. painos - FGUP. "Print Yard" A.M. Gorky: Williams, 2006. - S. 135-136. — ISBN 5-8459-0887-6 .