Mindestanzahl von Schritten erforderlich jeden „speziellen“ Punkt auf einem Gitter besuchen

Question

ich an diesem Problem steckte:

---

Angenommen, haben wir die folgenden m von n Gitteranordnung (oder Matrix) G über das Alphabet {0, X, Y}

G =
0 0 X X ..
0 0 0 X ..
XY 0 .. X
:  :  :          :
0 X 0 .. 0

Finden Sie eine gute untere Schranke auf der minimal Anzahl der Schritte für erforderlich Y zu besuchen jedes der X ist auf dem Gitter (Ieeach der X ist in der Matrix) mindestens einmal, wo Y kann bewegen links, rechts , bis und unten eine Zelle zu einem Zeitpunkt?

(The Y und die X 's in dem Gitter G willkürlich gesetzt wurden, The Y und die X' s können überall auf der Matrix sein, auch die Anzahl der X 's auf der Matrix war willkürlich und es muss genau eins Y auf der Matrix) sein.

---

Sicherlich gibt es keine irgendeine Art von mathematischen Formel, die die genaue Anzahl der Schritte geben kann (Da es ein TSP Problem ist).

Aber wie können wir ein ausreichendeng untere Schranke für die tatsächliche Anzahl der Schritte (dh relativ leicht zu berechnen, unter Verwendung eines Algorithmus, zum Beispiel) zu finden?

ich gesehen habe, was vorgeschlagen wurde:

Using A* to solve Travelling Salesman

Und es wurde dort vorgeschlagen, dass die Gesamtkosten des Minimum Spanning Tree eine gute untere Schranke für TSP Probleme sein kann.

Aber im Gegensatz zu dem Problem gibt, hier, in diesem Problem, wir sind nicht erforderlich jedender Punkte auf dem Gitter zu besuchen, aber wir sind erforderlich jeder besuchen von den "speziellen" Punkten auf dem Grid mindestens einmal und um zu ihnen zu kommen müssen wir einige "nicht-spezielle" Punkte auf dem Raster zu besuchen, So weiß ich nicht, wie der minimale Spannbaum aussieht für dieses Problem (und vielleicht, wie Kruskal alg um es zu finden).

(Anmerkung: Ich habe dieses Problem aufgetreten, während eine Heuristik für A * Rastersuche, um herauszufinden, die einen Weg für Y berechnet, die jede der X ‚s auf dem Netz besuchen müssen mindestens einmal)

Danke für jeden Hinweis oder Hilfe.

Answer 1

Wenn ich die Frage richtig verstanden habe, ist eine enge Untergrenze für das Ziel des beschriebenen Problems gefordert. Eine solche Grenze ist tatsächlich der minimale aufspannende Baum der Instanz; die Abstände wären die paarweise kürzesten Wege zwischen dem X und Y Knoten (die in diesem Fall einige diskrete euklidische Abstände sind). Die Dichtheit des gebundenen kann eine Instanz gesehen werden, unter Berücksichtigung der

YXXXXX...X 

wie

sieht, wo das Gewicht des Spanning-Tree von Y auf die (nämlich die Anzahl der Knoten minus eins zu besuchen) dem Gewicht des kürzesten Weges ganz rechts X Knoten. Insgesamt muss Kruskals Algorithmus nicht modifiziert werden, um den minimalen Spannbaum zu berechnen.