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.^[1]

Opis

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

Iako se čini da pretraga mora biti inverzna za obrnutu pretragu, u stvari je samo neophodno pronaći bilo koji dat čvor ${\displaystyle n}$, i čvor ${\displaystyle 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 ${\displaystyle n}$ sa roditeljem ${\displaystyle p}$, onda ${\displaystyle k_{1}(p,n)=k_{2}(n,p)}$, definiše cenu od ${\displaystyle p}$ do ${\displaystyle n}$.

Terminologija i notacija

${\displaystyle b}$

izdvojeni faktor pretrage stabla

${\displaystyle k(n,m)}$

cena puta od čvora ${\displaystyle n}$ do čvora ${\displaystyle m}$

${\displaystyle g(n)}$

cena puta od čvora do ${\displaystyle n}$

${\displaystyle h(n)}$

istraživanje procene puta od čvora ${\displaystyle n}$ do kraja grafa

${\displaystyle s}$

početno mesto

${\displaystyle t}$

krajnje mesto (ponekad se obeležava i sa ${\displaystyle g}$)

${\displaystyle d}$

trenutni smer pretrage, ${\displaystyle d=1}$ za pravilan smer, a za unazad je ${\displaystyle d=2}$.

${\displaystyle d'}$

obrnuti smer pretrage, ${\displaystyle d'=3-d}$.

${\displaystyle TREE_{d}}$

pretraga stabla u pravcu ${\displaystyle d}$

${\displaystyle OPEN_{d}}$

lišće stabla ${\displaystyle TREE_{d}}$

${\displaystyle CLOSED_{d}}$

čvorovi stabla ${\displaystyle 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 ${\displaystyle h}$ čvora ${\displaystyle n}$ koristeći procenu izmedju ${\displaystyle n}$ i korena suprotne pretrage stabla, ${\displaystyle s}$ ili ${\displaystyle 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 ${\displaystyle h}$ čvora ${\displaystyle n}$ koristeći razdaljinu izmedju čvora ${\displaystyle n}$ i podskup ${\displaystyle OPEN_{d}'}$. Pravi primer bi bio BHFFA (Dvosmerna pretraga Front-to-Front algoritmom), gde je funkcija ${\displaystyle h}$ definisana kao minimum istraživačkih procena između trenutnog čvora i njemu suprotnim čvorovima. Formalno:

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

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

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