Hallo, ich möchte ein Programm schreiben, der eine 2D-Matrix (Start = 1; Ziel: 0; Platz: 2; Hinderniss: -1) als Input nimmt und nach dem Djikstra Algorithmus die optimale Route berechnet und als Output einen 2x1-Matrix ausgibt mit dem optimalen Weg. Das Programm möchte ich mit MATLAB nutzen. Es gibt viele Dateien im Internet, jedoch nutzen alle Knoten und einen Graphen. Wenn ich beispielsweise einen Code mit Matrizen finde, dann ist der mit verschiedenen Zahlen beschriftet. Nun zu meiner Frage: Wie genau kann ich den Code umschreiben, um den gewünschten Input, Output zu bekommen und die gewünschte Matrix zu verwenden. Danke.
Hat der Lehrer das nicht erklärt?
Kai S. schrieb: > Wie genau kann ich den Code umschreiben, um den gewünschten Input, > Output zu bekommen und die gewünschte Matrix zu verwenden. Ein Graph besteht aus Knoten und Kanten. Angenommen: In einer Matrix sind die indizierten Elemente die Knoten; die Kanten sind die Übergänge zu den Nachbarelementen. Dann wäre die Transformation von der Matrix zum Graphen einfach, richtig? In deiner Matrix sind hingegen nur diejenigen Elemente auch Knoten, die mit 0,1,2 markiert sind. Wie sieht hier dein Lösungsansatz aus?
Gast
#5039214
Es heißt Dijkstra-Algorithmus. https://de.wikipedia.org/wiki/Dijkstra-Algorithmus Dort steht alles für eine Implementierung.
Die Spezialisierung des Dijkstra-Agorithmus auf Gittergraphen heißt Lee-Algorithmus. Unter diesem Begriff findest du mehr.
Zum ersten Mal vom "Lee-Algorithmus" gehört. ;-)
1 | |
2 | |
Da geht irgendwo verloren, dass man (genauso wie bei der Breitensuche) eine Queue benötigt, in der man die Trackingpoints speichert (oder man erhöht die Komplexität "etwas" und durchsucht in jedem Durchgang alle Elemente ;-). Wenn es wirklich um ein Maze geht, wird man aber sowieso besser von beiden Enden aus suchen (falls Komplexität wichtig sein sollte). Soll es allgemein sein (also Dijkstra wie vom TS geschrieben) dann kann man solche Matrix-Elemente mit lediglich zwei Nachbarn als Teil einer gewichteten Kante betrachten, was die Knotenmenge erheblich reduzieren kann. Führt aber alles wohl zu weit: Ich haben den Eindruck der TS ist noch dabei sich mit dem Konzept Graph/Knoten/Kanten vertraut zu machen.