Zadanie 2

Wyobraźmy sobie, że żyjemy w kraju bardzo odległym od naszego jakim są Chiny. Odbywamy właśnie staż w urzędzie pocztowym w Pekinie. Bagatela mieszka tam/przebywa około 20 mln ludzi. Naszym zadaniem jako listonosza jest dotarcie do mieszkańców w wybranej dzielnicy. Trudność polega na tym, że liczba mieszkańców jest stosunkowo duża, a listonosz jest jeden. Zatem należy wypracować sobie taki algorytm, który pozwoliłby nam zoptymalizować naszą trasę. W końcu doba ma tylko 24 godziny.

Zatem przejdźmy do czynów. W 1962 roku chiński matematyk Mei-Kowan by rozwiązać ten problem w następujący sposób: 

wędrując od skrzynki do skrzynki (w wybranej dzielnicy), listonosz odwiedza mieszkańców swojego rejonu w taki sposób, by wędrować od domu do domu po czym wrócić na pocztę; duża liczba mieszkańców sprawia, że listonosz pragnie przebyć trasę jak najkrótszą drogą. 

I właśnie wyszukanie takiej trasy nazywamy problemem chińskiego listonosza ang. Chinese Postman Problem  CPP

W oparciu o teorię grafów zaimplementuj ten problem. Można wykorzystać materiały publikowane w:

• http://www.sciencedirect.com/science/article/pii/S0305054898000926
• www.google.pl - Mei-Ko Kwan postman - pierwszy link jaki się pojawi to dokument

Co się może przydać w rozwiązaniu problemu:

• podstawowe pojęcia z teorii grafów
• algorytm Dijkstry
• cykl Eulera