首页 > 代码库 > 双调旅行商问题 (Bitonic TSP)
双调旅行商问题 (Bitonic TSP)
问题描写叙述:
上述问题能够使用动态规划的方法来解决。
以下是解决思路的详细介绍:
1. 最优子结构:
如果d[i][j]表示从起点1出发到达i及j两个顶点的最短路程之和。为此能够如果K为此段路程上与j相加的节点。则d[i][j] = d[i][k] + len[k][j]。
证明:若存在一个更短的路径d[i][k],则就应该存在更短的路径d[i][j]。这与如果矛盾,因此得证。
以下来寻找j相邻的节点,当中若i<j-1,则显然k=j-1,若i=j-1。则显然k属于(1,j-2)之间。为此得到例如以下的递推关系:
d[i][j] = d[i][j-1]+len(j,j-1) i<j-1;
d[i][j] = min(d[i][k] + len(k,j)),k属于(1,j-2)。
终于输出的d[n-1][n]就可以。
对于路径的输出,仅仅须要记录每次与j相邻的节点就可以,也即记录k的值。
详细实现稍后补充!!
双调旅行商问题 (Bitonic TSP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。