Iteratívan mélyülő mélységi keresés

A számítástechnikában az iteratívan mélyülő keresés (IDA) vagy pontosabban az iteratívan mélyülő mélységi keresés (IDDFS) egy állapottér/gráf keresési stratégia, amely a mélységi keresés egy mélységkorlátozott verziója, melyben ismételten fut végig a gráf elemein egyre nagyobb mélységben, amíg meg nem találja a keresett elemet. Az IDDFS optimális, akárcsak a szélességi keresés, de sokkal kevesebb memóriát használ; minden iterációban az adott mélységben azonos módon járja be a gráf csúcsait, mint a mélységi keresés, de kumulált sorrendben a csúcsokat valójában a szélességi keresés sorrendjében látogatja meg először.

Algoritmus irányított gráfokra

A következő pszeudokód az iteratívan mélyülő mélységi keresést (IDDFS) mutatja be egy irányított gráfon alkalmazott rekurzív mélységkorlátozott mélységi keresés (DLS) szempontjából. Az IDDFS ezen megvalósítása nem veszi figyelembe a már meglátogatott csúcsokat, ezért nem működik irányítatlan gráfokon.

function IDDFS(root) is 
    for depth from 0 to ∞ do 
        found, remaining ← DLS(root, depth)
        if found ≠ null then
            return found
        else if not remaining then
            return null

function DLS(node, depth) is
    if depth = 0 then
        if node is a goal then
            return(node, true)
        else
            return (null, true)  (Nem találtuk meg, de még lehet gyerekeleme)

    else if depth > 0 then
        any_remaining ← false
        foreach child of node do
            found, remaining ← DLS(child, depth−1)
            if found ≠ null then
                return (found, true)
            if remaining then
                any_remaining ← true  (Legalább egy csúcsot találtunk az adott mélységben, ezért hagyjuk az IDDFS-t tovább dolgozni)
        return (null, any_remaining)

Ha megtaláljuk a keresett csúcsot, akkor a DLS megállítja a rekurziót és visszaadja, hogy nem kell több iteráció. Különben, ha van akár egy elem is azon abban a mélységben, akkor a remaining változó engedi az IDDFS függvényt tovább futni.

A rendezett kettesek hasznosak, mint visszatérési értékek, mert ezzel vezérelhetjük az IDDFS-t, hogy folytassa a mélyítést, vagy álljon meg, abban az esetben, ha nem tudjuk, hogy a keresett elem milyen mélységben található. Másik megoldásként használhatunk egy megkülönböztetett értéket, ami jelezni tudja, hogy nem találtuk meg a keresett értéket, vagy visszaadja a hátralévő csúcsokat.

Tulajdonságok

Az IDDFS egyesíti a mélységi keresés tárhatékonyságát és a szélességi keresés teljességét (ha véges számú él indul csak csúcsokból). Ha létezik megoldás, akkor a legrövidebb utat adja vissza (legkevesebb éllel rendelkező utat).

Mivel iteratív mélyítésnél a csúcsokat többször is érintjük, pazarlásnak tűnhet az ilyen módon történő bejárás, de mivel a legtöbb csúcs a fa legalsó szintjén található, ezért a fentebbi szinteken lévő csúcsok érintése nagyságrendileg nem számít túl sokat.

Az IDDFS fő előnye a játék fa alapú keresésekben, hogy a keresés eleje hajlamos javítani a gyakran használt heurisztikus algoritmusokat - pl. a gyilkos lépés heurisztikáját vagy az alfa-béta vágást - így az egyes ágakra egy pontosabb becslést tud adni és a keresés korábban befejeződik, mert összességében jobb sorrendben dolgozzuk fel a fát. Például az alfa-béta vágás akkor a leghatékonyabb csak, ha elsőre a legjobb lépést vizsgálja.

