C/C++ & Visual C++
Datové struktury a algoritmy (14.)
Úvodem | Datové struktury | Kurz DirectX | Downloads | Otázky a odpovědi | 2001 | 2002 | 2003 | 2004
Minule jsme si ukázali metody, kterými lze navštívit každý uzel stromu, byly to metody preorder, inorder a také postorder. Všechny tyto metody procházely strom do hloubky. V dnešním pokračování se podíváme na průchod stromem do šířky. Teorie je velice pěkná věc, ale lepší jsou praktické ukázky využití průchodu stromem a tak se i my podíváme na dva příklady. Jeden bude dnes a na ten druhý se podíváme příště.
14.1. Průchod stromem do šířky
Opět se jedná o úlohu, kdy je naším cílem navštívit všechny uzly stromu. U metod, se kterými jsme se seznámili minule, jsme postupovali do hloubky, vyšli jsme z kořenu a procházeli jsme například jeho levým podstromem, až jsme se dostali k listům stromu. U průchodu do šířky procházíme jednotlivé hladiny stromu. Jako první tedy navštívíme opět kořen, poté se podíváme na všechny jeho následovníky a pokračujeme až opět až k listům. Navíc volíme směr zleva doprava.
U procházení do hloubky, tedy její nerekurzivní verze, jsme využili datové struktury zásobníku. Pro realizaci průchodu do šířky využijeme frontu, kterou opět přepíšeme do dynamické reprezentace, abychom mohli procházet libovolně rozsáhlé stromy. Nejprve vložíme do fronty uzel a při každém průchodu z fronty jeden uzel vyjmeme a zpracujeme ho. Poté vložíme do fronty následovníky, pokud nějaké má. Jestliže je následovníku více, pak je vložíme v pořadí zleva doprava. Funkčnost, jak jsme si ji popsali výše, pak zajistí již fronta. Nejprve si ukážeme implementaci fronty:
#ifndef CDYNFRONTA_H
#define CDYNFRONTA_H
template<class T> class CPrvek {
private:
T m_Data;
CPrvek<T> *m_lpDalsi;
public:
CPrvek() : m_lpDalsi(NULL) { }
CPrvek(const T& _Data) : m_Data(_Data), m_lpDalsi(NULL) { }
T VratData() const { return m_Data; }
CPrvek<T>* VratDalsi() const { return m_lpDalsi; }
void NastavDalsi(CPrvek<T> *_lpDalsi) { m_lpDalsi = _lpDalsi; }
void NastavData(const T& _Data) { m_Data = _Data; }
};
template<class T> class CDynFronta {
private:
CPrvek<T> *m_lpVrchol, *m_lpPosledni;
public:
CDynFronta() : m_lpVrchol(NULL), m_lpPosledni(NULL) { }
~CDynFronta() { if(!JePrazdna()) { SmazFrontu(); } }
void VytvorPrazdnou();
bool SmazFrontu();
bool JePrazdna() { return (m_lpVrchol == NULL); }
bool Vloz(const T& _Data); // vklada na konec seznamu
bool Vyjmi(T &_Vyber); // odebere prvni prvek
};
template<class T> void CDynFronta<T>::VytvorPrazdnou()
{
if(m_lpVrchol)
{
SmazFrontu();
}
m_lpVrchol = NULL;
m_lpPosledni = NULL;
}
template<class T> bool CDynFronta<T>::SmazFrontu()
{
bool bNavrat = false;
if(!JePrazdna())
{
CPrvek<T> *lpMazany;
while(m_lpVrchol)
{
lpMazany = m_lpVrchol;
m_lpVrchol = m_lpVrchol->VratDalsi(); // posun na dalsi prvek
delete lpMazany;
}
bNavrat = true;
}
return bNavrat;
}
template<class T> bool CDynFronta<T>::Vloz(const T& _Data)
{
bool bNavrat = false;
// jen vlozime prvek do fronty
CPrvek<T> *lpNovy = new CPrvek<T>(_Data);
if(lpNovy)
{
if(m_lpVrchol == NULL) // je to tedy prvni prvek
{
m_lpVrchol = lpNovy;
m_lpPosledni = lpNovy; // zacatek i konec jsou si rovny
}
else
{
m_lpPosledni->NastavDalsi(lpNovy);
m_lpPosledni = lpNovy; // zapojime na konec fronty
}
bNavrat = true;
}
// opet novy prvek nemazeme
return bNavrat;
}
template<class T> bool CDynFronta<T>::Vyjmi(T &_Vyber)
{
bool bNavrat = false;
if(!JePrazdna())
{
_Vyber = m_lpVrchol->VratData();
CPrvek<T> *lpMazany = m_lpVrchol;
m_lpVrchol = m_lpVrchol->VratDalsi(); // odebereme prvni prvek
delete lpMazany;
bNavrat = true;
}
return bNavrat;
}
#endif
Používáme ukazatel na konec i začátek fronty pro urychlení práce. Pokud bychom měli ukazatel jen na začátek, bylo by při každém vkládání nutné projít frontou prvků od začátku a nelézt poslední prvek.
Nyní si ukážeme metodu vykonávající průchod stromem do šířky:
template<class T> void CBinStrom<T>::PruchodStromem5()
{
typedef CUzel<T> LPTCUZEL;
CDynFronta<LPTCUZEL> Fronta;
if(!JePrazdny()) // overime, jestli ve stromu neco je
{
Fronta.Vloz(*m_lpKoren);
}
CUzel<T> Zpracovani;
while(!Fronta.JePrazdna())
{
if(Fronta.Vyjmi(Zpracovani))
{
cout << Zpracovani.VratData() << " ";
// ukladame zleva doprava
if(Zpracovani.VratLevy()) { Fronta.Vloz(*Zpracovani.VratLevy()); }
if(Zpracovani.VratPravy()) { Fronta.Vloz(*Zpracovani.VratPravy()); }
// mohly by nasledovat dalsi prvky u obecnych stromu
}
}
}
Přidal jsem podmínku pro ověření, zda-li je strom prázdný, jinak bychom ukládali do fronty nesmyslnou hodnotu a došlo by k vyvolání výjimky. V minulém dílu tato podmínka chyběla u nerekurzivního průchodu stromem do hloubky. Připomeneme si, jak náš strom vypadá a ukážeme si výstup programu po zavolání metody PruchodStromem5():
Výstup programu bude: 8, 5, 9, 4, 7, 13, 11.
Kód naleznete v sekci Downloads (projekt Strom).
14.2. Využití prohledávání do hloubky a do šířky
Ukážeme si dva příkládky na využití průchodu stromem, jeden bude využívat průchod do hloubky a druhý do šířky. Pokud budeme programovat například nějakou hru, pak se budeme na počátku nacházet v nějakém stavu. Různými přechody do dalších stavů se budeme snažit dojít až k řešení úlohy. Řešení úlohy může být jednoznačné nebo může být více stavů, které jsou řešením, úloha je pak mnohoznačná. Základními úlohami, které se uvádějí u průchodů jsou logické úlohy na šachovnici. Po každém provedeném tahu se nám naskýtá více možností na další tah, přičemž nikdy nevíme, a samozřejmě to nelze ani předem spočítat, jestli námi vybraný tah povede ke správnému řešení.
Jako první úlohu budeme řešit problém, jak koněm umístěným na libovolném místě šachovnice proskákat všechna pole, navíc budeme chtít, aby každé pole bylo navštíveno pouze jednou. Jako druhou úlohu si zvolíme nalezení nejkratší cesty koněm mezi dvěma libovolnými místy na šachovnici.
Nejprve si tedy povíme pravidla šachu. Kůň se pohybuje do tvaru písmene L, pohyb lze tedy vykonat o jedno pole v jednom směru a poté o dvě pole ve směru na něj kolmém. Dáma ohrožuje pole, která leží vlevo, vpravo, nahoře a dole od ní a navíc ještě pole na diagonálách.
Vrhněme se nyní na navržení datových struktur pro pohyby koněm. Pohyby koně, je jich celkem osm, uložíme do pole struktur. Tyto struktury budou obsahovat právě souřadnice možných skoků koněm. Vzhledem k tomu, že strom všech možných tahů koněm by byl velice rozsáhlý, budeme vytvářet průběžně s každým tahem. Tedy v paměti počítače se nikdy nebude vyskytovat kompletní strom.
Nyní si rozebereme příklady podrobněji a zvlášť a to v pořadí v jakém jsme si ukázali algoritmy průchodu.
14.2.1. Prohledávání do hloubky
Úloha o projití celého hracího pole koněm vede na průchod stromem do hloubky. Vrcholy stromu mají význam jednotlivých situací na herním poli. Jako kořen máme stav, kdy kůň stojí na určitém místě. V každém následujícím tahu máme podle pozice koně až osm možností, jak lze koněm táhnout. Menší počet možností bude jednak u míst která jsou blízko krajům šachovnice, ale s postupným procházením šachovnice i u vnitřních polí, abychom vyhověli podmínce o pouze jedné návštěvě políčka (a hned s prvním pohybem bude maximální počtu možných tahů jen 7). Situace, kdy kůň nemůže pokračovat, ať už proto, že dosáhl řešení úlohy nebo nemůže splnit pravidla pro pohyb v dalším kroku, jsou reprezentována listy pomyslného stromu.
Takže nejprve si vytvoříme strukturu pro tahy koněm a definujeme některé konstanty:
#define SirkaPole 8
#define VyskaPole 8
#define MaxPocetTahu ((SirkaPole * VyskaPole) - 1)
typedef struct {
int dx; // zmena v x
int dy; // zmena v y
} TahKonem;
// osm moznych tahu konem
TahKonem MozneTahy[8] = { {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1} };
Na pořadí tahů v poli možných tahů nezáleží, neboť řešení nalezneme ve všech případech. Ovšem některé kombinace mohou trvat velmi dlouho, protože v nepříznivých případech budeme muset projít velkou část pomyslného stromu.
Tahy koněm budeme provádět na šachovnici, definované jako pole celých čísel. Dále napíšeme metody pro tisk hracího pole a pro jeho inicializaci. Hodnota -1 bude znamenat, že pole ještě nebylo koněm navštíveno. Ostatní čísla znamenají, v kterém tahu kůň dané pole navštívil a číslovat začínáme od 0:
int Sachovnice[SirkaPole][VyskaPole];
void TiskSachovnice()
{
for(int i = 0; i < SirkaPole; i++)
{
for(int j = 0; j < VyskaPole; j++)
{
cout << setw(4) << Sachovnice[i][j];
}
cout << endl << endl;
}
}
void VymazSachovnici()
{
for(int i = 0; i < SirkaPole; i++)
{
for(int j = 0; j < VyskaPole; j++)
{
Sachovnice[i][j] = -1;
}
}
}
Nyní už k vlastní funkci, která bude provádět jednotlivé tahy. Jejími parametry budou číslo tahu, pozice koně a odkazem předávaná proměnná, která signalizuje, zda je cesta nalezena, nebo ne:
void UdelejTah(int _iCislo, int _PozX, int _PozY, bool *_bTahOK)
{
int iTah = 0;
bool bTahOK = false;
int NoveX, NoveY;
do
{
NoveX = _PozX + MozneTahy[iTah].dx;
NoveY = _PozY + MozneTahy[iTah].dy;
iTah++; // priste zkusime dalsi tah
if((NoveX >= 0) && (NoveX < SirkaPole) && (NoveY >= 0) && (NoveY < VyskaPole))
{
// jsme stale na sachovnici
if(Sachovnice[NoveX][NoveY] == -1)
{
// jeste jsme na tomto poli nebyli
Sachovnice[NoveX][NoveY] = _iCislo;
if(_iCislo < MaxPocetTahu) // pokud tah nebyl posledni, zkus dalsi
{
// zkusime dalsi tah
UdelejTah(_iCislo + 1, NoveX, NoveY, &bTahOK);
if(!bTahOK)
{
// pokud tah neni mozny, pak ho zrusime - nastavime na -1
Sachovnice[NoveX][NoveY] = -1;
}
}
else
{
bTahOK = true;
}
}
}
} while (!bTahOK && (iTah < 8));
*_bTahOK = bTahOK; // vratime hodnotu pres parametr
}
Funkce jednoduše provádí tahy podle pořadí v poli možných tahů. K původní pozici koně, která je předána jako parametr přičte pohyb koně. Pokud toto pole leží uvnitř šachovnice, tak tento tah provede. Posléze ověří, zda nebylo dosud provedeno šířka * výška zmenšená o 1 tahů, což by znamenalo, že celá šachovnice je obsazena. Pokud ne, zkusí udělat další tah. Přes parametr se vrátí hodnota true nebo false podle toho, zda tato posloupnost tahů vede k řešení. Jestli tomu tak není, pak jednoduše tah vrátíme nastavením políčka na -1 a přejdeme k dalšímu průchodu cyklem - zkusíme z pole možných tahů následující tah.
Funkce main() pak vypadá následovně:
int main(int argc, char* argv[])
{
int PozX, PozY;
cout << "Zadej x souradnici kone: ";
cin >> PozX;
cout << "Zadej y souradnici kone: ";
cin >> PozY;
if((PozX >= 0) && (PozX < SirkaPole) && (PozY >= 0) && (PozY < VyskaPole))
{
VymazSachovnici();
Sachovnice[PozX][PozY] = 0; // prvni pole
bool bOK;
UdelejTah(1, PozX, PozY, &bOK);
// pokud ma bOK hodnotu true, mame zaplnenou sachovnici tahy konem - staci ji vytisknout
if(bOK)
{
TiskSachovnice();
}
else
{
cout << "Cesta konem nebyla nalezena" << endl;
}
}
else
{
cout << endl << "Zadana pozice lezi mimo hraci pole" << endl;
}
char c;
cin >> c;
return 0;
}
Zeptáme se uživatele na pozici koně, velikost šachovnice se dá měnit jen pomocí konstant a tedy i následné rekompilace. Nebyl by však problém změnit statickou alokaci na dynamickou. Ověříme, zda pozice koně leží uvnitř šachovnice. Pokud ano, pak nastavíme první pole jako výchozí (dáme na něj 0). Poté už jen zavoláme výše popsanou rekurzivní metodu.
Kód naleznete v sekci Downloads (projekt PruchodKonem1).
14.3. Co bude příště
Jak jsme si slíbili v úvodu, v příštím dílu se podíváme na průchod stromem do šířky v podobě příkladu. Možná si ještě ukážeme jednu velice známou úlohu na průchod stromem do šířky. A pak budeme porovnávat oba algoritmy z hlediska použitelnosti. Těším se nashledanou u dalšího dílu.