thumb|right|200px|Rešitev problema trgovskega potnika thumb|right|200px|Problem za potovanje skozi 15 največjih nemških mest. Na sliki manjka Dortmund. Skupno število možnih potovanj je 14!/2 = 43.589.145.600 Problem trgovskega potnika ( (TSP)) je dobro znan problem. Trgovski potnik mora obiskati določeno množico mest tako, da bo pri tem prehodil čim krajšo pot in se vrniti v izhodišče.
Je NP-težek problem v kombinatorični optimizaciji pomemben pri operacijskih raziskavah, matematični optimizaciji in teoretičnemu računalništvu.
Problem potujočega kupca in problem vožnje z vozilom sta oba posplošitvi TSP.
Obstajajo trije načini reševanja
reševanje problema trgovskega potnika z dinamičnim programiranjem reševanje problema trgovskega potnika s sestopanjem reševanje problema trgovskega potnika z metodo razveji in omeji
Kategorija:Programiranje Kategorija:Algoritmi Kategorija:NP-polni problemi Kategorija:Hamiltonove poti in cikli