Претрага у дубину итеративним продубљивањем

Претрага у дубину итеративним продубљивањем (енгл. Iterative deepening depth-first search, ИДДФС) је стратегија претраге у којој се алгоритам Ограничене претраге у дубину узастопно употребљава повећавајући границу дубине са сваком наредном итерацијом док не достигне вредност $d$, дубину најближег циљног стања. ИДДФС је идентичан алгоритму претраге у ширину (БФС), али користи много мање меморије; сваком итерацијом чворови дрвета претраге су посећени истим редоследом као код претраге у дубину (ДФС), али је кумулативни редослед у којем су чворови први пут посећени као код БФС претраге.

Особине

ИДДФС комбинује просторну ефикасност ДФС алгоритма и комплетност БФС алгоритма (када је фактор гранања коначан). Оптимални резултати се добијају када је цена пута неопадајућа функција од дубине чвора. Просторна сложеност ИДДФС је $O(bd)$, где је $b$ фактор гранања, а $d$ је дубина најближег циља. Итеративним продубљивањем се иста стања посећују више пута, што се може учинити као велико расипање времена, али долази се до закључка да нас то и не кошта превише, пошто се у дрвету претраге већина чворова налази у доњем нивоу, тако да вишеструка посета вишим нивоима није претерано битна. .

Када се ради о дрвету игара (гаме трее) главна предност ИДДФС алгоритма је то што се у ранијој фази претраге тежи побољшању уобичајено коришћених хеуристика, као што су киллер хеуристиц и алфа-бета одсецање (алпха-бета прунинг), тако да се може доћи до прецизније претпоставке резултата различитих чворова при крајњој претрази у дубину. Такође претрага се извршава брже пошто је урађена у бољем редоследу. На пример алгоритам алфа-бета одсецања је најефикаснији уколико прво тражи најбоље могуће потезе.

Друга предност овог алгоритма огледа се у његовом одзиву. С обзиром да почетне итерације користе мале вредности за $d$, извршавају се изузетно брзо. Ово омогућава алгоритму да достави ране претпоставке о резултату скоро тренутно, које постају све прецизније како се $d$ повећава. Када се користи у итеративној поставци, као на пример у програму за шах, ова особина омогућава програму да у било ком тренутку одигра тренутно најбољи досада пронађени потез. Ово се може формулисати на следећи начин. Сваки ниво претраге корекурзивно (цорецурсивелy) даје бољу апроксимацију решења, иако се у сваком кораку сав посао одвија рекурзивно. Ово није могуће постићи класичним ДФС алгоритмом, који не пружа моменталне резултате. Временска сложеност ИДДФС алгоритма у добро уређеном дрвету је иста као код ДФС алгоритма $O(b^{d})$.

Приликом претраге итеративним продубљивањем, чворови на доњем нивоу су проширени (проширити – погледати децу чвора) једном, они на следећем нивоу два пута и тако све до корена дрвета претраге које је проширено $d+1$ пута. . Укупан број проширивања при претрази итеративним продубљивањем је

$(d+1)1+(d)b+(d-1)b^{2}+\cdots +3b^{d-2}+2b^{d-1}+b^{d}$

$\sum _{i=0}^{d}(d+1-i)b^{i}$

Фор $b=10$ анд $d=5$ тхе нумбер ис

6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

Свеукупно, претрага итеративним продубљивањем од нивоа 1 до нивоа $d$ проширује само око 11% више чворова него БФС, са фактором гранања 1, или ограничена претрага у дубину до нивоа $d$, када је $b=10$. Чак и када је фактор гранања 2, претрага итеративним продубљивањем, траје само два пута дуже од потпуне БФС претраге. Ово значи да је временска сложеност ИДДФС алгоритма и даље $O(b^{d})$, а просторна $O(d)$ као код обичног ДФС алгоритма. Генерално гледано,ИДДФС би увек требало да буде први избор, када се врше велике претраге и када нам дубина на којој се налази наше решење није позната.

Пример

За следећи граф:

ДФС алгоритам креће из чвора А. Претпоставимо да се прво посећују леве гране чворова, као и то да претрага памти претходно посећене чворове тако да их неће поново посећивати (пошто је у питању мали граф). Резултат претраге ће изгледати овако: А, Б, D, Ф, Е, C, Г. Уколико извршимо исту претрагу без памћења претходно посећених чворова резултат је следећи: А, Б, D, Ф, Е, А, Б, D, Ф, Е…итд, дакле добијамо петљу А, Б, D, Ф, Е због које никада нећемо посетити чворове C и Г.

Претрага итеративним продубљивањем спречава настајање ове петље па ће чворови, уколико важи претпоставка да се прво посећују леве гране па онда десне, бити посећени у следећем редоследу:

• 0: А
• 1: А (поновљено), Б, C, Е

(Приметимо да се итеративним продубљивањем сада дошло до чвора C, док обичним ДСФ-ом није.)

• 2: А, Б, D, Ф, C, Г, Е, Ф

(Приметимо да и даље можемо видети C али се оно појављује касније, такође можемо видети да се до чвора Е сада долази другачијом путањом)

• 3: А, Б, D, Ф, Е, C, Г, Е, Ф, Б

Алгоритам

Следећи псеудокод представља ИДДФС алгоритам имплементиран помоћу рекурзивног алгоритма Ограничене претраге у дубину (дептх-лимитед сеарцх, ДЛС)

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}

Алгоритам Ограничене претраге у дубину се може рекурзивно имплементирати на следећи начин. Приметите да се провера да ли је нађен циљни чвор врши само када је depth == 0, јер када је depth > 0, ДЛС проверава чворове које је посетио у претходним итерацијама ИДДФС-а.

DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth > 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return null
}

Сродни алгоритми

Сличан ИДДФС алгоритму је алгоритам претраге итеративним продужавањем, који ради са границама цене пута уместо са границама дубине претраге као ИДДФС. Он обилази чворове у таквом редоследу да цена путање расте, па је зато први циљни чвор на који се наиђе онај са најјефтинијом путањом. Када се пореде ова два алгоритма долази се до закључка да је ИДДФС ефикаснији од претраге итеративним продужавањем. .