A második előnye, hogy az algoritmus gyorsan reagál, mert a kezdeti iterálásoknál kis $d$ (mélység) -t használ, és ezeket extrém gyorsan tudja kiszámolni. Ez lehetővé teszi az algoritmus számára, hogy a keresés már a futás korai stádiumában, szinte azonnal jó irányba induljon, és $d$ növekedésével ez csak egyre pontosabbá válik. Interaktív környezetben, például sakkjátszó programban történő alkalmazás esetén ez a képesség lehetővé teszi a program számára, hogy bármikor elvégezhessen egy lépést, az addig a pillanatig elvégzett keresés aktuálisan legjobbnak ítélt lépéssel. Ezt megfogalmazhatjuk úgy is, hogy a keresés minden mélységnél egyre pontosabb választ ad corekurzív (a rekurzió ellentéte) módon, habár minden egyes lépésén belül egyébként rekurzívan jár el. A hagyományos mélységi keresés erre nem képes, nem tud bármely pillanatban eredményt adni.

Aszimptotikus elemzés

Időbonyolultság

Az IDDFS időbonyolultsága egy (kiegyensúlyozott) fában megegyezik a szélességi keresésével, azaz $O(b^{d})$, ahol $b$ az elágazási tényező és $d$ pedig a keresett érték mélysége.

Bizonyítás

Egy iteratívan mélyülő keresésben a csomópontok adott $d$ mélységben 1-szer ágazik el , $d-1$ pedig kétszer ágazik el, és így tovább egészen a keresési fa gyökeréig, ami $d+1$-szer ágazik el. Így az elágazások száma összesen egy iteratív mélységi keresésben:

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

ahol $b^{d}$ az elágazások száma $d$ mélységen, $2b^{d-1}$ az elágazások száma $d-1$ mélységen és így tovább. Abban az esetben, ha kiemelünk $b^{d}$-t, akkor a következő képletet kapjuk:

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

Most nézzük meg, mi történik, ha $x={\frac {1}{b}}=b^{-1}$ Így most a képletünk a következőképpen alakul:

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

Ez kevesebb, mint a végtelen sorozat

$b^{d}(1+2x+3x^{2}+4x^{3}+\cdots )=b^{d}\left(\sum _{n=1}^{\infty }nx^{n-1}\right)$

amely képlet a következőhöz konvergál

$b^{d}(1-x)^{-2}=b^{d}{\frac {1}{(1-x)^{2}}}$, ha $abs(x)<1$

Vagyis, ahova eljutottunk az a következő:

$b^{d}(1+2x+3x^{2}+\cdots +(d-1)x^{d-2}+dx^{d-1}+(d+1)x^{d})\leq b^{d}(1-x)^{-2}$, ha $abs(x)<1$

Mióta tudjuk, hogy $(1-x)^{-2}$ vagy $\left(1-{\frac {1}{b}}\right)^{-2}$ biztosan egy konstans, amely független $d$-től (mélység), ha $b>1$(azaz, ha az elágazási tényező nagyobb mint 1), az iteratív mélységi keresés futási ideje $O(b^{d})$.

Példa

Amennyiben $b=10$ és $d=5$ a számunk az alábbi lesz:

$\sum _{i=0}^{5}(5+1-i)10^{i}=6+50+400+3000+20000+100000=123456$

Mindent összevetve, egy iteratív mélységi keresés az 1-es mélységből lefelé haladva egészen $d$ mélységig csak körülbelül $11\%$-al több csúcs elágazást tesz (ennyivel több csúcsot vizsgál) mint egy sima szélességi keresésben vagy mint egy mélységében limitált keresésben $d$ mélységig, amennyiben $b=10$.

Minél nagyobb az elágazási tényező, annál kevesebbszer kell vizsgálni a "helytelen" utakat (vagyis ezeket gyorsan ki tudjuk zárni), de még akkor is, ha az elágazási tényező az 2, az iteratív mélységi keresés csupán kétszer olyan hosszú ideig tart, mint egy teljes szélességi keresés. Ez azt jelenti, hogy az időbonyolultsága az iteratív mélyítésnek továbbra is $O(b^{d})$ lesz.

Tárbonyolultság

Az IDDFS tárbonyolultsága $O(d)$ ahol $d$ a keresett elem mélysége.

Bizonyítás

Mivel az IDDFS bármely pillanatban egy mélységi keresést végez el, csak egy csúcspont ágat kell tárolnia egyszerre, amely ágat éppen vizsgál. Mivel biztosan megtalálja a keresett elemet a fában, jelen esetben a maximum mélysége $d$ lesz, ennélfogva a maximum tárigénye $O(d)$ lesz.

