Mobile versionIch habe alle Hauptalgorithmen auf Diagramme und ähnliche Probleme beim Stackoverflow überprüft.
Bei fast allen TSP-Beispielen, die ich gegoogelt habe, ging es um vollständige Diagramme.
TSPLIB scheint mein Problem nicht lösen zu können.
Tut mir leid, wenn ich etwas verpasst habe.
Eingabediagramm (siehe Bilder):
• Gewichtet
• Ungerichtet
• Planar
• Kein Hamilton-Pfad
• Keine negativen Kanten
• Größe: bis zu 100 Eckpunkte (aber normalerweise 50-70)
Kantenlänge im Diagramm fast gleich, daher können wir sagen, dass es sich um ein ungewichtetes Diagramm handelt und 1 als Kantenlänge annehmen.< /p>
Sollte mit gelöst werden „Dead-End“-Fälle:
Echte Eingabediagramme sehen so aus (beginnend bei Scheitelpunkt 0):
Großes Diagramm:
Erwartetes Ergebnis:
• Kürzester Pfad (ein Satz von Scheitelpunktindizes) durch alle Kanten ab Startkante.
• Nr muss am Ende zur Startkante zurückkehren
Habe nur eine Idee:
1) Überprüfen Sie alle möglichen Kombinationen des Pfades, messen Sie die Entfernung und finden Sie den Pfad mit der kleinsten Entfernung.
1a) Verwenden Sie die Tiefensuche oder die Breitensuche
1b) Wenn der aktuelle Scheitelpunkt während der Iteration mehr als eine Kante hat, erstellen Sie eine separate Kombinationen für alle (versuchen Sie alle möglichen Wege).
1c) In meinem Fall gibt es viele „Sackgassen“ im Diagramm, daher sollte der Algorithmus den Weg finden (das schnellste ofc) von dort aus und iteriere durch bereits passierte Scheitelpunkte und bleibe nicht hängen.
2) Rekonstruiere den Pfad
Vielleicht sollte ich hier den Minimum Spanning Trees-Algorithmus verwenden auch…
Oder vielleicht sollte ich für eine schnellere Berechnung mein Diagramm in mehrere kleinste aufteilen, die nur mit einer einzelnen Kante verknüpft sind (wie 49-52, 40-41 auf dem Screenshot)< /p>
Jede Hilfe wird geschätzt.
Ich bevorzuge C#-Beispiele (libs), aber ich kann Code aus jeder Sprache portieren.