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:
| - | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | -1 | -2 | -3 | -4 |
| 1 | 1 | 0 | -1 | -2 | -3 |
| 2 | 2 | 1 | 0 | -1 | -2 |
| 3 | 3 | 2 | 1 | 0 | -1 |
| 4 | 4 | 3 | 2 | 1 | 0 |
Diagonála na které odčítáme indexy (tedy ve směru "\")
| - | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 2 | 3 | 4 | 5 | 6 |
| 3 | 3 | 4 | 5 | 6 | 7 |
| 4 | 4 | 5 | 6 | 7 | 8 |
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 2N. 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 763! 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.