Általánosságban, az iteratív mélyítés az előnyben részesített keresési módszer, amennyiben nagy keresési tárhelyünk van és a keresett elem mélysége nem ismert.

Példa

Vegyük példának a következő gráfot:

egy mélységi keresésben, amely A csúccsal kezdődik, feltételezve, hogy a fent látható gráf bal oldali éleit előbb választjuk ki, mint a jobb oldaliakat, továbbá feltételezve azt, hogy a keresés képes megjegyezni a korábban már meglátogatott csúcsokat, és nem vizsgálja őket többször (mivel a képen egy igazán kis gráf látható), a következő sorrendben fogja vizsgálni a csúcsokat: A, B, D, F, E, C, G. Az élek, amelyik ezt a gráfot alkotják egy Trémaux fát formáznak, mely egy nagyon fontos struktúrája a gráfelméletnek.

Ugyanezt a keresést végrehajtva, anélkül, hogy képesek lennénk emlékezni a korábban meglátogatott csúcsokra, a következő csúcs-látogatási sorrendet kapjuk: A, B, D, F, E, A, B, D, F, E, stb... egy végtelen folyamat, az A, B, D, F, E ciklus soha nem éri el a C-t vagy a G-t, így visszaemlékezés nélkül ez az iteráció örökké tartana.

Az iteratív mélyítés megakadályozza ezt a végtelen hurkot és el fogja érni a következő csúcsokat a megadott mélységeken, feltételezve, hogy balról-jobbra haladunk, ahogy fentebb is tárgyaltuk:

• 0: A
• 1: A, B, C, E

(Az iteratív mélyítés most már látja a C csúcsot, ezzel ellentétben a hagyományos mélységi keresés nem látja soha a végtelen ciklus miatt.)

• 2: A, B, D, F, C, G, E, F

(Ez a lépés-sorozat továbbra is látja a C csúcsot, habár később mint az előbbi, de látja. Valamint eléri még az E csúcsot is, egy különböző útvonalon, és vissza iterál F-hez kétszer is.)

• 3: A, B, D, F, E, C, G, E, F, B

Fent ábrázolt gráfunk esetében minél több mélységet adunk hozzá, a két ciklusunk: "ABFE" és "AEFB" útvonalak egyszerűen tovább fognak tartani, mielőtt az alogritmusunk feladja a harcot és megpróbál egy másik ágon elindulni.

Kapcsolódó algoritmusok

Van egy, az iteratív mélyülő mélységi kereshez hasonló keresési stratégia, amelyet iteratív hosszabbító keresésnek hívunk, amely növekvő él-súlyozási limitekkel dolgozik mélységi limitek helyett. Ez a keresés a súlyok növekedő sorrendjében vizsgálja az ágakat; ebből kifolyólag az első célcsúcs amellyel találkozik, az a legolcsóbb útvonalon lesz megtalálható. Az iteratív hosszabbító keresés azonban jelentősen költségesebb, ezért kevésbé használható, mint az iteratív mélyítés.

Az iteratív mélyítés A* algoritmus algoritmus egy "legjobbat először" módszerrel valósít meg iteratív mélységi keresést 'f' értékeken alapulva - hasonlóan az A* algoritmusban használt 'f' értékekhez.

 Kétirányú IDDFS

Az IDDFS-nek van egy kétirányú párja, amely két keresés között váltogat: az egyik a gyökértől indul és halad az éleken át a célcsúcs fele, a másik pedig a célcsúcstól indulva halad az éleken az ellentétes irányba (vagyis a gyökér fele). A keresési folyamat először megnézi, hogy a gyökér és a célcsúcs megegyeznek-e egymással, és ha igen, akkor visszatér egy egyetlen csúcsból álló triviális útvonallal (a gyökér és egyben célcsúccsal). Ellenkező esetben az előre felé haladó keresés összeköti a gyökér elemet a hozzá köthető gyermek csúcsokkal ($A$ felállás), a visszafelé haladó keresés pedig kibővíti a célcsúcsot a szülőcsúcsaival ($B$ felállás), majd ellenőriz és megvizsgálja, hogy $A$-nak és $B$-nek van-e közös csúcsa. Amennyiben igen, megtaláltuk a legrövidebb utat. Máskülönben az útvonalak tovább terjeszkednek és az algoritmus folytatódik.

