Problem kineskog poštara

Jedan od najpoznatijih i najviše izučavanih problema kombinatorne optimizacije je već pomenuti Problem kineskog poštara, skraćeno CCP (eng. Chinese Postman Problem). Naznačeni problem se sastoji u sledećem:
Jedan poštar je odgovoran za raznošenje pošte u dijelu grada. On započinje sa raznošenjem pošte iz određenog čvora u kome je locirana pošta i tokom radnog vremena mora da obiđe sve ulice u posmatranom dijelu grada najmanje jedanput, da bi se na završetku radnog vremena vratio u poštu. Logično je da sebi postavimo sledeće pitanje: koja je to ruta kojom treba da se kreće poštar, tako da rastojanje koje pređe bude minimalno, pri čemu svaku ulicu treba da obiđe najmanje jedanput.