一种基于统计的TSP贪婪算法
摘要:NP问题一直是计算机算法方面的一个重要研究领域。用数理统计的方法来解决TSP问题,是当前该领域的一个热点。该文较详细的介绍了一种常用的基于统计的TSP贪婪算法。
关键词:NP问题;旅行商问题;数理统计;贪婪算法
中图分类号:TP312文献标识码:A文章编号:1009-3044(2013)36-8325-02
1TSP简介
旅行商问题,即TSP问题(TravellingSalesmanProblem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。
旅行推销员问题是图论中最著名的问题之一,即“已给一个n个点的完全图,每条边都有一个长度,求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds,Cook和Karp等人发现,这批难题有一个值得注意的性质,对其中一个问题存在有效算法时,每个问题都会有有效算法。
迄今为止,这类问题中没有一个找到有效算法。倾向于接受NP完全问题(NP-Complet或NPC)和NP难题(NP-Hard或NPH)不存在有效算法这一猜想,认为这类问题的大型实例不能用精确算法求解,必须寻求这类问题的有效的近似算法。
2贪婪算法的分析和目前状况
贪婪算法(Greedyalgorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪婪法不要回溯。
贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序,按这种顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。
对于一个给定的问题,往往可能有好几种量度标准。初看起来,这些量度标准似乎都是可取的,但实际上,用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解,而是次优解。因此,选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
一般情况下,要选出最优量度标准并不是一件容易的事,但对某问题能选择出最优量度标准后,用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择,即局部最优解选择,然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题,最终可得到问题的一个整体最优解。
求解TSP的最直观的贪婪算法是基于最近领域的启发式方法:随机从某个城市出发,前往最近的未被访问过的城市,一直到所有的城市都被访问过并仅被访问一次,最后返回初始城市.这样的路径很难做到完美,通常要为在起始阶段贪婪的选择付出很大的代价。
本文将为大家介绍一种基于数理统计的边平均长度贪婪算法,该算法具有以下几个特点:简单,快速,高效,观念比较新颖,在整个贪婪算法中独树一帜。
3边平均长度算法
为了更好表达相关概念,本文定义以下几个术语(仅在本文内有效):
1)回路:是指这样一条路径,经过图中的每个点一次,且最后回到起点/
2)最短回路:是所有回路中路径值最小的那条回路/
3)边平均长度:
假设s是图纸中的一条边,那么该边的平均长度为
M(s)=包含边s的所有回路长度之和/回路的数量
为了方便讨论,我们假定每个图只有一条最短回路。
图1
例如:以图1总共有3个回路:ABCDABDCACBD.
每个回路长度P(ABCD)=33,P(ABDC)=36,P(ACBD)=19,最短回路是ACBD.
期刊库(http://www.zgqkk.com),是一个专门从事期刊推广、投稿辅导的网站。
本站提供如何投稿辅导,寻求投稿辅导合作,快速投稿辅导,投稿辅导格式指导等解决方案:省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。
【免责声明】本文仅代表作者本人观点,与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。
投稿辅导服务咨询与期刊合作加盟
陆老师联系QQ: 913775405(普刊)
蒋老师联系QQ: 867306987(核心)
刘老师联系QQ: 271374912(核心)
联系电话:18015016272
17327192284
投稿辅导投稿邮箱:zgqkk365@126.com
期刊推荐
- 《课程教育研究》 旬刊 国家级
- 《网络空间安全》(信息安全与技术)月刊 国
- 《价值工程》旬刊 国家级 科技统计源期刊
- 《高教论坛》 月刊 省级
- 《法制与社会》旬刊 省级
- 《中国教育学刊》月刊 14版北大核心
- 《语文建设》 旬刊 14版北大核心
- 《中国绿色画报》 月刊 国家级
- 《社科纵横》季刊 社科类优秀期刊
- 《求索》月刊 14版北大核心期刊
- 《财会月刊》旬刊 14版北大核心
- 《艺术品鉴》 月刊 省级
- 《中华建设》月刊 国家级 建设类优秀期刊
- 《教学与管理》旬刊 北大核心
- 《当代经济》 旬刊 省级
- 《新课程研究》旬刊 省级 教育类优秀学术期
- 《文教资料》 旬刊 省级
- 《学术界》 月刊 双核心
- 《吉林教育》旬刊 省级 教育类学术期刊
- 《中国农业资源与区划》 月刊 14版北大核心
- 《继续教育研究》月刊 北大核心期刊
- 《财经界(学术版)》半月刊 国家级
- 《电影评介》半月刊 14版北大核心
- 《公路交通科技》 月刊 北大核心
- 《新闻传播》月刊 省级 新闻类优秀期刊