Problem chińskiego listonosza (
ang.Chinese postman problem lub route inspection problem) – w
teorii grafów
zadanie znalezienia
drogi
zamkniętej (wracającej do wierzchołka początkowego), zawierającej każdą
krawędźgrafu
co najmniej raz i mającej minimalny koszt (sumę wag krawędzi).
Problem został pierwszy raz sformułowany w 1962 roku w języku chińskim.
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
jest to problem klasy
P
. W przypadku grafów mieszanych (częściowo skierowanych, częściowo nieskierowanych) problem zalicza się do klasy
NP-zupełnych[1].
Przypisy
↑ W.L. Pearn, J.B. Chou. Improved solutions for the Chinese postman problem on mixed networks. „Computers & Operations Research”. 26 (8), ss. 819-827 (lipiec 1999). Elsevier Science Ltd..
doi:10.1016/S0305-0548(98)00092-6
.
ISSN0305-0548(
ang.
).
