Ich möchte die kürzeste Route von Station A zu Station B in Prolog in bidirektionalen Graphen finden (wenn A mit B verbunden ist als B mit A verbunden ist), hat das Diagramm keine Gewichte auf Ästen. Die Frage lautet wie folgt:
lösen (Start, Ende, Pfad).
Start-Start-Station.
Zielstation.
Pfad-Liste aller Stationen mit der kürzesten Route. Der Abstand zwischen zwei direkt verbundenen Stationen in der Grafik ist gleich. Tatsache in der Basis sind wie folgt:
Tatsache ("Staion1", "Metroline", "Station2", "Metroline").
U-Bahn-Linie ist die Nummer der Linie, die die beiden Stationen direkt verbindet. Wenn das 2. und 4. Argument gleich sind, sind die Stationen direkt verbunden.Return kürzesten Weg mit Breathth erste Suche in Prolog
Linie ("Abbesses", "12", "Pigalle", "12").
Linie ("Abbesses", "12", "Lamarck Caulaincourt", "12").
Linie ("Ale'sia", "4", "Mouton Duvernet", "4").
Linie ("Ale'sia", "4", "Porte d'Orle'ans", "4").
(Alexandre Dumas, 2, Philippe Auguste, 2).
Linie ("Alexandre Dumas", "2", "Avron", "2").
Linie ("Alma Marcesu", "9", "Ie'na", "9").
EDIT: Ich habe versucht, das Problem zu lösen, und ich finde heraus, dass es schneller arbeiten würde, wenn Sie BFS verwenden.
hier ist die Lösung, die ich schrieb:
lösen (Start, Ende, Pfad): - solve1 ([Start], Ende, [Start], Pfad).
solve1 ([P | O], Ende, besucht, [Ende |?]): - Kinder (P, S), Mitglied (Ende, S),!.
solve1 ([P | O], Ende, besucht, Pfad): -
(nicht (Mitglied (P, besucht)), Kinder (P, S), anhängen (O, S, O1), lösen1 (O1, Ende, besucht, Pfad));
(solve1 (O, Ende, besucht, Pfad)).
? - sollte die Liste mit Pfad zum Zielknoten sein
Das einzige Problem ist, dass ich nicht weiß, wie man den Pfad zum Zielknoten zurückgibt.
Vielen Dank.
Sagen Sie uns, wie Sie das Problem und wo Sie stecken geblieben zu lösen begonnen haben. Es sieht so aus, als wolltest du, dass andere das für dich komplett lösen ... –