![]() |
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 hloubky18.1.1. Prohledßvßnφ do hloubkyMinule 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" void NastavTahy(int _PozX, int _PozY, int *_lpTahy, int
*_lpPocetTahu) 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) 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.
M∞°enφ byla provedena na Intel PIII/1133 MHz, 512 MB RAM, vÜechna m∞°enφ byla provßd∞na z polφΦka Üachovnice o sou°adnici (1,1). Pro m∞°enφ pou₧φvßme funkci GetTickCount(), kterou lze najφt v hlaviΦkovΘm souboru windows.h.Vidφme, ₧e heuristika nßm p°inesla podstatnΘ zrychlenφ v²poΦtu. U Üachovnice 8x8 na °eÜenφ nemusφme Φekat p°i volb∞ libovolnΘho pole. V p°φpad∞ neoptimalizovanΘ implementace se °eÜenφ doΦkßme u n∞kter²ch polφ b∞hem n∞kolika vte°in, ale u v∞tÜiny je to v °ßdu hodin. Tato heuristika nenφ pro problΘm obsazenφ celΘ Üachovnice jedinou mo₧nostφ. Jin²m p°φstupem je Warnsdorrf∙v algoritmus. Dnes se budeme krßtce v∞novat teorii skrytΘ za tφmto algoritmem a zaΦneme tabulkou znßzor≥ujφcφ Üachovnici:
╚φsla v jednotliv²ch polφch urΦujφ, z kolika polφ je danΘ pole dostupnΘ. Kon∞m pak pohybujeme tak, ₧e se sna₧φme nejprve projφt p°es nejmΘn∞ dostupnß pole. Z tabulky je vid∞t, ₧e nejmΘn∞ dostupn²mi jsou pole v rozφch a proto se je sna₧φme projφt jako prvnφ. Poka₧dΘ, kdy₧ tßhneme kon∞m, snφ₧φme o 1 hodnoty ve vÜech polφch, kterß jsou z tohoto pole dostupnß. 18.2. Co bude p°φÜt∞P°φÜt∞ se podφvßme na implementaci Warnsdorffova algoritmu a dostaneme se k vlastnostem strom∙. Serißl bude dßle pokraΦovat informacemi o datov²ch strukturßch naz²van²ch grafy. TakΘ se budeme v∞novat jeÜt∞ jednomu vyu₧itφ strom∙, kter²m je zpracovßnφ aritmetick²ch v²raz∙. Serißl se nßm tedy pomalu, ale celkem jist∞, blφ₧φ ke svΘmu konci. Pokud byste m∞li p°ßnφ na tΘma serißlu navazujφcφho, nechte mi vzkaz na mailu. T∞Üφm se p°φÜt∞ nashledanou. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||