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^{\prime }$

obrnuti smer pretrage, $d^{\prime }=3-d$.

$TRE{E}_d$

pretraga stabla u pravcu $d$

$OPE{N}_d$

lišće stabla $TRE{E}_d$

$CLOSE{D}_d$

čvorovi stabla $TRE{E}_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 $OPE{N_d}^{\prime }$. 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)=\underset{i}{\min }\{H(n,o_i)|o_i\in OPE{N}_{d^{\prime }}\}$

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

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.