作者stool100 (思念是毒你是解药)
看板CodeJob
标题[发案] 最短汉米尔顿路径(Hamilton path)演算法
时间Thu Feb 14 10:05:07 2008
状态: 已发包
发案人: Kevin Lai
联络方式1: MSN :
[email protected]
联络方式2: 站内信联系
有效时间: 徵到为止
专案类型: 演算法
专案说明:
请教是否有高人可以协助最佳路径的演算法
条件是 平面上 N 个点
每一点都必须拜访
不需考虑交叉线或是转角
也不用回到原点
只需要最短路径
希望是简单快速的演算法
不需严谨到绝对最短路径
虚拟码含说明即可.
不需程式.
技术需求: 演算法
预算: 欢迎报价
接案者要求: 北部
附注:
结案意见: (结案後自由填写,可以询问接案人愿不愿意暴光接案身份)
接案人:
说明: 目前进行中
--
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.6.19
※ 编辑: stool100 来自: 122.116.6.19 (02/14 10:06)
1F：推 uqljnro:最小生成树 02/14 11:51
2F：推 yoco315:推最小生成树 02/14 12:48
3F：推 tkcn:我倒觉得直接用 BB 找到一定阶段，效果可能会比较好 02/14 15:32
4F：推 revivalworld:google Prim or Dijkstra 02/14 19:53
5F：推 tkcn:不懂MST跟最短路径有啥关系..找出来的path有一堆edge要走两次 02/14 21:19
※ 编辑: stool100 来自: 122.116.6.19 (02/14 21:25)
6F：推 cole945:推 tkcn 囧" 而且Hamilton path不是NPC吗? 02/14 23:27
7F：推 yoco315:MST 是 TSP 的一个近似解，演算法上课不是都会教？ 02/15 10:13
8F：→ yoco315:对了，请问 BB 是虾米？ 02/15 10:13
9F：推 cole945:呃..好像没学到过o_O 不过我的疑惑是,MST并不是path呀._.? 02/15 11:18
10F：→ cole945:还有TSP是什麽的缩写@o@? 02/15 11:20
11F：→ cole945:知道TSP是什麽了..||| 02/15 11:26
12F：推 asword:BB 是 branch and bound? 02/15 13:30
13F：推 tkcn:是的.. BB 是 Branch & Bound 02/15 13:40
15F：推 revivalworld:囧 是 hamilton 看错了Orz 02/15 17:59
16F：→ JosephChen:Traveling Salesman Problem 02/15 22:30
17F：→ TonyQ:MST是全局的树啊 但是只看树跟子节点的话可以视为很多的path 02/16 00:45
18F：推 ahand520:hamilton path是NPC喔，如果要heuristic我这边倒是有 02/16 15:29