C/C++ & Visual C++

DatovΘ struktury a algoritmy (17.)

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

Vφtejte u dalÜφho dφlu o datov²ch strukturßch, v p°edchozφch dφlech jsme si povφdali o problematice pr∙chodu datovΘ struktury typu strom do hloubky a do Üφ°ky. V poslednφch dvou dφlech jsme si uvedli n∞kterΘ p°φklady a takΘ jsme porovnali tyto dva algoritmy. Dnes se budeme v∞novat optimalizaci t∞chto algoritm∙. P°eji p°φjemnΘ Φtenφ.

17.1. Optimalizace prohledßvßnφ do Üφ°ky a do hloubky

17.1.1. Prohledßvßnφ do Üφ°ky

P°edminule jsme se v∞novali ·loze nalezenφ nejkratÜφ cesty kon∞m mezi dv∞ma poli na Üachovnici. K tomu jsme pou₧ili pr∙chod do Üφ°ky, vhodn² pro ·lohy s menÜφm poΦtem tah∙ vedoucφch k °eÜenφ. Implementovali jsme jednoduchou verzi, kterß pro malß pole vyhovala. Pro pole v∞tÜφch rozm∞r∙ by pak snesla n∞jakΘ to urychlenφ. Dv∞ma hlavnφmi zpomalenφmi v²poΦtu bylo vyhledßvßnφ polφ ze kter²ch je t°eba jeÜt∞ pokraΦovat a druh²m pak prohledßnφ Üachovnice pro vytiÜt∞nφ cesty. Nynφ si tedy algoritmus vylepÜφme.

ProblΘm s poli, ze kter²ch je t°eba dßle skßkat vy°eÜφme pomocφ fronty, kterou jsme ji₧ n∞kolikrßt programovali. Druh² problΘm vy°eÜφme tak, ₧e si ke ka₧dΘmu polφΦku budeme zapisovat jeho p°edch∙dce. Bude tedy muset existovat dvourozm∞rnΘ pole o velikosti Üachovnice, jeho₧ elementy budou sou°adnice. To podle pravidla: za v∞tÜφ rychlost musφme ob∞tovat trochu vφce pam∞ti. Nßsleduje implementace, ukß₧eme si delÜφ v²pis, abychom vid∞li, co se vÜe zm∞nilo:

#include "stdafx.h"
#include <iostream>
#include <iomanip>

#include "DynFronta.h"

using namespace std;

#define SirkaPole 4
#define VyskaPole 4

struct TahKonem {
    int dx; // zmena v x
    int dy; // zmena v y

    TahKonem() { ; }
    TahKonem(int _dx, int _dy) : dx(_dx), dy(_dy) { ; }
    void Nastav(int _dx, int _dy) { dx = _dx; dy = _dy; }
};

TahKonem MozneTahy[8] = { TahKonem(2, 1), TahKonem(1, 2), TahKonem(-1, 2), TahKonem(-2, 1),
TahKonem(-2, -1), TahKonem(-1, -2), TahKonem(1, -2), TahKonem(2, -1) }; // mozne tahy konem

int Sachovnice[SirkaPole][VyskaPole];
TahKonem Predchudci[SirkaPole][VyskaPole]; // predchudci poli

void TiskSachovnice()
{
    ...
}

void VymazSachovnici()
{
    ...
}

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

    // zacneme v cili
    X = _CilX;
    Y = _CilY;

    while((X != _PozX) || (Y != _PozY))
    {
        // a pomoci predchudcu si najdeme cestu
        NoveX = Predchudci[X][Y].dx;
        NoveY = Predchudci[X][Y].dy;

        X = NoveX;
        Y = NoveY;

        cout << "Jdi na pole: (" << NoveX << " ; " << NoveY << ")" << endl;
    }

    cout << endl;
}

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

    CDynFronta<TahKonem> Neprozkoumane;

    Sachovnice[_PozX][_PozY] = iCislo; // prvni pole znulujeme
    Neprozkoumane.Vloz(TahKonem(_PozX, _PozY)); // a vlozime do fronty

    TahKonem Zkoumany; // zkoumany tah

    // dokud jsme nenavstivili pole na sachovnici
    while(Sachovnice[_CilX][_CilY] == - 1)
    {
        // vezmeme si pole z fronty
        if(!Neprozkoumane.JePrazdna())
        {
            Neprozkoumane.Vyjmi(Zkoumany);

            iCislo = Sachovnice[Zkoumany.dx][Zkoumany.dy] + 1; // delame dalsi tah v poradi

            // udelame vsechny mozne tahy z tohoto pole
            for(iTah = 0; iTah < 8; iTah++)
            {
                NoveX = Zkoumany.dx + MozneTahy[iTah].dx;
                NoveY = Zkoumany.dy + 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 dalsim cislem
                        Sachovnice[NoveX][NoveY] = iCislo;
                        // pridame si ho ke zkoumani do fronty
                        Neprozkoumane.Vloz(TahKonem(NoveX, NoveY));
                        // a navic si ulozime predchudce tohoto pole pro zpetny pruchod
                        Predchudci[NoveX][NoveY].Nastav(Zkoumany.dx, Zkoumany.dy);
                    }
                }
            }
        }
    }

    // mame nalezenou cestu -> udelame zpetny pruchod
    ZpetnyPruchod(_PozX, _PozY, _CilX, _CilY);
}

