Variation des chinesischen Postboten Problem_

Question

Um gut auf meine Frühjahrs-Viertelprüfungen vorbereitet zu sein, studiere und experimentiere ich gerade mit Grafikproblemen.

Ich kannte typische Probleme wie den "Traveling Salesman" schon, aber als ich mir das "chinesische Postbotenproblem" und seine Variationen genauer anschaute, fühlte ich sofort, dass ein wichtiger Aspekt des Problems fehlte: Der Aspekt von mit einer begrenzten Kapazität, so die Notwendigkeit, an die Büro-Station nach einer bestimmten Nummer n Briefe wird erfolgreich geliefert (um neue zu bekommen). Wie wäre es dann, den kürzesten Weg zu finden?

Ich war sehr fasziniert von der CPP wegen ihrer Relevanz und einfachen Anwendbarkeit für das wirkliche Leben, aber ich denke, das Hinzufügen dieses Aspekts würde es noch realistischer anwendbar machen.

Ich wäre dankbar für jede Hilfe, wie man den kürzesten Weg in einem ungerichteten Graphen findet, der jede Kante mindestens einmal besucht (CPP) die Einschränkung, nach einem bestimmten zum Ausgangspunkt (Poststation) zurückkehren zu müssen Anzahl der Briefe wird geliefert.

---

EDIT (Beschreibung der originial CPP): „Das chinesische Postbote Problem oder Routeninspektionsproblem ist einen kürzesten geschlossenen Pfad oder Schaltung zu finden, die jeden Rand eines (verbundenen) ungerichteter Graph besucht Wenn der Graph hat. eine Eulersche Schaltung (ein geschlossener Weg, der jede Kante einmal abdeckt), diese Schaltung stellt eine optimale Lösung dar. Wenn der Graph kein Eulerian ist, muss er Ecken von ungerader Gradzahl enthalten.Mit dem Handshake-Lemma muss eine gerade Zahl von Um das Postman-Problem zu lösen, finden wir zuerst einen kleinsten T-Join. Wir machen den Graph Eulerian durch Verdoppelung des T-Joins. Die Lösung des Postman-Problems im ursprünglichen Graphen erhält man, indem man eine Eulersche Schaltung für das Neue findet Grafik. " Src: wikipedia.org

Answer 1

Ihre Variante ist NP-hart durch eine Reduktion von beispielsweise 3-partition problem, wo alle Werte streng zwischen B/4 und B/2 liegen. Es könnte "gelöst" werden mit einigen der gleichen Methoden wie capacitated vehicle routing. Sie müssen jedoch verstehen, dass CPP weniger ein echtes Problem als eine Ausrede ist, T-Joins zu studieren.