Problem trgovskega potnika

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
Rešitev problema trgovskega potnika
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 (angleško traveling salesman problem (TSP)) je dobro znan problem. Trgovski potnik mora obresti 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