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.