C/C++ & Visual C++

DatovΘ struktury a algoritmy (16.)

┌vodem  |  DatovΘ struktury |  Visual Studio .NET  |  Downloads  |  Otßzky a odpov∞di

V dneÜnφm dφlu naÜeho serißlu si ukß₧eme jeÜt∞ jeden p°φklad na pr∙chod stromem do hloubky, op∞t se budeme pohybovat na Üachovnici. Pak si srovnßme prohledßvßnφ do hloubky a do Üφ°ky.

16.1. Vyu₧itφ prohledßvßnφ do hloubky a do Üφ°ky

16.1.1. Prohledßvßnφ do hloubky

Na tento problΘm jsme si u₧ jeden p°φklßdek ukßzali, ale byla by Ükoda neuvΘst si jeÜt∞ jeden velice znßm² problΘm, kter² napadl kolem roku 1850 matematika K.F. Gausse. NßÜ ·kol nynφ stojφ takto: na Üachovnici dan²ch rozm∞r∙  mßme umφstit prßv∞ tolik dam, kolik je na Üachovnici sloupc∙. Tedy nap°. na Üachovnici o velikosti 4x4 mßme umφstit 4 dßmy. Samoz°ejm∞ ne libovoln∞, n²br₧ tak, aby se neohro₧ovaly. Dßma na polφΦku ohro₧uje vÜechna pole v horizontßlnφ i vertikßlnφ p°φmce prolo₧enΘ jejφ pozicφ a navφc i pole na diagonßlßch. Tedy jedno z mo₧n²ch °eÜenφ ·lohy pro Üachovnici 4x4 vypadß graficky nßsledovn∞:

Pokud se rozhodnete zkusit vy°eÜit si ·lohu na Üachovnici, pak m∙₧ete postupovat t°eba nßsledovn∞: umφstφte prvnφ dßmu do prvnφho sloupce, pak umφstφte dalÜφ do druhΘho sloupce tak, aby neohro₧ovala prvnφ. A do ka₧dΘho dalÜφho sloupce pak umφstφte dßmu tak, aby neohro₧ovala ₧ßdnou p°edchozφ. Jestli₧e se dostanete do situace, kdy nenφ mo₧nΘ dalÜφ dßmu umφstit a stßle nemßte °eÜenφ, pak je nutnΘ p°emφstit p°edchozφ. Jak jist∞ vidφte, tak je to prohledßvßnφ vÜech mo₧nostφ umφst∞nφ dam. A funkce, kterß bude °eÜit tuto ·lohu bude nepochybn∞ rekurzivnφ.

