C/C++ & Visual C++

DatovΘ struktury a algoritmy (18.)

┌vodem  |  DatovΘ struktury |  Kurz DirectX  |  Downloads  |  Otßzky a odpov∞di

V minulΘm dφlu naÜeho serißlu jsme se podφvali na optimalizaci algoritm∙ prohledßvßnφ do Üφ°ky a do hloubky. Algoritmus prohledßvßnφ do Üφ°ky jsme vylepÜili rychlejÜφm vyhledßvßnφm v poli. U algoritm∙ pr∙chodu do hloubky jsme si probrali teorii, jak tyto algoritmy lze optimalizovat a dnes je na Φase podφvat se na implementaci n∞kter²ch t∞chto vylepÜenφ. P°eji p∞knΘ Φtenφ.

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

18.1.1. Prohledßvßnφ do hloubky

Minule jsme skonΦili tφm, ₧e heuristika je nßvodem pro postup v²poΦtu, zalo₧en² na n∞jakΘm pravidlu. Toto pravidlo musφme urΦit z charakteru ·lohy. Je d∙le₧itΘ si p°ipomenout, ₧e pou₧itφ heuristiky neznamenß nalezenφ nejoptimßln∞jÜφho °eÜenφ. My se vrßtφme k ji₧ jednou vy°eÜenΘ ·loze o pohybu kon∞ po Üachovnici, kdy k∙≥ mß za ·kol proskßkat vÜechna pole Üachovnice. Jen pro zajφmavost si uve∩me, ₧e tuto ·lohu formuloval znßm² matematik Euler p°ed vφce ne₧ 200 lety. My jsme v tΘto ·loze m∞li pevn∞ zadanΘ po°adφ mo₧n²ch tah∙, kterΘ jsme postupn∞ provßd∞li z danΘho pole. NaÜe heuristika bude spoΦφvat v tom, ₧e toto po°adφ budeme m∞nit. Pravidlo pro urΦenφ sm∞r∙ bude nßsledujφcφ: z poslednφho pole, kterΘ k∙≥ navÜtφvil, p∙jdeme nejprve na ta pole, ze kter²ch je mo₧nΘ pokraΦovat nejmΘn∞ zp∙soby. Uvidφme, ₧e p°idßnφ heuristiky nßm program ani moc nezm∞nφ, jen se rozÜφ°φ o dv∞ procedury. Jedna procedura bude mφt za ·kol zjistit, kolik je mo₧nostφ pohybu kon∞ z danΘho pole. Tuto hodnotu nßm pak funkce vrßtφ pomocφ nßvratovΘ hodnoty. Druhß procedura pak set°φdφ tahy podle heuristiky. Zde je implementace:

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

using namespace std;

#define SirkaPole 8
#define VyskaPole 8
#define MaxPocetTahu ((SirkaPole * VyskaPole) - 1)

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

TahKonem MozneTahy[8] = { {2, 1}, {1, 2}, {-1, 2}, {-2, 1},
{-2, -1}, {-1, -2}, {1, -2}, {2, -1} }; // osm moznych tahu konem

int Sachovnice[SirkaPole][VyskaPole];

void TiskSachovnice()
{
...
}

void VymazSachovnici()
{
...
}

int PocetMoznychTahu(int _PozX, int _PozY)
{
    int iPocet = 0;
    int NoveX, NoveY;

    for(int iTah = 0; iTah < 8; iTah++)
    {
        NoveX = _PozX + MozneTahy[iTah];
        NoveY = _PozY + MozneTahy[iTah];

        if((NoveX >= 0) && (NoveX < SirkaPole) && (NoveY >= 0) && (NoveY < VyskaPole))
        {
            // pole lezi uvnitr sachovnice, jeste overit, zda bylo navstiveno
            if(Sachovnice[NoveX][NoveY] == -1)
            {
                // nebylo jeste navstiveno - pripocteme si mozny tah
                iPocet++;
            }
        }
    }

    return iPocet;
}

void NastavTahy(int _PozX, int _PozY, int *_lpTahy, int *_lpPocetTahu)
{
    int iPocetMoznychTahu[8]; // moznych tahy z pole, index odpovida tahu
    int NoveX, NoveY;

    *_lpPocetTahu = 0;

    // najdeme vsechny tahy z dane pozice, ktere jsou proveditelne a najdeme k nim pocet
    // dosazitelnych poli
    for(int iTah = 0; iTah < 8; iTah++)
    {
        NoveX = _PozX + MozneTahy[iTah].dx;
        NoveY = _PozY + MozneTahy[iTah].dy;

        if((NoveX >= 0) && (NoveX < SirkaPole) && (NoveY >= 0) && (NoveY < VyskaPole))
        {
            // pole lezi uvnitr sachovnice, jeste overit, zda bylo navstiveno
            if(Sachovnice[NoveX][NoveY] == -1)
            {
                // nebylo jeste navstiveno
                _lpTahy[*_lpPocetTahu] = iTah; // ulozime si index tahu

                 // urcime si pocet tahu z pole
                iPocetMoznychTahu[*_lpPocetTahu] = PocetMoznychTahu(NoveX, NoveY);
                (*_lpPocetTahu)++; // pripocteme si mozny tah
            }
        }
    }

    // nyni uz jen setridime tahy podle poctu volnych tahu
    for(int i = 0; i < (*_lpPocetTahu) - 1; i++)
    {
        int k = i;
        for(int j = i + 1; j < (*_lpPocetTahu); j++)
        {
            if(iPocetMoznychTahu[j] < iPocetMoznychTahu[k])
            {
                k = j; // index nejmensiho pak bude j
            }
        }

        if(k > i)
        {
            // prohodime dva tahy i pocet tahu, aby si obe pole odpovidala
            int iVymena = iPocetMoznychTahu[k];
            iPocetMoznychTahu[k] = iPocetMoznychTahu[i];
            iPocetMoznychTahu[i] = iVymena;

            iVymena = _lpTahy[k];
            _lpTahy[k] = _lpTahy[i];
            _lpTahy[i] = iVymena;
        }
    }
}

Tato funkce tedy slou₧φ k urΦenφ po°adφ prochßzenφ tah∙. Nejprve si spoΦφtßme mo₧nΘ tahy z danΘho pole (_PozX, _PozY). Ulo₧φme si posloupnost mo₧n²ch tah∙ do pole _lpTahy, prvky pole jsou vlastn∞ indexy do pole MozneTahy. SouΦasn∞ si uklßdßme i poΦty tah∙, kterΘ je mo₧nΘ ud∞lat z t∞chto polφ - tedy polφ dostupn²ch z p∙vodnφho polφΦka urΦenΘho pozicφ (_PozX, _PozY). Pak u₧ nßm nezb²vß nic jinΘho, ne₧, ₧e tahy set°φdφme podle toho, kolik z nich je mo₧no ud∞lat dalÜφch tah∙. Musφme prohazovat slo₧ky obou polφ - jak tah∙, tak poΦt∙ mo₧n²ch tah∙. K set°φd∞nφ pole pou₧ijeme star² znßm² algoritmus t°φd∞nφ p°φm²m v²b∞rem. JeÜt∞ pozm∞n∞nß procedura UdelejTah():

void UdelejTah(int _iCislo, int _PozX, int _PozY, bool *_bTahOK)
{
    int iTah = 0;
    bool bTahOK = false;
    int NoveX, NoveY;
    int iPocetTahu; // urcuje pocet tahu nalezenych heuristikou
    int iMozneTahy[8]; // udava indexy tahu urcenych heuristikou do pole moznych tahu

    // urcime si posloupnost tahu heuristikou
    NastavTahy(_PozX, _PozY, iMozneTahy, &iPocetTahu);

    // a nalezene tahy provedeme
    while((iTah < iPocetTahu) && !bTahOK)
    {
        // indexujeme pomoci indexu v pole iMozneTahy
        NoveX = _PozX + MozneTahy[iMozneTahy[iTah]].dx;
        NoveY = _PozY + MozneTahy[iMozneTahy[iTah]].dy;
        iTah++; // priste zkusime dalsi tah

        // rovnou umistime na pole, tah je urcite proveditelny
        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;
        }
    };

    *_bTahOK = bTahOK; // vratime hodnotu pres parametr
}

V prvnφm vstupu do funkce UdelejTah() si nechßme urΦit posloupnost vhodn²ch tah∙ podle heuristiky. Vyu₧ijeme faktu, ₧e heuristika nßm vracφ pouze proveditelnΘ tahy a tak s klidem tahy provßdφme bez nutnosti ov∞°ovßnφ, zda na Üachovnici le₧φ, Φi jestli u₧ nßhodou nebyly navÜtφveny. Nynφ se podφvßme na rychlostnφ srovnßnφ algoritmu bez a s heuristikou. K≤d bude zakomentovan² ve zdrojov²ch souborech, zde si ho ukazovat nebudeme. VÜechen k≤d naleznete op∞t v sekci Downloads.