Проблем трговачког путника
Из пројекта Википедија
Проблем трговачког путника је проблем дискретне или комбинаторне оптимизације. Овај проблем илуструје класу проблема из области теорије рачунске сложености који су тешки за решавање.
[уреди] Поставка проблема
Ако је дат одређен број градова, цене путовања од било ког града до било ког града, која је најјефтинија рута која обилази сваки град тачно једном, и враћа се у почетни град?
Еквивалентан проблем изражен у терминима теорије графова би гласио: Дат је комплетан тежински граф (чији врхови представљају градове, гране представљају путеве, а тежине представљају цену путовања, или дужину пута) - наћи хамилтонски цикл најмање тежине.
Може се показати да захтев да се врати у почетни град не мења рачунску комплексност овог проблема.
Решење овог проблема је од великог практичног значаја, не само у питању саобраћаја. Добар пример у коме је битно на ефикасан начин решити проблем трговачког путника би могла да буде организација теретне луке: Ако се у луци у сваком тренутку налази више хиљада контејнера, наслаганих једни на друге, и свакодневно се стотине контејнера искрцавају са бродова, или товаре на шлепере, који је оптималан редослед кретања кранова за утовар и истовар, и где поставити који контејнер.
[уреди] Рачунска комплексност
Најдиректније решење би било да се испробају све пермутације, и да се види која је најјефтинија (коришћење метода грубе силе), али како је број пермутација за n градова n!, овакво решење врло брзо постаје непрактично.
Коришћењем техника динамичког програмирања, овај проблем се може решити у времену O(2n). Мада је ово време експоненцијално, ипак је много јефтиније од O(n!). Види Велико О.
