作者noodleT (面T)
看板Prob_Solve
标题[问题] 最短路径问题
时间Mon Jul 25 22:25:26 2016
http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d062
题目如上面连结。
我的做法是先求出任两点间的最短路径值，
接着利用贪婪法决定下一个拜访(最近)的城市。
但如果离起点(当下位置)最近的有两个以上，
则把这些路径都测试过一遍。
虽然有通过测验，但这种作法是正确的吗？
还是运气好罢了？
会提出这问题是因为想到 TSP 无法用贪婪解。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.12.195.169
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1469456729.A.513.html
※ 编辑: noodleT (39.12.195.169), 07/25/2016 22:26:21
1F：推 FRAXIS: 这问题跟 TSP 应该是等价的吧 所以 greedy 应该不 work.. 07/25 22:37
我认为是不等价的，
TSP 中 af 距离为 sqrt(2)
而在此题中 af = ab + bf = 2
观念若有错请多包涵
※ 编辑: noodleT (39.12.195.169), 07/25/2016 22:55:35
2F：推 FRAXIS: TSP 中的 edge weight 是输入的一部分 07/25 23:03
3F：→ FRAXIS: 你想的 TSP 是 edge weight 被设定为 Euclidean distance 07/25 23:03
4F：→ FRAXIS: 所以只是 TSP 的特例而已.. 07/25 23:03
5F：推 FRAXIS: 不过这题的图是定死的 而且是 grid 的 subgraph 07/25 23:05
6F：→ FRAXIS: 所以应该有比较快的方法作吧 07/25 23:06
7F：推 DJWS: 运气好 07/26 06:52
8F：推 FRAXIS: 我查了一下 TSP 在 grid graph 中还是 NPC 的 07/26 11:49
9F：→ FRAXIS: HAMILTON PATHS IN GRID GRAPHS 论文 title 07/26 11:49
10F：→ FRAXIS: 不过如果 grid graph 上面没有洞的话是多项式可解的 07/26 11:50
11F：→ noodleT: 在这张图上有什麽例子是贪婪解不出来的？ 07/26 12:15
12F：→ noodleT: 看很久没看出来 07/26 12:16
13F：推 yvb: 从 n 出发, 须拜访 a, b, f, j, p. 07/26 14:07
14F：→ noodleT: 谢谢楼上，我再想想其他解法 07/26 19:57
15F：→ FRAXIS: 应该就 backtracking 吧 07/26 21:38
目前利用一张表来储存子问题(应该是属於动态规划解)，但效果不彰。
从 a 出发把所有点走一遍需要跑 30 秒左右(答案 15?)
unsigned SortestVisitWithBacktracking
(char begin,const std::vector<char> &visit)const
{
//map<pair<起点,拜访点向量>,最小路径>
static std::map<std::pair<char,std::vector<char> >,unsigned> table;
//...
}
在思考是不是需要改成
unsigned SortestVisitWithBacktracking
(char begin,const std::vector<char> &visit,unsigned 剩余步数限制)const
利用贪婪求一开始的剩余步数限制，
然後每次递回都更新(缩小)剩余步数限制
※ 编辑: noodleT (110.28.205.127), 07/28/2016 00:00:13
16F：推 FRAXIS: 应该是要的吧 不然你的方法就等同产生所有排列了.. 07/28 09:16
17F：推 DJWS: TSP可以用动态规划解 时间从O(n!)变O(2^n * n) 快了很多 07/28 22:00
18F：→ DJWS: O(2^n * n^2) 07/28 22:04
19F：→ noodleT: 加入限制条件後就快多了 08/01 16:38
20F：推 FRAXIS: 你还可以尝试 A star 08/01 21:01
21F：→ noodleT: 好的 08/01 21:17
22F：→ noodleT: a start 似乎没有保证最佳解 08/06 21:48
23F：推 FRAXIS: A* 如果你 heuristic 设计的对是保证会有最佳解的.. 08/06 22:02
24F：推 DJWS: 这题的heuristic要怎麽设计？我是第一次听说这种题目可以A* 08/10 07:06
25F：推 FRAXIS: 要设计不难啊 有没有用又是另外一回事.. 08/10 08:02
26F：→ FRAXIS: MST 的 cost 应该可以当 heuristic 吧 08/10 08:03
27F：推 DJWS: 是可以，不过总共得算多少次MST呢? 08/10 21:43