You are here: Allgemeines > Softwarebibliothek > Routenplanung > ChinesischerPostbote > GerichteterCPPCode (02 Mar 2012, UnknownUser)

Chinesischer - Postbote - Problem (Pseudocode)

Eingabe: Ein gewichteter, gerichteter, endlicher Graph G = (V,E). Jeder Koten hat mindestens eine ankommende und eine abgehende Kante.

Ausgabe: Ein minimaler Kreis, der jede Kante mindestens einmal besucht hat.

BEGIN

Bestimme zwei Mengen von Knoten Y und Z. In Y kommen die Knoten mit mehr ankommenden Kanten als abgehenden (grün), und in Z die mit mehr abgehenden Kanten (rot).

Bestimme die kürzesten Wege zwischen je zwei Knoten y,z aus Y und Z.
(Alle Kanten werden ausgeblendet und die Kanten zwischen Y und Z werden eingeblendet)

Bestimme auf diesen Wegen und den Knoten aus Y und Z nun ein optimales Matching.
(Der Matching Algorithmus läuft nun los, wie bei der ungarischen Methode)

Erzeuge nun einen neuen Graphen G' der aus dem Graphen G und den Matchingkanten besteht.
(Die Matchingkanten (dick rot) werden nun mit Kantenzügen entlang der kürzesten Wege (dünn rot) ersetzt.)

Bestimme nun den Eulerkreis.
(In den Tupeln an den Kanten wird nun eingetragen, in welcher Reihenfolge die Kanten abgelaufen werden. Näheres zum Euleralgorithmus hier.)

END

Topic revision: r8 - 02 Mar 2012 - 09:30:21 - UnknownUser

Allgemeines

Impressum | Disclaimer und Rechtshinweise | AnregungenCopyright Technische Universität München, M9