Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m33pal:uloha3-2014 [2014/10/18 22:11]
velekmar vytvořeno
+++ courses:a4m33pal:uloha3-2014 [2025/01/03 18:28] (aktuální)
@@ Řádek 1: / Řádek 1: @@
 ===== Jak na to =====
+Myslenka, kterou zde uvadim je nasledujici: vytvorit novy graph, ktery bude obsahovat pouze pumpy (vcetne Start a cil, protoze maji take pumpy) a potom v novem grafu najit nejlepsi cestu pomoci Dijkstry aniz bychom resili benzim. To lze udelat v 3 nasledujicich krocich:
+  - Pocitam (pomoci Dijkstry ) nejlepsi cestu mezi Startem a mesty s pumpou (vcetne cilu, je-li to mozne). Budu zde ale brat ohled na benzin. Muze se tedy stat, ze mi na ceste dojde a nebudu moci pokracovat dale. Pokud jsem tedy schopen dojit ze Startu do nejakeho mesta M s pumpou ve vzdalenosti D, pak vytvorim v novem grafu hranu (start, M) = D; Uzel M se tedy stane sousedem Startu v novem grafu.
+  - Spustim opet Dijsktru tento krat z kazdeho mesta s pumpou do jinych mest s pumpou (vcetne cilu), kam jsem schopen dojet(opet zalezi na benzinu). Pak zase vytvorim v novem grafu hrany mezi mestem s pumpou odkud jsem zacal a kazdem mestem s pumpou, kam jsem dojel.
+  - Pomoci techto dvou kroku dostanu tedy novy graf, ktery bude obsahovat pouze start, vsechna mesta s pompou, kam jsem byl schopen dojet a cil. Hrany jsou pak nejlepsi cesty, ktere mi vratil Dijkstra. Protoze v tom novem grafu jsou same pumpy, uz neni potreba pocitat benzin. Spustim tedy klasicky algoritmus Dijkstry v tom novem grafu a vysledek je reseni.
+===== Mozna optimalizace =====
+V 1. a 2. kroku se muze stat, ze spocitam nejakou hranu 2 nebo vic krat. Je tedy potreba nejdriv kontrolovat jestli jsem nejakou hranu nepocital, predtim nez ji budu pocicat.

courses/a4m33pal/uloha3-2014.1413663072.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru