| Chinesisches Postbotenproblem | |
|
Das chinesische Postbotenproblem ist nach dem chinesischen Mathematiker Mei Go Guan benannt. Er dachte Anfang der 60er Jahre des 20.Jh. als einer der ersten über die Wegeoptimierung für Postboten nach. Bei dem Problem geht es darum, die kürzeste Rundtour durch einen zusammenhängenden, gewichteten Graphen zu finden, mit der Bedingung, dass jede Kante mindestens einmal besucht werden muss. Ähnliche Probleme finden sich auch bei der Routenplanung der Müllabfuhr oder bei der Planung einer Rundreise. (Hußmann 2007, S. 70-76) |