K≤d k p°φkladu naleznete v sekci Downloads (projekt KunSirka2).

V k≤du jsme navφc pov²Üili strukturu TahKonem na strukturu stejnΘho jmΘna, ale p°idali jsme jφ navφc i metody pro prßci s datov²mi slo₧kami a konstruktorem. Ulo₧φme si tedy v²chozφ pole do fronty, to je p°i prvnφm vstupu do cyklu while vybrßno a z n∞ho skßΦeme na vÜechna mo₧nß polφΦka, kterß nßm pravidla dovolujφ. Tato pole si ulo₧φme do fronty Neprozkoumane a postupn∞ z nich skßΦeme dßle. Navφc poka₧dΘ nastavujeme p°edch∙dce danΘho polφΦka.

Vidφme, ₧e algoritmus zp∞tnΘho pr∙chodu se velice zjednoduÜil. Vlastn∞ u₧ ani nejde o zp∞tn² pr∙chod, ale jen o indexovßnφ pole. V²sledky dostßvßme stejnΘ jako v p∙vodnφm algoritmu. Cesta je takΘ zobrazena v opaΦnΘm po°adφ - tedy od cφle k v²chozφmu poli.

17.1.2. Prohledßvßnφ do hloubky

Jak jsme ji₧ zmφnili v minulΘm dφlu, backtracking, neboli prohledßvßnφ do hloubky se vyznaΦuje znaΦnou Φasovou nßroΦnostφ. Ta je v∞tÜinou exponencißlnφ a tedy Φinφ tyto algoritmy Φasto nepou₧iteln²mi. N∞kdy se ovÜem p°esto musφme pomocφ backtrackingu dobrat °eÜenφ a tak se sna₧φme tyto algoritmy alespo≥ co nejlΘpe zoptimalizovat. Jsou v podstat∞ dv∞ mo₧nosti:

• o°ezßvßnφ

• heuristika

O°ezßvßnφ spoΦφvß v tom, ₧e pokud v n∞jakΘm bodu v²poΦtu vφme, ₧e danß v∞tev nem∙₧e vΘst k °eÜenφ, tak ji prost∞ z kompletnφho stromu problΘmu od°φzneme. To znamenß, ₧e uÜet°φme prochßzenφ vÜech stav∙ le₧φcφch pod tφmto bodem. Algoritmu to oznßmφme stejn∞, jako by doÜel do koneΦnΘho stavu, tedy do n∞kterΘho listu, kter² nenφ °eÜenφm ·lohy.

Druhou mo₧nostφ je heuristika. Uve∩me si nejprve p°φklad: mßme t°i lidi a t°i r∙znΘ prßce, ka₧d² Φlov∞k d∞lß r∙znou prßci za rozdφlnΘ ceny. K jednΘ prßci lze p°i°adit pouze jednoho Φlov∞ka a ka₧d² by m∞l mφt svou prßci. Cenu nßm udßvß nßsledujφcφ tabulka (sloupce urΦujφ prßci, °ßdky pak lidi):

Jednou mo₧nou heuristikou by bylo vybrat nßhodn∞ Φlov∞ka a p°i°adit mu op∞t nßhodn∞ vybranou prßci. Tφm pßdem ovÜem v∙bec nevyu₧φvßme informace, kterΘ jsme dostali z tabulky. Jinou heuristikou by bylo vybrat z tabulky nejmenÜφ cenu a p°id∞lit podle toho k sob∞ Φlov∞ka a prßci a dßle se zab²vat redukovan²m problΘmem. Je jasnΘ, ₧e druhΘ °eÜenφ, kterΘ p°eci jen bere v ·vahu data ·lohy, bude lepÜφ. Zmφn∞nß ·loha se naz²vß problΘmem p°id∞lenφ. Vidφme, ₧e heuristika je vlastn∞ nßvodem, kter² by m∞l vΘst k rychlejÜφm· nalezenφ °eÜenφ.

Definice heuristiky by mohla znφt i nßsledovn∞: zjednoduÜenφ, pop°. odhad, kter² sni₧uje nebo omezuje hledßnφ °eÜenφ ve slo₧it²ch ·lohßch. Narozdφl od algoritm∙ vÜak heuristika nezaruΦuje optimßlnφ, n∞kdy vÜak ani rozumnΘ, °eÜenφ a Φasto se pou₧φvß bez teoretickΘ zßruky.

