Dynamické programování – Pascal – Fórum – Programujte.com

Zdravím, dneska jsme dostali na zkoušce vyřešit tuto úlohu:
http://tinypic.com/view.php?pic=2w6ukg2&s=4
http://tinypic.com/view.php?pic=21km35u&s=4
Jsem z toho úplně zničený - nepochopil jsem ani pořádně zadání, natož, abych ještě dokázal úlohu vyřešit, či dokonce naprogramovat.
Chtěl jsem vás jen požádat o jakoukoliv radu, názor či dobrý tip, jak na to - jak to vyřešit, jak to naprogramovat..
Za cokoliv budu vděčný.

tak todle chce najit vhodnej algoritmus prochazeni stromu... tj nejdriv si udelat z dat o spojich nejakou strukturu kde na sebe budou navazovat ...

dalsi a slozitejsi cast je najit cestu s nejmensi cenou (nezamenovat s penezni cenou tady v tom musi byt i cas a vzdalenost)... tj budes muset ohodnocovat jednotlive uzly podle nekolika kriterii

doporucuju nejaky scripta o umele inteligenci... prochazeni stromu a tak

To Jeyekomon :
Jen jsem to prolétl, ale již z letmého pohledu je zřejmé, že se jedná o úlohu zaměřenou na teorii grafů. Stačí si nalézt základní pojmy z teorie grafů a grafové algoritmy. Pak už to budeš mít za chvilinku:)
Jinak tohle najdeš v každé slušné publikaci typu "Algoritmizace a datové struktury".:-)

Já bych to řešil asi takhle: Síť měst a spojů mezi nimi bych reprezentoval jako orientovaný graf (jak poznamenal Mihulik), kde města jsou vrcholy s spoje mezi nimi jsou hrany. Vlastně vy to byl multigraf, protože mezi dvěma městy může vést více spojů. Spoje bych do grafu zanesl pouze ty, které vyjíždějí ve stejný čas nebo později než chce osoba nastoupit a přijíždějí dříve nebo v čas, kdy chce osoba cestu dokončit. Jednotlivé hrany bych ohodnotil číslem cena za autobus + doba jízdy * hodinový plat osoby.

Teď už jde jen o to projít všechny cesty mezi městy A a B a pokud peníze za autobus nepřekročí peníze v peněžence, tak si cestu zapamatujeme. Zde se využije dynamické programování - cesty z A do B jsou cesty z A do jednotlivých sousedů a z nich pak do B, ale už je blbost aby se cestující vracel zpět do A. Protože ale z jednoho vrcholu může vést více hran do jiného, to znamená, že na některou linku by v daném městě chvíli čekal, zatímco jiná by mu jela třeba hned, takže se k ohodnocení spoje na který čeká musí ještě přičíst doba čekání * hodinový plat osoby. Z toho také vyplývá, že při procházení cestou si musíme pamatovat časy příjezdu osoby do města, abychom mohli vyřadit ty spoje, které už vyjely dřív.

Nyní z nalezených cest vybereme tu s nejmenším ohodnocením a to je námi hledaná ideální cesta. Pekud žádnou nenajdeme, pak neexistuje žádný způsob, jak se dopravit mezi A a B za zadané peníze a čas. Doufám, že jsem neopomněl nějaký důležitý detail ze zadání, který mije řešení diametrálně měnil. Slovní postup není až tak náročný, ale naprogramovat to už by mohlo být na delší čas.

Díky všem za ochotu pomoct, ale, jak řekl Wideman, naprogramovat to už by mohlo být na delší čas.. jo, to teda jo..
Zkusím se s tím nějak poprat.. :smile13:

Konečně někdo s netriviálním problémem. Vypadá to na programátorskou výzvu. Popřemýšlím o tom.

To Yety : krom toho ze to bude mit uz nejspis 9 mesicu vyreseny.. ale aspon se zabavis :D