Problem bei der Routeninspektion - Route inspection problem

In der Graphentheorie , einem Teilgebiet der Mathematik und Informatik , besteht das chinesische Postman-Problem , Postman-Tour- oder Routeninspektionsproblem darin , einen kürzesten geschlossenen Weg oder Kreis zu finden, der jede Kante eines (verbundenen) ungerichteten Graphen besucht . Wenn der Graph einen Eulerschen Kreis hat (ein geschlossener Weg, der jede Kante einmal abdeckt), ist dieser Kreis eine optimale Lösung. Andernfalls besteht das Optimierungsproblem darin, die kleinste Anzahl von zu duplizierenden Graphkanten (oder die Teilmenge von Kanten mit dem minimal möglichen Gesamtgewicht) zu finden, damit der resultierende Multigraph eine Eulersche Schaltung hat. Es kann in polynomieller Zeit gelöst werden .

Das Problem wurde ursprünglich 1960 von dem chinesischen Mathematiker Kwan Mei-Ko untersucht , dessen chinesisches Papier 1962 ins Englische übersetzt wurde. Der ursprüngliche Name "Chinese Postman Problem" wurde ihm zu Ehren geprägt; verschiedene Quellen schreiben die Prägung entweder Alan J. Goldman oder Jack Edmonds zu , die beide zu dieser Zeit beim US National Bureau of Standards waren.

Eine Verallgemeinerung besteht darin, eine beliebige Menge T von gleich vielen Knoten zu wählen , die durch eine Kantenmenge im Graphen verbunden werden sollen, deren Knoten ungeraden Grades genau die von T sind . Eine solche Menge wird T- Join genannt. Dieses Problem, das T- Join-Problem , ist auch in polynomieller Zeit durch denselben Ansatz lösbar, der das Postman-Problem löst.

Ungerichtete Lösung und T- Joins

Das Problem der ungerichteten Routeninspektion kann in polynomieller Zeit durch einen Algorithmus gelöst werden, der auf dem Konzept eines T- Joins basiert. Sei T eine Menge von Knoten in einem Graphen. Eine Kantenmenge J heißt T- Join, wenn die Ansammlung von Knoten, die eine ungerade Anzahl inzidierender Kanten in J haben, genau die Menge T ist . Ein T- Join existiert immer dann, wenn jede zusammenhängende Komponente des Graphen eine gerade Anzahl von Knoten in T enthält . Das T- Join-Problem besteht darin, einen T- Join mit der minimal möglichen Anzahl von Kanten oder dem minimal möglichen Gesamtgewicht zu finden.

Für jedes T besteht ein kleinster T- Join (sofern er existiert) notwendigerweise aus Pfaden, die die Ecken von T paarweise verbinden. Die Pfade werden so beschaffen, dass die Gesamtlänge oder das Gesamtgewicht von allen so klein wie möglich ist. In einer optimalen Lösung teilen sich keine zwei dieser Pfade eine Kante, aber sie können gemeinsame Scheitelpunkte haben. Ein minimaler T- Join kann erhalten werden, indem man einen vollständigen Graphen auf den Ecken von T konstruiert , mit Kanten, die kürzeste Pfade in dem gegebenen Eingabegraphen darstellen, und dann in diesem vollständigen Graphen ein perfektes Matching mit minimalem Gewicht findet . Die Kanten dieses Matchings stellen Pfade im ursprünglichen Graphen dar, deren Vereinigung den gewünschten T- Join bildet. Sowohl das Konstruieren des vollständigen Graphen als auch das anschließende Finden einer Übereinstimmung darin kann in O( n 3 ) Rechenschritten erfolgen.

Für das Routeninspektionsproblem sollte T als Menge aller Knoten ungeraden Grades gewählt werden. Nach den Annahmen des Problems ist der ganze Graph zusammenhängend (sonst existiert keine Tour), und nach dem Handshaking-Lemma hat er eine gerade Anzahl von ungeraden Knoten, so dass immer ein T- Join existiert. Die Verdoppelung der Kanten eines T- Joins führt dazu, dass der gegebene Graph zu einem Eulerschen Multigraphen wird (ein zusammenhängender Graph, in dem jeder Knoten geraden Grad hat), woraus folgt, dass er eine Euler-Tour hat , eine Tour, die jede Kante des Multigraphen besucht genau einmal. Diese Tour wird eine optimale Lösung für das Problem der Routeninspektion sein.

Gezielte Lösung

Bei einem gerichteten Graphen gelten die gleichen allgemeinen Ideen, jedoch müssen unterschiedliche Techniken verwendet werden. Wenn der gerichtete Graph Eulersch ist, braucht man nur einen Eulerkreis zu finden. Wenn dies nicht der Fall ist, muss man T- Joins finden, was in diesem Fall bedeutet, Pfade von Knoten mit einem In- Grad größer als ihr In- Grad zu solchen mit einem Out- Grad größer als ihr In- Grad zu finden, so dass sie Ein-Grad jedes Knotens gleich seinem Aus-Grad. Dies kann als ein Beispiel des Minimum-Cost-Flow-Problems gelöst werden, bei dem es eine Angebotseinheit für jede Einheit mit Überschuss-In-Grad und eine Nachfrageeinheit für jede Einheit mit Überschuss-Out-Grad gibt. Als solche ist sie in O(| V | 2 | E |) -Zeit lösbar . Eine Lösung existiert genau dann, wenn der gegebene Graph stark zusammenhängend ist .

Windiges Postbotenproblem

Das Windy-Postman-Problem ist eine Variante des Routeninspektionsproblems, bei dem die Eingabe ein ungerichteter Graph ist, bei dem jedoch jede Kante andere Kosten für das Durchqueren in eine Richtung haben kann als für das Durchqueren in die andere Richtung. Im Gegensatz zu den Lösungen für gerichtete und ungerichtete Graphen ist sie NP-vollständig .

Anwendungen

Verschiedene kombinatorische Probleme wurden auf das chinesische Postman-Problem reduziert, einschließlich des Findens eines maximalen Schnitts in einem planaren Graphen und eines Kreises minimaler mittlerer Länge in einem ungerichteten Graphen.

Varianten

Einige Varianten des chinesischen Postman-Problems wurden untersucht und haben sich als NP-vollständig erwiesen .

  • Das chinesische Postbotenproblem für gemischte Graphen: Bei diesem Problem können einige der Kanten gerichtet sein und können daher nur aus einer Richtung besucht werden. Wenn das Problem eine minimale Durchquerung eines Digraphen (oder Multidigraphen) erfordert, wird es als "New York Street Sweeper-Problem" bezeichnet.
  • Das k- chinesische Postbotenproblem: Finde k Zyklen, die alle an einer bestimmten Stelle beginnen, so dass jede Kante von mindestens einem Zyklus durchlaufen wird. Ziel ist es, die Kosten des teuersten Zyklus zu minimieren.
  • Das "Rural Postman Problem": Lösen Sie das Problem mit einigen Kanten, die nicht benötigt werden.

Siehe auch

Verweise

Externe Links