Kétirányú keresés

A kétirányú keresés egy keresőalgoritmus egy gráfban: egy irányított gráfban megkeresi a legrövidebb utat a kezdeti csúcstól a célcsúcsig.

Két keresés zajlik párhuzamosan: az egyik a kezdeti csúcstól előre, a másik a célcsúcstól visszafelé. Amikor találkoznak, az algoritmus leáll. Ezt a technikát az indokolja, hogy sok esetben gyorsabb.

Andrew Goldberg és társai meghatározták a helyes leállási feltételeket a Dijkstra-algoritmusra vonatkozóan.

Akárcsak az A* algoritmus, a kétirányú keresés is vezérelhető a célcsúcsig (az előre mutató fában), illetve a kezdőcsúcsig (a hátrafelé mutató fában) hátralevő út heurisztikus becslésével.

Ira Pohl volt, aki 1971-ben először megtervezett és megvalósított egy kétirányú heurisztikus keresőalgoritmust. A kezdő, illetve a célcsúcsból induló keresőfák nem találkoztak a megoldási tér közepén. Champeaux 1977-ben javította ezt a hibát.

Az egyirányú A* algoritmus által megengedett heurisztikát használó megoldás legrövidebb úthosszal rendelkezik; ugyanez a tulajdonság érvényes a BHFFA2 kétirányú heurisztikus változata számára is, amelyet a de Champeaux ismertetett (1983). A BHFFA2 többek között gondosabb kimeneti feltételekkel rendelkezik, mint a BHFFA.

Leírás

A kétirányú heurisztikus keresés egy állapottér-keresés, ahol egy bizonyos $s$ állapotból egy másik $t$ állapotba kerül. Ez egyidejű kereséssel történik $s$-től $t$-ig és $t$-től $s$-ig. Egy érvényes operátor listával tér vissza, amelyeket $s$-re alkalmazva megkapjuk $t$-t.

Bár úgy tűnhet, hogy az operátoroknak a fordított kereséshez invertálhatónak kell lenniük, csak akkor szükséges, ha bármilyen $n$ csomópontra meg akarjuk találni $n$ szülőcsomópontjainak halmazát úgy, hogy minden szülő csomópontból létezzen néhány érvényes operátor $n$-hez. Ezt gyakran hasonlítják az útvonal-keresési területen egy egyirányú utcához: nem szükséges mindkét irányba haladni, de az utca végén állva meg kell határozni az utca kezdetét, mint lehetséges útvonalat.

Hasonlóképpen, az inverz ívekkel rendelkező élekhez (például az ívek minden irányba futnak) nem szükséges, hogy mindegyik irány azonos költségekkel járjon. A fordított keresés mindig az inverz költséget (például az ív költségét előre irányban) fogja használni. Formálisabban, ha $n$ egy csomópont egy $p$ szülővel, akkor $k_{1}(p,n)=k_{2}(n,p)$, amelyet úgy definiálnak, hogy „$p$-től $n$-ig terjedő költség” (Auer Kaindl 2004).

Terminológia és jelölések

$b$

a keresési fa elágazási tényezője.

$k(n,m)$

az $n$ csomópontból az $m$ csomópontba való mozgás költsége.

$g(n)$

a gyökér és az $n$ csomópont közötti költség.

$h(n)$

az $n$ csomópont és a cél közötti távolság heurisztikus becslése.

$s$

a kezdő állapot.

$t$

a cél állapota (néha $g$, nem összetévesztendő a függvénnyel).

$d$

az aktuális keresési irány. Megegyezés szerint a $d$ egyenlő 1-gyel előre irányban és 2-vel hátrafelé irányban (Kwa 1989).

$d'$

az ellenkező keresési irány (például $d'=3-d$).

$\mathrm {TREE} _{d}$

a keresési fa d irányban. Ha $d=1$, akkor a gyökér $s$, ha $d=2$, akkor a gyökér $t$.

$\mathrm {OPEN} _{d}$

a $\mathrm {TREE} _{d}$ levelei (néha $\mathrm {FRINGE} _{d}$ néven hivatkoznak rá). Ebből a készletből választunk ki egy csomópontot a bővítéshez. A kétirányú keresésben ezeket néha „határoknak” vagy „hullámfrontoknak” nevezzük, utalva arra, hogy miként jelennek meg, ha a keresést grafikusan ábrázoljuk. Ebben a metaforában egy „ütközés” akkor következik be, amikor a bővítési fázisban egy „hullámfront” csomópontjának utódai vannak az ellentétes „hullámfronton”.

$\mathrm {CLOSED} _{d}$

a $\mathrm {TREE} _{d}$ leveleket nem tartalmazó csomópontjai. Ez a halmaz tartalmazza a keresés által már érintett csomópontokat.

A kétirányú heurisztikus keresés megközelítései

A kétirányú algoritmusok nagyjából három kategóriába sorolhatók:

• Front-to-Front (elölről előre)
• Front-to-Back vagy Front-to-End (elölről hátra)
• kerületkeresés (Kaindl Kainz, 1997)

Ezek a heurisztika kiszámításához használt függvényben különböznek.

Front-to-Back (elölről hátra)

Az elölről hátra algoritmusok kiszámítják egy $n$ csomópont $h$ értékét az $n$ és az ellentétes keresési fa gyökéreleme, $s$ vagy $t$ közötti heurisztikus becslés felhasználásával.

Az elölről hátra a legaktívabban kutatott a három kategória között. A jelenleg legjobb algoritmus (legalábbis a Tizenöt kirakó tartományban) a BiMAX-BS*F algoritmus, amelyet Auer és Kaindl készített 2004-ben.

Front-to-Front (elölről előre)

Az elölről előre algoritmusok kiszámítják egy $n$ csomópont $h$ értékét az n és a $\mathrm {OPEN} _{d'}$ néhány részhalmaza közötti heurisztikus becslés felhasználásával. A kanonikus példa a BHFFA (kétirányú heurisztikus front-front algoritmus) példája, ahol a $h$ függvény az összes aktuális csomópont és az ellenkező fronton lévő csomópontok közötti összes heurisztikus becslés minimuma. Vagy formálisan:

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

ahol a $H(n,o)$ az $n$ és $o$ csomópontok közötti távolság megengedett (vagyis nem túlbecsült) heurisztikus becslését adja vissza.

Az elölről előre algoritmus túlzottan számításigényes. Minden alkalommal, amikor egy $n$ csomópont felkerül a nyílt listára, ki kell számítani annak $f=g+h$ értékét. Ez magában foglalja egy heurisztikus becslés kiszámítását $n$-től az összes szemben lévő $\mathrm {OPEN}$ halmaz csomópontjához, a fentebb leírtak szerint. Az $\mathrm {OPEN}$ halmazok nagysága exponenciálisan növekszik minden olyan tartomány esetében, ahol $b>1$.

Fordítás

Ez a szócikk részben vagy egészben a Bidirectional search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.