Dvosmerno pretraživanje

Dvosmerna pretraga je algoritam za pretragu grafa koji pronalazi najkraći put od početnog do krajnjeg čvora grafa. Izvršava dve istovremene pretrage: jedna od početnog čvora, druga od krajnjeg čvora grafa i algoritam prekida sa radom kada se ove dve pretrage nađu na sredini grafa. Razlog zbog koga se pristupa na ovaj način je što je u većini slučajeva pretraga brža: npr, u pojednostavljenom modelu problema složenosti pretrage, u oba slučaja pretrage proširuje stablo izdavajući faktor b, a rastojanje od početnog do krajnjeg čvora grafa d, obe ove pretrage imaju složenost O(b^d/2), i vremenska složenost ove dve pretrage je manja od složenosti O(b^d) koja predstavlja rezultat pretrage od početka do kraja grafa.

Kao u algoritmu pretrage A*, dvosmerna pretraga može biti predvođena istraživačkom procenom preostalog puta do kraja grafa ili do početka grafa.

Ira Pohl je prva dizajnirala i implementirala dvostrani pretraživački algoritam. Endru Goldberg je dao objašnjenje tačne granice mogućeg korišćenja verzije dvosmerne pretrage Dijkstra algoritma.

Opis

Dvosmerno pretraživanje je oblik prostornog pretraživanja od mesta $s$ do mesta $t$, pretraživajući od $s$ do $t$ i od $t$ do $s$ istovremeno. Ovaj algoritam vraća važeći spisak puteva koji ako se primeni na $s$, dolazi se do $t$.

Iako se čini da pretraga mora biti inverzna za obrnutu pretragu, u stvari je samo neophodno pronaći bilo koji dat čvor $n$, i čvor $n$ mora imati validnu operaciju za svakog od njegovih roditelja. Ovo predstavlja jednosmernu ulicu u izboru nalaženja domena: nije neophodno da se ide u oba pravca, ali je neophodno kada se nadjemo na kraju grafa, da znamo moguću putanju do početka grafa.

Obrnuta pretraga će uvek zahtevati inverzne troskove. Formalnije, ako je čvor $n$ sa roditeljem $p$, onda $k_{1}(p,n)=k_{2}(n,p)$, definiše cenu od $p$ do $n$.

Terminologija i notacija

$b$

izdvojeni faktor pretrage stabla

$k(n,m)$

cena puta od čvora $n$ do čvora $m$

$g(n)$

cena puta od čvora do $n$

$h(n)$

istraživanje procene puta od čvora $n$ do kraja grafa

$s$

početno mesto

$t$

krajnje mesto (ponekad se obeležava i sa $g$)

$d$

trenutni smer pretrage, $d=1$ za pravilan smer, a za unazad je $d=2$.

$d'$

obrnuti smer pretrage, $d'=3-d$.

$TREE_{d}$

pretraga stabla u pravcu $d$

$OPEN_{d}$

lišće stabla $TREE_{d}$

$CLOSED_{d}$

čvorovi stabla $TREE_{d}$ koji imaju potomke, ovaj set sadrži čvorove koji su već pretraženi.

Pristup dvosmernom pretraživanju

Dvosmerni pretraživači se mogu svrstati u tri kategorije: Front-to-Front, Front-to-Back, i Obimna pretraga. Razlikuju se po funkciji koju koriste za istraživanje.

Front-to-Back

Front-to-Back algoritam izračunava vrednost $h$ čvora $n$ koristeći procenu izmedju $n$ i korena suprotne pretrage stabla, $s$ ili $t$.

Front-to-Back algoritam je najviše istraživan od sve tri kategorije. Trenutni najbolji algoritam je BiMAX-BS*F algoritam.

Front-to-Front

Front-to-Front algoritam izračunava vrednost $h$ čvora $n$ koristeći razdaljinu izmedju čvora $n$ i podskup $OPEN_{d}'$. Pravi primer bi bio BHFFA (Dvosmerna pretraga Front-to-Front algoritmom), gde je funkcija $h$ definisana kao minimum istraživačkih procena između trenutnog čvora i njemu suprotnim čvorovima. Formalno:

$h_{d}(n)=\min _{i}\left\{H(n,o_{i})|o_{i}\in OPEN_{d'}\right\}$

gde $H(n,o)$ vraća prihvatljivu istraživačku procenu o distanci između čvorova $n$ i $o$.

Front-to-Front pati od toga da bude preterano računski zahtevan. U svakom trenutku kada se čvor $n$ stavi u otvorenu listu, njegova vrednost mora biti izračunata kao $f=g+h$. Ovo uključuje izračunavanje procene od čvora $n$ do svih čvorova koji se nalaze u $OPEN$ set-u. $OPEN$ set se eksponencijalno povećava za sve oblasti u kojima je $b>1$.

Reference

• de Champeaux, Dennis; Sint, Lenie (1977), „An improved bidirectional heuristic search algorithm”, Journal of the ACM, 24 (2): 177—191, doi:10.1145/322003.322004 .
• de Champeaux, Dennis (1983), „Bidirectional heuristic search again”, Journal of the ACM, 30 (1): 22—32, doi:10.1145/322358.322360 .
• Pohl, Ira (1971), „Bi-directional Search”, Ур.: Meltzer, Bernard; Michie, Donald, Machine Intelligence, 6, Edinburgh University Press, стр. 127—140 .
• Russell, Stuart J.; Norvig, Peter (2002), „3.4 Uninformed search strategies”, Artificial Intelligence: A Modern Approach (2nd изд.), Prentice Hall .