没有合适的资源?快使用搜索试试~ 我知道了~
旅行商问题 Traveling Salesman Problem
需积分: 0 0 下载量 49 浏览量
2023-12-26
13:36:11
上传
评论
收藏 176KB PPT 举报
温馨提示
试读
29页
旅行商问题
资源推荐
资源详情
资源评论
旅行商问题
Traveling Salesman Problem(
TSP)
旅行商问题的发展历史
• 旅行商问题,也称货郎担问题,是一个较
古老的问题。其起源已经有些模糊了。最
早大概可以追溯到 1759 年 Euler 提出的骑
士旅行问题。
• 十九世纪初,爱尔兰数学家William R.
Hamilton和英国数学家Thomas P. Kirkman
研究过一些与旅行商问题相关的数学问题
。
• 二十世纪初,人们开始研究通用形式的旅行商问题。
• 二十世纪二十年代,数学家和经济学家 Karl Menger 在维
也纳向他的同事提出了这个问题。
• 二十世纪三十年代,旅行商问题出现在 Princeton 大学的
数学圈子里,主要的推动者有 Hassler Whitney 与 Merrill
Flood。
• 二十世纪四十年代,统计学家(Mahalanobis(1940),
Jessen(1942), Gosh(1948), Marks(1948))把它和农业应
用联系在一起研究。美国RAND 公司也推动了这个问题的
发展。
• 最终,旅行商问题成为了组合优化问题中的一个困难问题
原型的典型代表。求解这种问题令人望而生畏:当问题规
模变大的时候,路径的数目将是个天文数字,逐一检查它
们几乎是不可能的。在很长的一段时间内,没有任何解决
这个问题的好想法出现.
• 1954 年,旅行商问题的求解终于获得了突破。George
Dantizig, Ray Fulkerson 和 Selmer Johnson 提出了一个
求解旅行商问题的算法并用它成功地解决了一个有49 个
城市的实例。这个规模在当时相当引人注目;
• 1977 年,Groetschel 找到了有 120 个城市的旅行商问题
的最优路径;
• 1987年,Padberg 与 Rinaldi 找到了规模为 532 和 2392
的旅行商问题的最优路径;Groetschel与Holland找到了规
模为666的旅行商问题的最优路径。
• Applegate, Bixby,Chavátal 和 Cook 于 1994 年,1998年和
2001年解决了规模为 7397, 13509和 15112的旅行商问题
。
• 2004 年,一个具有 24978 个城市的旅行商问题的最优路
径由 Applegate, Bixby,Chavátal, Cook 和 Helsgaun 找到
。这是到目前为止精确找到最优解的最大规模的旅行商问
题.
• 旅行商问题吸引了越来越多的人对它进行研究。
其中,有数学家,计算机科学家,运筹学家,还
有一些其它领域的研究者。
• 然而,该问题是否存在一个有效的通用的求解方
法仍然是一个开放性的问题。事实上,旅行商问
题的解决将意味着 P=NP问题的解决。Clay
Mathematics Institute 曾悬赏 100 万美元来寻求
这个问题的解法,但没人拿到这个奖。
剩余28页未读,继续阅读
资源评论
RDSunday
- 粉丝: 232
- 资源: 171
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功