verschiedene Punkte werden zufällig aus einem Gitter ausgewählt. (Offensichtlich ist und ist eine gegebene konstante Zahl.) Aus diesen Punkten wird ein vollständig gewichteter Graph erstellt, so dass das Gewicht der Kante zwischen Scheitelpunkt und Scheitelpunkt dem Manhattan-Abstand zweier Scheitelpunkte auf dem ursprünglichen Gitter entspricht .k ≤ p × q k i j
Ich suche nach einer effizienten Methode, um die erwartete Länge des kürzesten (minimalen Gesamtgewichts) Hamilton-Pfades zu berechnen, der durch diese Knoten verläuft. Genauer gesagt sind die folgenden naiven Ansätze nicht erwünscht:
Berechnet die genaue Pfadlänge für alle Kombinationen von k Knoten und leitet die erwartete Länge ab.
Berechnet die ungefähre Pfadlänge für alle Kombinationen von k Knoten unter Verwendung der grundlegenden Heuristik der Verwendung eines minimalen Spannbaums, der einen Fehler von bis zu 50% ergibt. (Eine bessere Heuristik mit weniger Fehlern kann hilfreich sein.)
Antworten:
Unter der Annahme, dass und ziemlich groß sind, würde man erwarten, dass die erwartete Länge hauptsächlich von der Dichte abhängt, wobei ein gewisser Korrekturterm vom Umfang abhängt. Es wäre also in erster Ordnung eine Funktion der folgenden Form.qp q
Jetzt können Sie Experimente zu Problemen kleinerer Größe verwenden, um herauszufinden, was und sind. Um abzuschätzen , möchten Sie zunächst Experimente an einer Probe ohne Grenze durchführen: Der einfachste Weg, dies zu tun, besteht darin, ein Gitter zu verwenden, bei dem die linke Seite mit der rechten Seite und die Oberseite mit der Unterseite verbunden sind und a bilden Torus. Um zu schätzen , können Sie Experimente an einem Gitter verwenden.g f p × p g p × qf G f p × p G p × q
Für die Schätzung müssen Sie (genau oder ungefähr) relativ große TSPs lösen. Je größer die für die Schätzung verwendeten sind, desto besser sind Ihre Ergebnisse. Sie können entweder Heuristiken verwenden, die innerhalb weniger Prozent liegen, oder einen genauen TSP-Code. Sehen Sie hier für ein paar gute Heuristik. Der Concorde TSP-Solver von Bill Cook findet das genaue Optimum für relativ große Instanzen (es ist der beste verfügbare TSP-Code) und kann kostenlos für akademische Forschung verwendet werden.
quelle