Dynamické programování – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Jeyekomon0
Stálý člen
17. 9. 2008   #1
-
0
-

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ý.

Nahlásit jako SPAM
IP: 195.113.65.–
jjk
Reklama
Reklama
KIIV+42
God of flame
17. 9. 2008   #2
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.27.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Mihulik0
Návštěvník
18. 9. 2008   #3
-
0
-

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".:-)

Nahlásit jako SPAM
IP: 81.90.164.–
Wideman
~ Anonymní uživatel
7 příspěvků
18. 9. 2008   #4
-
0
-

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.

Nahlásit jako SPAM
IP: 213.29.196.–
Jeyekomon0
Stálý člen
20. 9. 2008   #5
-
0
-

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:

Nahlásit jako SPAM
IP: 195.113.65.–
jjk
Yety0
Stálý člen
29. 6. 2009   #6
-
0
-

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

Nahlásit jako SPAM
IP: 94.113.49.–
Kapitán A. J. Rimmer vesmírný dobrodruh
KIIV+42
God of flame
29. 6. 2009   #7
-
0
-

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

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 16 hostů

Podobná vlákna

Dynamické polia C++ — založil Filip

Dynamicke pole — založil george6565

Dynamicke pole — založil Earl Cash

Dynamicke signatury — založil raddino

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý