Chinesisches Postboten - Problem

Ziel des Chinesische Postboten-Problems ist es, einen kürzesten Pfad in einem Graphen zu finden, der jede Kante mindestens einmal benutzt und wieder zum Ausgangspunkt zurückkehrt.

Das prominenteste Beispiel für dieses Problem ist der Postbote, der in seinem Stadtteil Post austeilen muss. Er muss durch jede Straße mindestens einmal gehen, und am Ende seines Weges wieder am Postamt ankommen, wofür er selbstverständlich so wenig Zeit wie möglich brauchen möchte. Der Name des Problems begründet sich auf eben diesem Problem des Postboten, und auf der Tatsache, dass das Problem zum ersten Mal von einem Chinesen untersucht wurde.
Ein analoges Beispiel ist das Problem des Schneeräumdienstes: Auch hier muss das Schneeräumfahrzeug möglichst optimal jede Straße abfahren und am Ende zur Garage zurückkehren.

Ein Algorithmus zur Lösung dieses Problems ist der gerichtete CPP - Algorithmus.