Kürzester Pfad auf Graphen finden (Roboter, Irrgarten) |
| 29.02.2016, 02:18 | Auf diesen Beitrag antworten » | ||
| java_oca | Kürzester Pfad auf Graphen finden (Roboter, Irrgarten) Hallo, hier ein Rätsel wo ich gerne die Hilfe dieses Forums in Anspruch nehmen würde: Ein ungerichtetes Graph beschreibt ein Irrgarten. Jede Kante hat einen positiven bez. negativen Wert. Der Irrgarten kann aus mehreren Exit-Knoten bestehen, es kann aber auch nur einen geben. Jeder Roboter hat eine gewisse Prozentzahl von Energie. Bei jeder Bewegung (von einer Kante zur nächsten) ändert sich diese Energie, je nach dem Wert der Kante (Also wenn die Kante einen Wert von +20% hat, ändert sich die Energie des Roboters auch um +20%. Wenn die Kante -5% hat, ändert sich die Energie des Roboters auch um -5%, etc.). Der Roboter stirbt wenn die Energie <= 0 ist. Ziel ist es für ein Roboter den kürzesten Pfad zu finden, ohne dabei zu Sterben. Der Roboter hat eine Karte des Irrgartens, muss also nur noch den kürzesten Pfad ausrechnen. Was ist ein guter Ansatz bez. Algorithmus um solch eine Aufgabe anzugehen? Dijkstra-Algorithmus geht nicht, da es hier nicht um den kürzesten Pfad geht, sondern um den Günstigsten. Außerdem sind negative Kosten inkompatibel. A* geht auch nicht, da keine wirkliche Schätzung der Distanz zum Exit-Knoten errechnet werden kann. Den besten Ansatz den ich bisher finden konnte war der Bellman–Ford Algorithmus, allerdings findet dieser nur den günstigsten, nicht den kürtesten Pfad. Danke für eure Hilfe im Voraus! java_oca. ADMIN: Habe Thema ausversehen in falsche Kategorie gepostet. Bitte in Algorithmen verschieben. Danke 
|
||
|
|
|||
| 29.02.2016, 06:32 | Auf diesen Beitrag antworten » | ||
| eulerscheZahl | Wie stellst du bei Bellman-Ford sicher, dass du zwischendurch nicht stirbst? Vielleicht kann man das Problem als Min-Cost-Flow umformen. Je nach Größe des Graphen könntest du auch eine Lookup Table verwenden: wenn du in Knoten X bist und Y Energie übrig hast, schaffst du es auf Weg Z am schnellsten. Da kannst du bei den Endknoten starten und dich dann zur Startposition durcharbeiten. |
||
| 29.02.2016, 14:27 | Auf diesen Beitrag antworten » | ||
| java_oca |
Hallo, danke für deine Antwort. Geht aber m.M. nach nicht, da durch negative Schleifen low cost immer unemdlich sein wird... Grüße, -java_oca |
||
|
|
