Szerkesztő:BotlikRoland/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ás 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

A következő grafikonhoz:

Irodalomjegyzék

[[Kategória:Gráfalgoritmusok]]