The directed Chinese Postman Problem

摘要

The Chinese Postman Problem has many applications, including robot exploration, and analysing interactive system and Web site usability. This paper reviews the wide range of applications of the problem and presents complete, executable code to solve it for the case of directed multigraphs. A variation called the 'open Chinese Postman Problem' is also introduced and solved. Although optimizations are possible, no substantially better algorithms are likely.