V p°φkladu s kon∞m na Üachovnici jsme m∞li datovou strukturu pro hracφ pole, v tomto p°φpad∞ by takΘ bylo mo₧nΘ reprezentovat hracφ pole dvourozm∞rn²m polem. P°i umφst∞nφ dßmy bychom pak prohledßvali diagonßly, pop°. do jednotliv²ch prvk∙ pole umφs¥ovali urΦitou hodnotu, ₧e pole je ohro₧eno. My si vÜak prßci ulehΦφme a budeme pracovat s jednorozm∞rn²mi poli. Prvnφ pole bude urΦovat obsazenφ °ßdku ve sloupci dßmou. DalÜφ dv∞ pole budou pro diagonßly. StaΦφ si toti₧ vÜimnout, ₧e pozice na diagonßlßch veden²ch zprava doleva (ve sm∞ru "/") majφ stejn² souΦet index∙ x a y. Pro diagonßlu opaΦnou, tedy vedenou zleva doprava (sm∞r "\"), je pak shodn² rozdφl index∙. To by nßm tedy dßvalo rozsah index∙ od 2 do 16 pro prvnφ diagonßlu a rozsah od -7 do 7 pro diagonßlu druhou, tedy alespo≥ pro p°φpad Üachovnice 8x8 s poΦφtßnφm od 1 do 8. Ideßlnφ implementace pro jazyk Pascal, kde meze polφ mohou b²t libovolnß Φφsla. My to ud∞lßme podle nßsledujφcφ ukßzky:

Zde indexy sΦφtßme (sm∞r "/")

V prvnφ tabulce nßm indexy b∞hajφ od -4 do 4, v druhΘm p°φpad∞ pak od 0 do 8. èachovnice mß rozm∞r 5x5. Velikost pole se tedy bude °φdit podle vzorce (N-1)*2 + 1. Implementace algoritmu bude vypadat nßsledovn∞:

void Umisti(int _iSloupec, bool *_bOK)
{
    bool bOK;
    bool bDalsiOK;

    *_bOK = false;

    for(int iRadek = 0; iRadek < N; iRadek++)
    {
        if(*_bOK) break;

        bOK = true;
        bDalsiOK = false;

        // overime, zda jiz v nejakem predchozim sloupci neni dama na stejnem radku
        for(int i = 0; i < _iSloupec; i++)
        {
            if(arPozice[i] == iRadek)
            {
                bOK = false;
                break;
            }
        }

        if((bOK) && (!arDiag1[iRadek - _iSloupec + N - 1]) && (!arDiag2[iRadek + _iSloupec]))
        {
            // pozice je bezpecna => umistime damu
            arPozice[_iSloupec] = iRadek;
            arDiag1[iRadek - _iSloupec + N - 1] = true;
            arDiag2[iRadek + _iSloupec] = true;

            // a pokusime se umistit dalsi damu, pokud to ma jeste smysl
            if(_iSloupec < N - 1)
            {
                Umisti(_iSloupec + 1, &bDalsiOK);

                if(!bDalsiOK)
                {
                    // pokud nelze provest dalsi tah, odstranime damu
                    arPozice[_iSloupec] = -1;
                    arDiag1[iRadek - _iSloupec + N - 1] = false;
                    arDiag2[iRadek + _iSloupec] = false;

                    *_bOK = false;
                }
                else
                {
                    *_bOK = true;
                }
            }
            else
            {
                // sem se dostaneme v pripade, ze jsme v poslednim sloupci
                *_bOK = true;
            }
        }
    }
}

Tφmto algoritmem dostaneme prvnφ nalezenΘ °eÜenφ problΘmu osmi dam. Pokud bychom cht∞li nalΘzt vÜechna °eÜenφ, staΦφ upravit k≤d nßsledovn∞:

void Umisti(int _iSloupec, bool *_bOK)
{
    bool bOK;
    bool bDalsiOK;

    *_bOK = false;

    for(int iRadek = 0; iRadek < N; iRadek++)
    {
        if(*_bOK) break;

        bOK = true;
        bDalsiOK = false;

        // overime, zda jiz v nejakem predchozim sloupci neni dama na stejnem radku
        for(int i = 0; i < _iSloupec; i++)
        {
            if(arPozice[i] == iRadek)
            {
                bOK = false;
                break;
            }
        }

        if((bOK) && (!arDiag1[iRadek - _iSloupec + N - 1]) && (!arDiag2[iRadek + _iSloupec]))
        {
            // pozice je bezpecna => umistime damu
            arPozice[_iSloupec] = iRadek;
            arDiag1[iRadek - _iSloupec + N - 1] = true;
            arDiag2[iRadek + _iSloupec] = true;

            // a pokusime se umistit dalsi damu
            if(_iSloupec < N - 1)
            {
                Umisti(_iSloupec + 1, &bDalsiOK);

                if(!bDalsiOK)
                {
                    // pokud nelze provest dalsi tah, odstranime damu
                    arPozice[_iSloupec] = -1;
                    arDiag1[iRadek - _iSloupec + N - 1] = false;
                    arDiag2[iRadek + _iSloupec] = false;

                    *_bOK = false;
                }
                else
                {
                    *_bOK = true;
                }
            }
            else
            {
                // sem se dostaneme v pripade, ze jsme v poslednim sloupci
                cout << "RESENI: " << iCount++ << endl;
                for(int i = 0; i < N; i++)
                {
                    cout << arPozice[i] << " ";
                }

                cout << endl;

                arPozice[_iSloupec] = -1;
                arDiag1[iRadek - _iSloupec + N - 1] = false;
                arDiag2[iRadek + _iSloupec] = false;

                *_bOK = false;
            }
        }
    }
}

Jen zm∞nφme k≤d tak, ₧e p°i ka₧dΘm dosa₧enφ poslednφho sloupce vytiskneme °eÜenφ. PotΘ dßmu op∞t odebereme a oznßmφme, ₧e poslednφ tah byl Üpatn². Algoritmus se tak bude sna₧it nalΘzt dalÜφ °eÜenφ a tedy skonΦφ, a₧ projde ·pln∞ vÜechny mo₧nosti. V reßlnΘm p°φpad∞ by samoz°ejm∞ bylo lepÜφ, kdybychom si °eÜenφ uklßdali do pole pro pozd∞jÜφ zpracovßnφ. Uve∩me, ₧e pro Üachovnici 8x8 mß ·loha osmi dam 92 °eÜenφ. NejmenÜφ Üachovnice, pro kterou je ·loha °eÜitelnß, mß rozm∞r 4x4.

K≤d k ob∞ma p°φklad∙m naleznete v sekci Downloads (projekt Damy, resp. Damy2).

16.2. Srovnßnφ algoritm∙ pr∙chodu stromem do Üφ°ky a do hloubky

Kdy₧ jsme se seznßmili s ob∞ma pr∙chody stromem a ukßzali si ke ka₧dΘmu n∞jakΘ p°φklady, je na Φase podφvat se na to, jakΘ jsou vlastnosti t∞chto algoritm∙.  V obou p°φpadech jde o zkoumßnφ stromu, kter² je slo₧en ze vÜech posloupnostφ tah∙, kterΘ jsou mo₧nΘ. Strom je vytvo°en jen za b∞hu, generujφ se v podstat∞ jen jeho Φßsti, strom toti₧ m∙₧e b²t velice rozsßhl².

Prohledßvßnφ do hloubky, anglicky oznaΦovanΘ jako backtracking se vyznaΦuje tφm, ₧e postupn∞ prochßzφme vÜechny mo₧nΘ tahy a₧ do tΘ doby, dokud nenφ nalezeno °eÜenφ nebo skonΦφme v pozici, kdy u₧ nenφ podle nßmi definovan²ch pravidel mo₧n² dalÜφ tah. Vezmeme nejvyÜÜφ uzel a z n∞ho pak sledujeme cestu a₧ k °eÜenφ -  tedy k list∙m stromu. Pokud si vezmeme p°φklad, kdy bychom m∞li strom o v²Üce N pater a v ka₧dΘm uzlu bychom m∞li mo₧nost volby jen pouh²ch dvou °eÜenφ, bude mφt prostor vÜech tah∙ na poli rozm∞r 2^N. V ·lohßch, kter²mi jsme se zab²vali my to pak je mnohem vφce, nebo¥ v ka₧dΘm kroku mßme mo₧n²ch tah∙ vφce. V p°φpad∞ pr∙chodu do hloubky p°i snaze projφt vÜechna pole Üachovnice nßm pak listy stromu le₧φ a₧ v hloubce 64. Pokud si uv∞domφme, ₧e v prvnφm tahu mßme v nejhorÜφm p°φpad∞ 8 mo₧nostφ jak kon∞m tßhnout a v dalÜφch pak 7, lze °φci, ₧e velikost prostoru vÜech tah∙ bude zhruba 7⁶³! Tyto ·lohy jsou tedy pak charakteristickΘ svou vysokou Φasovou slo₧itostφ (°ßdov∞ exponencißlnφ), vhodnost vyu₧itφ ΦistΘho backtrackingu je tedy prakticky omezena jen na ·lohy s mal²m poΦtem stav∙. V p°φÜtφm dφlu si ukß₧eme, jak algoritmus trochu zrychlit.

Druhou metodou pak je prohledßvßnφ do Üφ°ky, kterΘ se Üφ°φ po hladinßch stromu. Pokud se podφvßme na algoritmus nalezenφ nejkratÜφ cesty mezi dv∞ma zadan²mi poli, vidφme, ₧e z bodu se Üφ°φ jakoby vlna, kterß obklopφ p∙vodnφ bod. Z t∞chto bod∙ se pak Üφ°φ dalÜφ vlny. Proto se tento algoritmus takΘ n∞kdy naz²vß algoritmem vlny. P°edstavme si, ₧e bychom metodu pr∙chodu pou₧ili na n∞kterou z ·loh, kterΘ jsme °eÜili pomocφ pr∙chodu do hloubky. Te∩ mßm na mysli zrovna ty, jejich₧ °eÜenφ se nachßzφ v hloubce 64 tah∙, pak bychom se °eÜenφ asi nedoΦkali. Vφme toti₧, ₧e musφme v₧dy evidovat vrcholy z nich₧ chceme dßle pokraΦovat, co₧ by vedlo k obrovsk²m nßrok∙m na pam∞¥. Toto prohledßvßnφ je tedy vhodnΘ pro ·lohy, jejich₧ °eÜenφ nenφ schovßno a₧ n∞kde na dn∞ obrovskΘho stromu. V p°φpad∞ kon∞ hledajφcφho cestu vidφme, ₧e na Üachovnici 8x8 se °eÜenφ dß nalΘzt maximßln∞ 6 tahy. Velikou v²hodou tohoto algoritmu je takΘ to, ₧e nalezenΘ °eÜenφ je nejkratÜφm dostupn²m °eÜenφm, co₧ se samoz°ejm∞ hodφ i v p°φpad∞, ₧e to p°φmo od ·lohy nepo₧adujeme.

Backtracking tedy jednoduÜe zkoumß v jednu chvφli jednu konkrΘtnφ cestu, kde₧to algoritmus pr∙chodu do Üφ°ky se sna₧φ zkoumat souΦasn∞ vÜechny cesty vedoucφ z n∞jakΘho stavu sm∞rem k cφli. Na prvnφ ·lohu o pr∙chodu celΘho pole bychom pr∙chod do Üφ°ky nemohli pou₧φt, skonΦili bychom na nedostatku pam∞ti. OvÜem backtracking by bylo mo₧nΘ pou₧φt na ·lohu nalezenφ nejkratÜφ cesty, ale problΘmem by bylo, ₧e bychom museli projφt vÜechny cesty, ulo₧it si je s jejich dΘlkou do n∞jakΘ struktury a potΘ ze vÜech t∞chto mo₧n²ch cest vybrat tu nejkratÜφ.

┌pln² pr∙chod prostorem vÜech tah∙ (stavov²m prostorem) ovÜem nenφ mo₧n², nap°. hra Üach∙ mß strom koneΦn², avÜak tento strom je velice rozsßhl², nebo¥ po ka₧dΘm tahu lze provΘst zhruba 38 r∙zn²ch tah∙, co₧ vede na to, ₧e z ka₧dΘho vrcholu stromu vede dalÜφch 38 hran k vrchol∙m.

16.3. Co bude p°φÜt∞

V p°φÜtφm dφlu budeme optimalizovat algoritmy pr∙chodu pomocφ heuristik, budeme se v∞novat n∞kter²m vlastnostem strom∙.

T∞Üφm se p°φÜt∞ nashledanou.