Algorithmus für kürzesten Weg
-
Hallo Leute!
Ich hoffe ihr könnt mir hier bei diesem Problem helfen, falls es denn überhaupt lösbar ist.
Mal angenommen wir haben ein quadratisches Kästchen, das in viele kleine Quadrate eingeteilt ist. Etwa in der Größenordnung 10x10.
Nun ist in jedem Kästchen entweder ein Kreuz oder nicht. Die Anzahl der Kreuze ist immer grade.
Was ich nun suche, ist eine Möglichkeit jweils zwei Kreuze zu verbinden. Gemeint ist, das jedes Kreuz mit genau einem anderen verbunden ist. Die Verbindung verläuft immer entlang der Kästchen, keine Diagonalen oder ähnliches. Die Länge zwischen zwei Kreuzen ist demzufolge leicht zu ermitteln.
Das Problem ist, ich muss die Variante jeweils 2 Kreuze zu verbinden finden, in der die Addition der Längen der einzelnen Verbindungen minimal ist. Ich hoffe das war ne halbwegs verständliche Beschreibung.
Da es sich um etwa 60 Kreuze handelt, ist es natürlich nicht drin alle Möglichkeiten durchzuprobieren. Aber vielleicht existiert ein halbwegs effizienter Algorithmus dafür? Wäre auch sonst für alle Hinweise und Anregungen dankbar!
-
Google mal nach Shortest-Path Algorithmen und schau dir vielleicht die Boos Graph Library an.
-
Shortest Path ist hier nicht das richtige Stichwort. Das ganze ist ein Matching-Problem, und zwar ein gewichtetes. Gute Stichworte sind etwa "minimum weight perfect matching" oder ähnliches, wenn's schnell sein soll zusammen mit "in the plane", da gibt's Tricks die geometrische Situation auszunutzen, so daß es schneller geht.
Zuerst mußte mal zwischen jedem, Knotenpaar den Abstand bestimmen. Das gibt Dir nen Graphen mit 2n Knoten und n^2 Kanten. Den kannste nun in einen beliebigen Matcher reinstecken und Du kriegst in O(n^3) oder sowas die Optimallösung.
Das geht aber auch schneller, indem Du die geometrische Situation ausnutzt (hier wird die L_1-Norm verwendet). Dadurch läßt sich die Laufzeit auf O(n^2 log(n)) oder sowas drücken. Kann sein, daß es da inzwischen auch schon was besseres gibt. Ein schon relativ altes Paper von Vaidya, "Geometry helps in Matching" zeigt, wie's geht. Möglicherweise gibt's inzwischen schon bessere Sachen (bin da ziemlich sicher), aber Vaidy ist da ein guter Startpunkt. Ist allerdings keine leichte Kost.