..: 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∞