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(bd/2), i vremenska složenost ove dve pretrage je manja od složenosti O(bd) 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  do mesta , pretraživajući od  do  i od  do  istovremeno. Ovaj algoritam vraća važeći spisak puteva koji ako se primeni na , dolazi se do . 

Iako se čini da pretraga mora biti inverzna za obrnutu pretragu, u stvari je samo neophodno pronaći bilo koji dat čvor , i čvor  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  sa roditeljem , onda , definiše cenu od  do .

Terminologija i notacija 
   izdvojeni faktor pretrage stabla
   cena puta od čvora  do čvora 
   cena puta od čvora do  
   istraživanje procene puta od čvora  do kraja grafa
   početno mesto
   krajnje mesto (ponekad se obeležava i sa )
   trenutni smer pretrage,  za pravilan smer, a za unazad je .
   obrnuti smer pretrage, .
   pretraga stabla u pravcu 
   lišće stabla 
   čvorovi stabla  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  čvora  koristeći procenu izmedju  i korena suprotne pretrage stabla,  ili .

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  čvora  koristeći razdaljinu izmedju čvora  i podskup . Pravi primer bi bio BHFFA (Dvosmerna pretraga Front-to-Front algoritmom), gde je funkcija  definisana kao minimum istraživačkih procena između trenutnog čvora i njemu suprotnim čvorovima. Formalno:

gde  vraća prihvatljivu istraživačku procenu o distanci između čvorova  i .

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

Reference 

 . 
 . 
 .
 .

Графовски алгоритми
Алгоритми претраживања
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( bd /2 ) , i vremenska složenost ove dve pretrage je manja od složenosti O( bd ) 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 do mesta , pretraživajući od do i od do istovremeno . Ovaj algoritam vraća važeći spisak puteva koji ako se primeni na , dolazi se do \ . Iako se čini da pretraga mora biti inverzna za obrnutu pretragu , u stvari je samo neophodno pronaći bilo koji dat čvor , i čvor 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 sa roditeljem , onda , definiše cenu od do \ . Terminologija i notacija izdvojeni faktor pretrage stabla cena puta od čvora do čvora cena puta od čvora do istraživanje procene puta od čvora do kraja grafa početno mesto krajnje mesto ( ponekad se obeležava i sa ) trenutni smer pretrage , za pravilan smer , a za unazad je \. obrnuti smer pretrage , \. pretraga stabla u pravcu lišće stabla čvorovi stabla 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 čvora koristeći procenu izmedju i korena suprotne pretrage stabla , ili \ . 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 čvora koristeći razdaljinu izmedju čvora i podskup \ . Pravi primer bi bio BHFFA ( Dvosmerna pretraga Front-to-Front algoritmom ) , gde je funkcija definisana kao minimum istraživačkih procena između trenutnog čvora i njemu suprotnim čvorovima . Formalno : gde vraća prihvatljivu istraživačku procenu o distanci između čvorova i \ . Front-to-Front pati od toga da bude preterano računski zahtevan . U svakom trenutku kada se čvor stavi u otvorenu listu , njegova vrednost mora biti izračunata kao \ . Ovo uključuje izračunavanje procene od čvora do svih čvorova koji se nalaze u set-u . set se eksponencijalno povećava za sve oblasti u kojima je \ . Reference \ . \ . \ . \ . Графовски алгоритми Алгоритми претраживања