 Thema: Kürzester Pfad auf Graphen finden (Roboter, Irrgarten) |
|
|
 29.02.2016 14:27 |
Forum: Logik |
| Zitat: |
Original von eulerscheZahl
Vielleicht kann man das Problem als Min-Cost-Flow umformen. |
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
|
|
| Thema: Ist mein ER-Diagramm korrekt ? |
|
|
Hallo,
das ist leider kein ERD, sondern ein ERM (Entity–relationship model). M. m. nach kann allerdings ein Schüler mehrere Zeugnisse haben (z.B. für verschiedene Jahre). Ansonsten sehe ich damit keine Probleme.
Grüße,
java_oca.
|
|
| Thema: 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 
|
|
|