Pokud °eÜφme ·lohu, sna₧φme se heuristiku pou₧φt tak, abychom naÜφm algoritmem prochßzeli prßv∞ ty cesty, o kter²ch si myslφme, ₧e povedou rychleji k °eÜenφ. Jak vφme, backtracking prochßzφ vÜechna °eÜenφ, ovÜem v "nßhodnΘm" po°adφ. My tedy toto po°adφ budeme ovliv≥ovat, ale ₧ßdnΘ cesty nesmφme vynechat, jinak bychom se takΘ °eÜenφ nemuseli doΦkat. Pokud ·loha °eÜenφ nemß, nemßme samoz°ejm∞ ₧ßdnou Üanci s heuristikou usp∞t. Stejn∞ tak tomu je v p°φpad∞, kdy pot°ebujeme vÜechna °eÜenφ danΘ ·lohy. V obou posledn∞ zmφn∞n²ch p°φkladech toti₧ budeme muset nezbytn∞ projφt vÜechny v∞tve stromu ·lohy.

P°φkladem na prvnφ metodu - o°ezßvßnφ - m∙₧e b²t uveden tzv. magick² Φtverec. Ten nab²vß podobu matice o velikosti N x N a oznaΦuje se jako Φtverec °ßdu N. Jeden mo₧n² tvar je nßsledujφcφ:

Co je na takovΘ sm∞si Φφsel magickΘho? Krom∞ toho, ₧e obsahuje Φφsla od 1 do N² , kterß se neopakujφ, po pozorn∞jÜφm prozkoumßnφ jednotliv²ch °ßdk∙, sloupc∙ a dokonce hlavnφch diagonßl uvidφte, ₧e souΦet Φφsel v nich je roven jednomu Φφslu. V p°φpad∞ tohoto Φtverce je to 34.

NaÜφm ·kolem by m∞lo b²t sestrojit prßv∞ takov²to magick² Φtverec. Pokud bychom se na tuto ·lohu vrhli jednoduch²m backtrackingem, tak bychom se pro v∞tÜφ Φtverce asi °eÜenφ nedoΦkali. Algoritmus by toti₧ zkouÜel strkat do prvnφho °ßdku Φφsla 1, 2, 3, 4, pak by zkusil 1, 2, 3, 5. To samoz°ejm∞ za p°edpokladu, ₧e jdeme na ·lohu systematicky, ale jinak to ostatn∞ asi ani nejde. Nßm vÜak staΦφ ·vaha, ₧e v ka₧dΘm °ßdku/sloupci p°eci musφ b²t stejn² souΦet. SouΦet vÜech Φφsel v tabulce je aritmetickou °adou, pokud si tedy vzpomeneme na vzoreΦek ze Ükoly, N² * (N² + 1) / 2 dostßvßme pro naÜφ matici souΦet 136. A proto₧e se tento souΦet musφ rozd∞lit mezi °ßdky/sloupce, staΦφ ho vyd∞lit N a dostßvßme souΦet 34. Pro magick² Φtverec °ßdu 3 pak dostßvßme 15. Algoritmus by tedy vypadal tak, ₧e polo₧φme kompletnφ prvnφ °ßdek, ud∞lßme jeho souΦet a pokud nebude roven naÜemu souΦtu, ihned zkusφme jinou kombinaci Φφsel. Tφm se vyhneme zbyteΦnΘmu umφs¥ovßnφ dalÜφch °ßdk∙.

P°φkladem na metodu druhou je nalezenφ cesty mezi dv∞ma poli na Üachovnici kon∞m, se kterou jsme se ji₧ setkali. V tΘto ·loze jsme m∞li urΦeno po°adφ zkoumßnφ cest pomocφ inicializace mo₧n²ch tah∙ kon∞m na poΦßtku programu. Heuristika, kterou bychom v tomto p°φpad∞ pou₧ili, bude mφt za ·kol toto po°adφ promφchat. Toto promφchßnφ bude pouze na zßklad∞ n∞jakΘho naÜeho odhadu. JedinΘ, co se v p°φpad∞ hledßnφ libovolnΘ cesty m∙₧e zm∞nit je rychlost v²poΦtu a to jak pozitivn∞, tak negativn∞. Jinak nßm toti₧ navφc heuristika m∙₧e vrßtit jinou cestu ne₧-li by vrßtil algoritmus backtrackingu bez heuristiky.

17.2. Co bude p°φÜt∞

P°φÜt∞ se podφvßme na implementace algoritm∙ a ud∞lßme si rychlostnφ srovnßnφ optimalizovan²ch a neoptimalizovan²ch algoritm∙ prohledßvßnφ do hloubky.

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