ordog 最近的时间轴更新 ordog 最近的时间轴更新 |
ordogV2EX 第 277764 号会员，加入于 2017-12-29 16:36:45 +08:00 |
ordog 最近回复了
2018-01-02 10:59:24 +08:00 回复了 elfive 创建的主题 › 算法 › 求一个最短行程的算法或思路 |
添加一个虚拟的起始点 O，O 到所有线段两端的距离相同，比如都是 0。问题转化为一个全联通的 TSP 问题（包括 O 点在内），只是一些两两点之间路径固定（初始的黑色线段）。如果问题规模不大，是可以通过整数规划求精确解的。如果采用一些 tsp 的启发式方法求解，需要注意由于 O 点的存在，两边之和大于第三边的法则这里不适用。
Select Language