旅行商问题

简介:

     旅行商问题(Traveling Saleman Problem,TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig(1959)等人提出。

  • 问题描述

由n个城市组成的网络,编号为V1,V2,....,Vn, Dij 表示Vi到Vj的距离(或时间,费用等),一般Dij ≠ Dji,一个推销员从V1开始,访问每个城市一次且仅一次,然后返回V1。这个推销员如何选择线路,才能使行程最短?

  • 问题抽象

一个有向图G(V,E),从某个顶点出发,经过每个结点一次且仅一次,返回出发结点。对于任意Vi,Vj ∈ V , 存在Eij和Eji,0 < Eij < ∞ ,0 < Eji < ∞,如果没有此条件,问题有可能无解,也就是说,此图是一个有向完全图。

  • 问题求解

(1)枚举法

相当于对V1,V2,V3,....,Vn做圆周排列,圆周排列为n!/n = (n-1)!,也即有(n-1)!条路径,需要(n-1)(n-1)!次加法,(n-1)!-1次比较。

(2)动态规划

令f(Vi ; V)表示结点从结点Vi出发,遍历V中的点一次且仅一次,然后返回V1的最短距离,其中V是某些结点构成的集合,且V1,Vi \notin V。

多段判决公式: f(Vi ; V ) = min { Dij + f(Vj ; V\{Vj} }  (Vj ∈ V)

因此问题就成了求 f(V1 ; { V2,V3,V4,...,Vn} } 的最小值


本文转自nxlhero 51CTO博客,原文链接:http://blog.51cto.com/nxlhero/696905,如需转载请自行联系原作者

 

相关文章
|
20天前
|
算法 Java Go
非启发式算法——旅行商问题(TSP)及其解决算法
非启发式算法——旅行商问题(TSP)及其解决算法
26 0
|
7月前
|
机器学习/深度学习 算法 机器人
【TSP问题】基于改进蜜蜂算法解决旅行商问题(Matlab代码实现)
【TSP问题】基于改进蜜蜂算法解决旅行商问题(Matlab代码实现)
|
8月前
|
存储 算法 决策智能
蚁群算法解决TSP(旅行商)问题
蚁群算法解决TSP(旅行商)问题
177 0
|
机器学习/深度学习 传感器 算法
【TSP问题】基于蜜蜂算法解决旅行商问题附Matlab代码
【TSP问题】基于蜜蜂算法解决旅行商问题附Matlab代码
|
算法
漫画:什么是旅行商问题?
和小灰所遇到的问题类似,旅行商问题所描述的是这样一个场景: 有一个商品推销员,要去若干个城市推销商品。该推销员从一个城市出发,需要经过所有城市后,回到出发地。每个城市之间都有道路连通,且距离各不相同,推销员应该如何选择路线,使得总行程最短呢?
176 0
漫画:什么是旅行商问题?
|
安全 数据库 计算机视觉
北京住建委:“人脸识别”将成每间公租房标配
预计到2019年6月底,人脸识别系统将覆盖所有已运营项目,涉及12万居民。
608 0
不一样的厦门,不一样的旅行!
厦门旅行的最后一天,位于酒店旁边的麦当劳,我又忍不住开始用文字记录短暂的厦门之行。 厦门之行,不一样的厦门之行,没有满屏的美食照片,没有满屏的风景照片,有的只是零星的个人足迹。
1050 0