..: C/C++ & Visual C++ :..

Vítejte u dalšího dílu seriálu o datových strukturách. V posledním pokračování jsme si teoreticky probrali průchod stromem do šířky a přešli jsme k praktické ukázce využití dříve probraného průchodu do hloubky. Dnes si ukážeme příklad s tématikou průchodu do šířky. Problém bude opět vycházet z šachového prostředí.

15.1. Využití prohledávání do hloubky a do šířky

15.1.1. Prohledávání do šířky

Problémem pro prohledávání do šířky pro nás bude úloha nalézt na šachovnici nejkratší cestu mezi dvěma poli pomocí koně. V tomto případě opět použijeme maticové reprezentace šachovnice, kde si na každé políčko uložíme hodnotu, která bude určovat v kterém tahu koněm jsme se na toto pole dostali. Na políčku prvním, z kterého začínáme, tedy bude 0. Na všech polích, na která je možno se dostat jedním tahem koně uložíme 1. V dalším kroku pak bereme všechna pole na kterých je hodnota 1 a z nich skáčeme na pole, která mají vzdálenost 1 tahu koněm od tohoto pole a na kterých jsme dosud nebyli. Tato pole budou mít hodnotu 2 atd. Na pole, která už byla dosažena v prvním tahu nemá cenu skákat, neboť bychom jen prodlužovali cestu a nalezená cesta by tedy nebyla nejkratší. Skákání po šachovnici končí okamžikem, kdy dosáhneme cílového pole. Hodnota na tomto poli pak udává, kolik bylo zapotřebí tahů k dosažení tohoto pole.

Je vidět, že při poskakování si budeme muset uchovávat pole, do kterých jsme se tahem dostali, ale dále jsme z nich nepokračovali. V naší ukázce tato pole budeme hledat průchodem pole podle hodnot. Je to nejjednodušší řešení tohoto problému, neboť není třeba využívat jiných datových struktur. Ukážeme si tedy algoritmus pro nalezení cesty:

void NajdiCestu(int _PozX, int _PozY, int _CilX, int _CilY)
{
    int iCislo = 1; // kolikaty tah konem se pokousime udelat
    int NoveX, NoveY;
    int iTah = 0; // tahy konem

    Sachovnice[_PozX][_PozY] = 0; // prvni pole

    // dokud jsme nenavstivili pole na sachovnici
    while(Sachovnice[_CilX][_CilY] == - 1)
    {
        for(int i = 0; i < SirkaPole; i++)
            for(int j = 0; j < VyskaPole; j++)
            {
                // najdeme pole, na ktera jsme se dostali v minulych tazich
                if(Sachovnice[i][j] == (iCislo - 1))
                {
                    // udelame vsechny mozne tahy z tohoto pole
                    for(iTah = 0; iTah < 8; iTah++)
                    {
                        NoveX = i + MozneTahy[iTah].dx;
                        NoveY = j + MozneTahy[iTah].dy;

                        // pokud je pole stale na sachovnici
                        if((NoveX >= 0)&&(NoveX < SirkaPole)&&(NoveY >= 0)&&(NoveY < VyskaPole))
                        {
                            if(Sachovnice[NoveX][NoveY] == -1)
                            {
                                // jeste jsme na tomto poli nebyli, tak si ho oznacime
                                Sachovnice[NoveX][NoveY] = iCislo;
                            }
                        }
                    }
                }
            }

        iCislo++; // delame dalsi tah
    }
}

Tímto tedy máme v poli Sachovnice nalezenou cestu, pokud si pole necháme vypsat můžeme si ji jednoduše prstem nalézt. My bychom ji však chtěli v posloupnosti polí, která je nutno projít k dosažení cíle. K tomu použijeme techniku zpětného průchodu, kdy vyjdeme z cílového pole a budeme hledat cestu k poli výchozímu. Je jasné, že v okolí cílového pole musí být na dosah nějakého tahu koněm pole, které bude mít hodnotu o jedna nižší než pole cílové. Toto pole si vybereme a stejnou metodou budeme hledat pole s hodnotou o jedna nižší. Pokud se podíváme na výsledky hledání cesty pro šachovnici 4x4, uvidíme následující obrázek:

0	3	2	5
3	4	1	2
2	1	4	3
5	2	3	2

Zeleně je označeno pole výchozí, červeně pak pole cílové. Vidíme, že v okolí cílového pole na dosah jednoho tahu koně leží dvě pole s hodnotou čtyři. Protože však hledáme libovolnou nejkratší cestu, pak je nám jedno, které pole si vybereme. Následuje algoritmus zpětného průchodu, který vypíše posloupnost polí navštívených koněm od cílového pole k výchozímu:

void ZpetnyPruchod(int _PozX, int _PozY, int _CilX, int _CilY)
{
    int X, NoveX;
    int Y, NoveY;
    int iTah;

    X = _CilX;
    Y = _CilY;

    while((X != _PozX) || (Y != _PozY))
    {
        iTah = 0;

        do {
            NoveX = X + MozneTahy[iTah].dx;
            NoveY = Y + MozneTahy[iTah].dy;

            // pokud je pole stale na sachovnici
            if((NoveX >= 0) && (NoveX < SirkaPole) && (NoveY >= 0) && (NoveY < VyskaPole))
            {
                if(Sachovnice[NoveX][NoveY] == Sachovnice[X][Y] - 1)
                {
                    // pokud se na pole da dostat jednim tahem, tak se na nej presuneme
                    X = NoveX;
                    Y = NoveY;

                    cout << "Jdi na pole: (" << NoveX << " ; " << NoveY << ")" << endl;
                    iTah = 0;
                }
                else
                {
                    iTah++; // zkus dalsi tah konem
                }
            }
            else
            {
                // pokud je pole mimo sachovnici, tak zkus opet dalsi tah
                iTah++;
            }
        } while(iTah != 0);
    }

    cout << endl;
}

Ve funkci main() se zeptáme na výchozí a cílový bod pohybu koně. Ověříme, zda tato pole opravdu leží uvnitř šachovnice a pak provedeme nalezení cesty. Předpokládáme, že úloha je zadána správně. Např. na šachovnici 3x3 nemusí jít cesta nalézt, od rozměru 4x4 je vše v pořádku.

15.2. Co bude příště

V příštím dílu si srovnáme oba typy průchodů stromem, neboť se oba nehodí na libovolnou činnost. Pokusíme se zoptimalizovat průchod do hloubky heuristikou. A určitě ještě něco navíc. Těším se příště nashledanou.

C/C++ & Visual C++

Datové struktury a algoritmy (15.)

15.1. Využití prohledávání do hloubky a do šířky

15.1.1. Prohledávání do šířky

15.2. Co bude příště