hrvatski

Problem kineskog poštara

Poštar treba pokupiti pisma u poštanskom uredu, dostaviti pisma u svim ulicama koje spadaju u njegovo područje i na kraju se vratiti u poštanski ured, pri tomu posao obaviti sa što manje hodanja. U terminima teorije grafova problem se svodi na pronalaženje najkraćeg zatvorenog puta u težinskim grafu koji uključuje svaki brid grafa najmanje jedanput. Ovo pitanje poznato je kao problem kineskog poštara (Chinese Postman Problem – CPP) i jedan je od najpopularnijih optimizacijskih problema s brojnim primjenama u praksi. Rad započinje uvodnim pojmovima iz teorije grafova te opisom matematičkih modela CPP-a. U drugom dijelu je detaljno opisan problem, njegove različite varijacije i postupci traženja rješenja.

graf; algoritam; optimizacija; problem kineskog poštara

nije evidentirano