Osadníci z Katanu – hledání nejdelší cesty
13. června 2006 15:13
programování
Konečně na svůj blog mohu napsat něco z mého oboru a z toho co
mě kromě skautingu zajímá nejvíce. Přichází první článek
o programování, nebo spíše o jednom konkrétním programu.
I když vlastně možná by to spíše mělo být v rubrice
škola, neboť jde o semestrální práci z teoretické
informatiky, kterou jsem dnes úspěšně odevzdal.
A o co tedy vlastně jde? Jde o program, který využívá
znalostí z teorie grafů a možnosti převedení relativně
běžných problémů na problémy nad grafy.
Možná znáte deskovou hru Osadníci z Katanu (The Settlers of
Catan). U nás v roverském kmeni je docela oblíbená a já
osobně také jeden exemplář vlastním. Můj program řeší část hry,
kdy se zjišťuje, který z hráčů má nejdelší cestu, za kterou
získá prémiové body do celkového hodnocení. Jde tedy o zajímavou
úlohu nad grafy – hledání nejdelší cesty.
Není to vlastně tak úplně standardní úloha, neboť běžné grafové
algoritmy řeší problém hledání nejkratší cesty. Proto jsem se při
svém řešení rozhodl na problematiku podívat trošku opačně. Prostě jsem
jen zkusil vzít klasický Dijkstrův algoritmus, který
hledá nejkratší cestu a při relaxaci – tedy porovnání ohodnocení již
objevených cest a modifikaci volby na tu nejkratší – volím naopak
cestu nejdelší. Tím ve výsledku dociluji toho, že algoritmus najde
nejdelší cestu.
Při realizaci programu využívám pro reprezentaci grafu v paměti
spojových seznamů, polí a vlastní prioritní fronty, která umí
zpracovávané uzly vždy seřadit do potřebného pořadí.
Pokud by vás prográmek zajímal, celý jej níže přikládám.
A ještě taková jedna drobnost, i přes to že s oblibou
programuji ve Visual Basicu .NET, tohle jsem napsal celé v C#. A to
i s využitím některých nových skvělých vlastností platformy .NET
2.0. Takže jsem si zkusil zase něco super, co mi opět ukázalo ohromnou
sílu platformy Microsoft .NET a také jsem odevzdal program v syntaxi
„blízké jazyku C“, který je na naší katedře až nechutně
zakořeněn. I z toho důvodu mě velmi potěšil zájem mého
cvičícího o C# a platformu .NET právě díky mé odevzdávané
práci.
autor: jerrysohn |
Komentáře
-
5. srpna 2006 21:35 |
vložil:
yog |
e-mail |
web
Tenhle článek mě velmi zaujal. Nemohl by ses, prosím, o tématu
grafových teorií více rozepsat? Podrobněji vysvětlit princip. Ukázat
příklady nějakých algoritmů a jejich nejastější využití při
programování. Předem dík
-
6. srpna 2006 9:02 |
vložil:
jerrysohn |
e-mail |
web
yog[1] Tak určitě bych se k teorii grafů mohl
rozepsat o něco více. Jakmile budu mít chviličku času tak uvedu
i nějaké příklady klasických algoritmů, které se snadno
používají. Ale zatím se do tohoto tématu nechci příliš pouštět
i z toho důvodu, že právě z toho předmětu mě čeká zkouška
(poslední pokus) a pokud ji nedám, tak by mohl následovat vyhazov, což bych
nerad. Ale až se budu na tuto zkoušku znovu učit, tak bych mohl nějaký
článek k tématu snad čas najít :o)
-
25. března 2008 18:19 |
vložil:
Lukas |
e-mail |
web
Ahoj Jerry,
to se celkem divim, ze ti to funguje ;-)
Zaujala me myslenka obraceneho klasickeho Dijkstrova
algoritmu (pomaham totiz ted jedne kamaradce psat v C# normalni
klasicky Dijkstruv algoritmus). Jeste to nemam uplne podlozene, ale
jednoduchym otocenim vyhodnocovaci podminky to jit nemuze. S dukazy mozna
prijdu pozdeji… :-)
Spis se chci ale zastavit
u tve implementace prioritni fronty.
Nejdrive par znamych odhadu
slozitosti:
Vlozeni prvku do serazene posloupnosti
O(ln(n))
Nalezeni nejvetsiho prvku
v neserazene posloupnosti O(n)
Razeni pole
pomoci QUICKSORT O(n ln(n)) (coz tusim Array.Sort() pouziva)
A nyni k me kritice Odhadu casove vzdalenosti:
Cituji: Výběr uzlu v prioritní frontě lze díky implementaci
provést zhruba v čase O(lg|U|) – Neni nahodou prioritni
fronta krasna v tom, ze vyber lze provest v konstantnim case? Tedy
O(1)? Proste vemu prvni prvek z fronty… code: Uzel vyzvednuto =
fronta.Dequeue();
Cituji: vždy je třeba po změně
hodnoty vzdálenosti provést seřazení prioritní fronty (zařazení uzlu na
správnou pozici prioritní fronty), což trvá O(lg|U|). – Toto by
platilo, kdyby jsi uzel vkladal do serazene posloupnosti, ty ale ovsem delas
neco uplne jineho…
Rozeberu metodu
PriorityQueue.Sort(ListSortDirection)
Uzel[] uzly =
this.ToArray();… v nejlepsim pripade O(1)
Array.Sort(uzly);… razeni seznamu o kterem
zhola nic nevime O(n ln(n))
this.Clear();… v nejlepsim pripade O(1)
cyklus pres vsechny uzly →
this.Enqueue(uzly[i]);… O(n)
Metoda PriorityQueue.Sort(ListSortDirection) tedy celkem
O(n ln(n) + n) = O(n log(n)) namisto uvadenych
O(lg|U|)
Neber to prosim jako kritiku na
tvoji osobu (vubec te neznam) jen jsem se nudil v praci a mel jsem potrebu
se k tomu vyjadrit :-)
Preju hodne uspechu na FELu
:-)
-
26. března 2008 23:48 |
vložil:
Jerrysohn |
e-mail |
web
Lukas[3] Děkuji za kritiku této práce… už je
to celkem dlouho co jsem to na FELu psal, a když jsem pak k tomu něco
dodělával, tak jsem si uvědomil, že na tento problém to prosté otočení
v pohodě funkční je, ale že by se mohly vyskytnout případy, kdy by
skutečně k nějakému problému dojít mohlo.
Pokud jde o ty složitosti, tak to nebyla vždy úplně moje silná
stránka a cílem té práce bylo si to spíše vyzkoušet a zpracovat to co
nejlépe jsem v té době mohl… V každém případě děkuji
za doplnění komentáře a věřím, že tvé připomínky třeba pomohou
někomu dalšímu, kdo se tady na to bude dívat :-)
P.S. Na FELu již více jak rok nestuduji, ale jsem nyní na TU
v Liberci, takže snad se mi bude i nadále dařit ve studijích zde
;-)
-
17. května 2009 23:31 |
vložil:
marvel |
e-mail |
web
ahoj. Otočení Diskstrova algoritmu obecně nemůže platit. To, že ti to
pro některé případy vyělo je věc čistě náhodná. Zkus si vzít graf,
kde máš nezáporný cyklus, pak nejdelší cesta povede nekonečně-krát
přes tenhle cyklus. Vlastně nepotřebuješ ani cyklus v grafu. Samotná
myšlenka je totiž chybná. Stačí si uvědomit, jak dijkstrův alg. pracuje.
V každé iteraci zaručí, že najde nejkratší cestu do 1 vrcholu.
Pro nejdelší cestu ale ten algoritmus nedokáže zaručit, že
v 1 iteraci najde nejdelší cestu do 1 vrcholu. Popravdě mě
dost udivuje, že ti cvičící ten program přijal.
-
17. května 2009 23:34 |
vložil:
marvel |
e-mail |
web
ještě něco. Problém nejdelších cest je NP-úplný, to znamená, že
neznáme algoritmus s lepší časovou složitostí než
exponenciální.