Problem chińskiego listonosza

Problem chińskiego listonosza (ang. Chinese postman problem, route inspection problem) – zadanie znalezienia najkrótszej ścieżki zamkniętej (wracającej do wierzchołka początkowego), która zawiera każdą krawędź grafu co najmniej raz.

Problem został pierwszy raz sformułowany przez chińskiego matematyka Kwan Mei-Ko w 1960 roku, choć jego artykuł został przetłumaczony na język angielski dopiero w 1962 roku[1].

Złożoność obliczeniowa problemu uzależniona jest od rodzaju grafu, na którym jest on rozpatrywany. W przypadku grafów w całości skierowanych albo nieskierowanych, problem chińskiego listonosza można rozwiązać w czasie wielomianowym. W przypadku grafów mieszanych (częściowo skierowanych, częściowo nieskierowanych) problem zalicza się do klasy NP-trudnych[2].

Algorytm

Rozpatrywany graf jest grafem spójnym, nieskierowanym i ważonym.

W grafie eulerowskim rozwiązanie problemu chińskiego listonosza stanowi cykl Eulera, jako że jest to z definicji ścieżka zamknięta przechodząca przez wszystkie krawędzie w grafie.

W grafie półeulerowskim rozwiązaniem problemu jest ścieżka Eulera (z definicji łącząca jedyne dwa wierzchołki nieparzystego stopnia w grafie) wraz z minimalną ścieżką (czyli ścieżką o najmniejszej sumie wag krawędzi) łączącą wierzchołki nieparzystego stopnia. Do wyznaczania najkrótszej ścieżki pomiędzy dwoma wierzchołkami służy algorytm Dijkstry.

Jeżeli rozpatrywany graf G nie jest półeulerowski, to znaczy, że posiada przynajmniej 4 wierzchołki nieparzystego stopnia. Z wszystkich wierzchołków nieparzystego stopnia grafu G należy utworzyć graf H, w taki sposób aby graf H był grafem pełnym z wagami na krawędziach odpowiadającymi najmniejszej ścieżce pomiędzy wierzchołkami w grafie G. W grafie H należy znaleźć minimalne skojarzenie doskonałe i uzupełnić o nie graf G. Graf G jest teraz multigrafem eulerowskim, w którym rozwiązaniem problemu chińskiego listonosza jest cykl Eulera[3].

Przypisy

  1. William R. Stewart, Chinese Postman Problem, Saul I. Gass, Michael C. Fu (red.), Boston, MA: Springer US, 2013, s. 161–164, DOI10.1007/978-1-4419-1153-7_110, ISBN 978-1-4419-1153-7 [dostęp 2024-01-30] (ang.).
  2. W.L. Pearn, J.B. Chou. Improved solutions for the Chinese postman problem on mixed networks. „Computers & Operations Research”. 26 (8), s. 819–827, lipiec 1999. Elsevier Science Ltd.. DOI: 10.1016/S0305-0548(98)00092-6. ISSN 0305-0548. (ang.). 
  3. J.Edmonds, E.L.Johnson. Matching Euler tours and the Chinese postman problem. „Mathematical Programming”, s. 88–124, 1973. DOI: 10.1007/bf01580113. (ang.). 

Linki zewnętrzne