Az algoritmusnak az egyik korlátozása, hogy azok a legrövidebb utak, amelyek páratlan számú élből állnak, nem lesznek észlelve. Tegyük fel, hogy megtaláltuk a legrövidebb utat $\langle s,u,v,t\rangle .$ Amennyiben a mélységünk elér a második ugráshoz, az élek mentén, az előrehaladó keresés folytatni fogja $v$-hez $u$-tól. A visszafelé haladó keresés pedig $v$-től $u$-hoz. Vagyis a keresési határok keresztül mennek egymáson, és inkább egy olyan úton halad tovább, amely szuboptimális,(nem megfelelő, vártnál rosszabb eredményű) és páros számok találhatóak meg az ívei mentén. Ez az alábbi diagramon van ábrázolva:

Kétirányú IDDFS

Ami a tárbonyolultságot illeti, az algoritmus a legmélyebb csúcspontokat megjelölheti az előrefelé haladó keresési folyamatban annak érdekében, hogy felismerje, ha egy középső csúcs a két keresési procedúra között találkozna.

További nehézsége a kétirányú IDDFS alkalmazásának az, hogy ha a forrás és a célcsúcs nem összefüggő gráfot alkotnak, pl. $s\in S,t\in T$ , és nincsen olyan él, amely elhagyja $S$-et és belelép $T$-be, a keresésnek soha nem lesz vége.

 Idő és tárbonyolultságok

A kétirányú IDDFs futási ideje a következő képlettel adható meg:

$2\sum _{k=0}^{n/2}b^{k}$

és a tárbonyolultság pedig az alábbival fejezhető ki:

$b^{n/2},$

ahol $n$ a csúcsok száma a legrövidebb $s,t$ útvonalon. Mivel az iteratív mélységi keresés futási időbonyolultsága $\sum _{k=0}^{n}b^{k}$-al fejezhető ki, a gyorsítás nagyjából a következő:

${\frac {\sum _{k=0}^{n}b^{k}}{2\sum _{k=0}^{n/2}b^{k}}}={\frac {\frac {1-b^{n+1}}{1-b}}{2{\frac {1-b^{n/2+1}}{1-b}}}}={\frac {1-b^{n+1}}{2(1-b^{n/2+1})}}={\frac {b^{n+1}-1}{2(b^{n/2+1}-1)}}\approx {\frac {b^{n+1}}{2b^{n/2+1}}}=\Theta (b^{n/2}).$

Pszeudokód

function Build-Path(s, μ, B) is
    π ← Find-Shortest-Path(s, μ) (Recursively compute the path to the relay node)
    remove the last node from π
    return π $\circ$ B (Append the backward search stack)

function Depth-Limited-Search-Forward(u, Δ, F) is
    if Δ = 0 then
        F ← F $\cup$ {u} (Mark the node)
        return
    foreach child of u do
        Depth-Limited-Search-Forward(child, Δ − 1, F)

function Depth-Limited-Search-Backward(u, Δ, B, F) is
    prepend u to B
    if Δ = 0 then
        if u in F  then
            return u (Reached the marked node, use it as a relay node)
        remove the head node of B
        return null
    foreach parent of u do
        μ ← Depth-Limited-Search-Backward(parent, Δ − 1, B, F)
        if μ $\neq$ null then
            return μ
    remove the head node of B
    return null

function Find-Shortest-Path(s, t) is
   if s = t then
       return <s>
   F, B, Δ ← ∅, ∅, 0
   forever do
       Depth-Limited-Search-Forward(s, Δ, F)
       foreach δ = Δ, Δ + 1 do
           μ ← Depth-Limited-Search-Backward(t, δ, B, F)
           if μ $\neq$ null then
               return Build-Path(s, μ, B) (Found a relay node)
           B ← ∅
       F, Δ ← ∅, Δ + 1

Fordítás

Ez a szócikk részben vagy egészben az Iterative deepening depth-first 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.