Двосмерно претраживање

Двосмерна претрага је алгоритам за претрагу графа који проналази најкраћи пут од почетног до крајњег чвора графа. Извршава две истовремене претраге: једна од почетног чвора, друга од крајњег чвора графа и алгоритам прекида са радом када се ове две претраге нађу на средини графа. Разлог због кога се приступа на овај начин је што је у већини случајева претрага бржа: нпр, у поједностављеном моделу проблема сложености претраге, у оба случаја претраге проширује стабло издавајући фактор б, а растојање од почетног до крајњег чвора графа д, обе ове претраге имају сложеност О(б^д/2), и временска сложеност ове две претраге је мања од сложености О(б^д) која представља резултат претраге од почетка до краја графа.

Као у алгоритму претраге А*, двосмерна претрага може бити предвођена истраживачком проценом преосталог пута до краја графа или до почетка графа.

Ира Похл је прва дизајнирала и имплементирала двострани претраживачки алгоритам. Ендру Голдберг је дао објашњење тачне границе могућег коришћења верзије двосмерне претраге Дијкстра алгоритма.

Опис

Двосмерно претраживање је облик просторног претраживања од места $s$ до места $t$, претраживајући од $s$ до $t$ и од $t$ до $s$ истовремено. Овај алгоритам враћа важећи списак путева који ако се примени на $s$, долази се до $t$.

Иако се чини да претрага мора бити инверзна за обрнуту претрагу, у ствари је само неопходно пронаћи било који дат чвор $n$, и чвор $n$ мора имати валидну операцију за сваког од његових родитеља. Ово представља једносмерну улицу у избору налажења домена: није неопходно да се иде у оба правца, али је неопходно када се надјемо на крају графа, да знамо могућу путању до почетка графа.

Обрнута претрага ће увек захтевати инверзне троскове. Формалније, ако је чвор $n$ са родитељем $p$, онда $k_{1}(p,n)=k_{2}(n,p)$, дефинише цену од $p$ до $n$.

Терминологија и нотација

$b$

издвојени фактор претраге стабла

$k(n,m)$

цена пута од чвора $n$ до чвора $m$

$g(n)$

цена пута од чвора до $n$

$h(n)$

истраживање процене пута од чвора $n$ до краја графа

$s$

почетно место

$t$

крајње место (понекад се обележава и са $g$)

$d$

тренутни смер претраге, $d=1$ за правилан смер, а за уназад је $d=2$.

$d'$

обрнути смер претраге, $d'=3-d$.

$TREE_{d}$

претрага стабла у правцу $d$

$OPEN_{d}$

лишће стабла $TREE_{d}$

$CLOSED_{d}$

чворови стабла $TREE_{d}$ који имају потомке, овај сет садржи чворове који су већ претражени.

Приступ двосмерном претраживању

Двосмерни претраживачи се могу сврстати у три категорије: Front-to-Front, Front-to-Back, и Обимна претрага. Разликују се по функцији коју користе за истраживање.

Фронт-то-Бацк

Фронт-то-Бацк алгоритам израчунава вредност $h$ чвора $n$ користећи процену измедју $n$ и корена супротне претраге стабла, $s$ или $t$.

Фронт-то-Бацк алгоритам је највише истраживан од све три категорије. Тренутни најбољи алгоритам је БиМАX-БС*Ф алгоритам.

Фронт-то-Фронт

Фронт-то-Фронт алгоритам израчунава вредност $h$ чвора $n$ користећи раздаљину измедју чвора $n$ и подскуп $OPEN_{d}'$. Прави пример би био БХФФА (Двосмерна претрага Фронт-то-Фронт алгоритмом), где је функција $h$ дефинисана као минимум истраживачких процена између тренутног чвора и њему супротним чворовима. Формално:

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

где $H(n,o)$ враћа прихватљиву истраживачку процену о дистанци између чворова $n$ и $o$.

Фронт-то-Фронт пати од тога да буде претерано рачунски захтеван. У сваком тренутку када се чвор $n$ стави у отворену листу, његова вредност мора бити израчуната као $f=g+h$. Ово укључује израчунавање процене од чвора $n$ до свих чворова који се налазе у $OPEN$ сет-у. $OPEN$ сет се експоненцијално повећава за све области у којима је $b>1$.

Референце

• де Цхампеауx, Деннис; Синт, Ление (1977), „Ан импровед бидирецтионал хеуристиц сеарцх алгоритхм”, Јоурнал оф тхе АЦМ, 24 (2): 177—191, дои:10.1145/322003.322004 .
• де Цхампеауx, Деннис (1983), „Бидирецтионал хеуристиц сеарцх агаин”, Јоурнал оф тхе АЦМ, 30 (1): 22—32, дои:10.1145/322358.322360 .
• Похл, Ира (1971), „Би-дирецтионал Сеарцх”, Ур.: Мелтзер, Бернард; Мицхие, Доналд, Мацхине Интеллигенце, 6, Единбургх Университy Пресс, стр. 127—140 .
• Русселл, Стуарт Ј.; Норвиг, Петер (2002), „3.4 Унинформед сеарцх стратегиес”, Артифициал Интеллигенце: А Модерн Аппроацх (2нд изд.), Прентице Халл .