[问题] 最短路径问题

楼主: noodleT (面T)   2016-07-25 22:25:26
http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d062
题目如上面连结。
我的做法是先求出任两点间的最短路径值,
接着利用贪婪法决定下一个拜访(最近)的城市。
但如果离起点(当下位置)最近的有两个以上,
则把这些路径都测试过一遍。
虽然有通过测验,但这种作法是正确的吗?
还是运气好罢了?
会提出这问题是因为想到 TSP 无法用贪婪解。
作者: FRAXIS (喔喔)   2016-07-25 22:37:00
这问题跟 TSP 应该是等价的吧 所以 greedy 应该不 work..TSP 中的 edge weight 是输入的一部分你想的 TSP 是 edge weight 被设定为 Euclidean distance所以只是 TSP 的特例而已..不过这题的图是定死的 而且是 grid 的 subgraph所以应该有比较快的方法作吧
作者: DJWS (...)   2016-07-26 06:52:00
运气好
作者: FRAXIS (喔喔)   2016-07-26 11:49:00
我查了一下 TSP 在 grid graph 中还是 NPC 的HAMILTON PATHS IN GRID GRAPHS 论文 title不过如果 grid graph 上面没有洞的话是多项式可解的
楼主: noodleT (面T)   2016-07-26 12:15:00
在这张图上有什么例子是贪婪解不出来的?看很久没看出来
作者: yvb   2016-07-26 14:07:00
从 n 出发, 须拜访 a, b, f, j, p.
楼主: noodleT (面T)   2016-07-26 19:57:00
谢谢楼上,我再想想其他解法
作者: FRAXIS (喔喔)   2016-07-26 21:38:00
应该就 backtracking 吧
作者: DJWS (...)   2016-07-28 22:00:00
TSP可以用动态规划解 时间从O(n!)变O(2^n * n) 快了很多O(2^n * n^2)
楼主: noodleT (面T)   2016-08-01 16:38:00
加入限制条件后就快多了
作者: FRAXIS (喔喔)   2016-08-01 21:01:00
你还可以尝试 A star
楼主: noodleT (面T)   2016-08-01 21:17:00
好的
作者: FRAXIS (喔喔)   2016-08-06 22:02:00
A* 如果你 heuristic 设计的对是保证会有最佳解的..
作者: DJWS (...)   2016-08-10 07:06:00
这题的heuristic要怎么设计?我是第一次听说这种题目可以A*
作者: FRAXIS (喔喔)   2016-08-10 08:02:00
要设计不难啊 有没有用又是另外一回事..MST 的 cost 应该可以当 heuristic 吧
作者: DJWS (...)   2016-08-10 21:43:00
是可以,不过总共得算多少次MST呢?

Links booklink

Contact Us: admin [ a t ] ucptt.com