Besuchen Sie alle Knoten in einem Diagramm mit mindestens wiederholten Besuchen

Question

Ich habe eine Kachel-basierte Karte, wo mehrere Kacheln Wände sind und andere sind begehbar. Die begehbaren Kacheln bilden eine Grafik, die ich in der Pfadplanung verwenden möchte. Meine Frage ist, sind sie irgendwelche guten Algorithmen für das Finden eines Pfades, der jeden Knoten im Diagramm besucht, wiederholende Besuche minimierend?

Zum Beispiel:

map example http://img220.imageshack.us/img220/3488/mapq.png

die untere, gelbe Fliese ist der Ausgangspunkt, der beste Weg, alle Steine ​​mit mindestens Wiederholungen zu besuchen ist:

path example http://img222.imageshack.us/img222/7773/mapd.png

Es gibt zwei Wiederhole Besuche in diesem Pfad. Ein schlechterer Weg wäre, an der ersten Kreuzung links abzubiegen und dann über drei bereits besuchte Kacheln zurückzugehen.

Ich interessiere mich nicht für den Endknoten, aber der Startknoten ist wichtig.

Danke.

Edit:

Ich habe Bilder auf meine Frage, aber kann sie nicht sehen, wenn es angezeigt wird. hier sind sie:

http://img220.imageshack.us/img220/3488/mapq.png

http://img222.imageshack.us/img222/7773/mapd.png

Zusätzlich in den Diagrammen ich diese brauchen denn es wird nie eine Situation, wo min Wiederholungen = 0. Das heißt, auf jeder Kachel in der Karte zu Schritt Der Spieler muss seinen eigenen Weg mindestens einmal kreuzen.

Answer 1

Ihre Formulierung ist schlecht - es ermöglicht eine Reduktion auf ein NP-vollständiges Problem. Wenn Sie wiederholte Besuche minimieren könnten, könnten Sie sie dann auf 0 schieben und dann hätten Sie eine Hamiltonian Cycle. Was ist solvable, aber schwer.

Answer 2

Das hört sich so an, als könnte es auf das Problem des reisenden Verkäufers abgebildet werden ... und so ist es wahrscheinlich, dass es NP-vollständig ist und kein effizienter deterministischer Algorithmus bekannt ist.

Einen Pfad zu finden ist ziemlich einfach - finde einen (oder den minimalen) Spanning-Teilbaum und führe dann eine Tiefen/Breite-zuerst-Traversierung durch. Das Finden der optimalen Route ist das wirklich Schwierige.

Sie könnten eine der dynamischen Optimierungstechniken verwenden, um zu versuchen, auf eine ziemlich gute Lösung zu konvergieren.

Es sei denn, es gibt ein Attribut des minimalen aufspannenden Unterbaums, das verwendet werden könnte, um den besten Pfad zu erzeugen ... aber ich erinnere mich nicht genug Graphtheorie dafür.