首页 > 编程语言 > 详细

北京地铁站点遍历最少经站次数问题普遍意义上是一个NP问题,目前不存在多项式时间算法能够解决该问题

时间:2016-09-19 01:09:04      阅读:407      评论:0      收藏:0      [点我收藏+]

标签:算法   log   com   http   it   si   la   sp   html   

http://www.cnblogs.com/jiel/p/5852591.html

 

众所周知求一个图的哈密顿回路是一个NPC问题:
  In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.
(来源于wiki:https://en.wikipedia.org/wiki/Hamiltonian_path

那么对于这里的-a 选项的问题,我们要求解这个问题的答案,假设我们存在一个多项式算法能够解决这个问题,并且得到答案{Len,{Station1,Station2,...}},其中Len是经过的最少站点数(重复算多个站点),后面跟着的是经过的站点名称。那么我们只需要作一个O(1)的判断:if Len==M print "Yes" else print "No" 即可完成对一个无向图是否存在哈密顿回路的判断(M为站点总数)。所以得到结论:存在一个多项式时间复杂度的算法以及一个多项式时间复杂度的转移,使得判断哈密顿回路是否存在的问题可以解决。显然与哈密顿回路是一个NPC问题矛盾。因此不存在一个多项式算法能够解决这个问题。

不知道这个推导是否正确?如果正确,那我想这个-a 的问题在这里是无法解决的(至少不能判定精确解)。

北京地铁站点遍历最少经站次数问题普遍意义上是一个NP问题,目前不存在多项式时间算法能够解决该问题

标签:算法   log   com   http   it   si   la   sp   html   

原文:http://www.cnblogs.com/toka/p/5883659.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号