[求助]：请教用ARX路径寻优的问题！

danglegedang · 发表于 2006-1-2 15:54:15

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

如图所示
由A点出发到B点有几种可选择的路径
请问用ARX程序如何需求它们之间的最短路径呢
谢谢

danglegedang · 发表于 2006-1-2 15:55:51

三维视图

Hellow · 发表于 2006-1-2 22:56:42

运筹学中典型的邮递员问题！

masterhe · 发表于 2006-1-3 09:14:24

这个问题其实在很多行业CAD软件中都会使用到，切入点是找到所有的路径，然后才是找最短的路径。
想清楚，方法其实就很简单了。我提示你就做两个类，一个表示节点，一个表示连线，你需要做了就是串起来。

danglegedang · 发表于 2006-1-6 09:53:45

非常感谢斑竹大人的指教
我现在水平比较低
您能给我解释的详细一点吗
特别是如何寻找所有路径
能否劳驾您帮我写几行主要的代码
谢谢

masterhe · 发表于 2006-1-6 20:29:22

如果“水平比较低”，这个问题过一段再做吧。不是调侃，是实在的建议。因为这个对指针、互引用类、递归都得用到。即使我帮你做出来，你也看不明白。

danglegedang · 发表于 2006-1-6 22:43:05

呵呵
我明白您的意思
只是小弟现在做毕业论文需要写一点这方面的东西
请斑竹大人高抬贵手了
不用太多
只写几行主要的代码
或者说框架
意思意思就行了
呵呵
谢谢

Hellow · 发表于 2006-1-8 00:20:46

写论文就比较好说，在《图论》这本书上，关于此问题应该有较为详细的描述，因为这是无向图方面典型的一种最短路径问题；若要写程序解决它，建议用Boost模板库，它里面专门有一个构件《Graph》，用于解决图论中的问题。

little5 · 发表于 2006-1-8 14:01:14

需要看看图论、网络优化什么的
－－－－－－－－－－－－－－－
如果只要求算a－b两点的最短路径，感觉应该很easy：不需要找所有路径（那样会出现np－hard），不涉及np－hard，用Dijikstra扩散就能搞定，当然也可以用一些更优化的算法，比如A*、两端同时Dijikstra扩散等等……
唯一的疑惑是，你的论文只需要做出2点间最短路就ok？感觉只找出一条路，实际意义不大，而且有n多已经做过的例子，当然如果是本科毕业论文，倒可以理解^_^

实际应用中应该能找出一组最短路才好，这样D扩散就不行了，很难回避np－hard问题，难啊～
－－－－－－－－－－－－－－－－－－－－－
另外arx中也有AcDbGraph类，但感觉写得不完全，或者是文档我没看懂（再感慨一次，ARX的文档真烂！），总之还不如自己写一个graph类……
To hellow: Boost库中的Graph模板你实际用过麽？是不是常用的图算法都有？呵呵，我回头找来看看，学c＋＋很久，连STL都没搞会，所以boost库一直是闻名已久，却从没有用过……

下学期的学习可能要涉及路网规划，希望和大家多多交流，……尤其是hellow，显然是高手，一定要多多指教^_^
Msn:gster1981@hotmail.com

RedCAD · 发表于 2006-1-8 19:20:02

用数学方法能解决吗？我认为这个问题用纯粹的数学是不能完全解决的，试想，给你一张全国公路网地图，现在要求任意两点间的最短路程，用软件能分析出来吗？如果从物理学分析，只要两点间的电阻最小，那就是最短的路径，不知我是否把问题复杂化了

little5 · 发表于 2006-1-8 21:13:35

“试想，给你一张全国公路网地图，现在要求任意两点间的最短路程，用软件能分析出来吗？”
——————————————
很多GIS软件的必备功能^_^
另外游戏中的自动寻路算法也是原理相同的（但要麻烦的多，涉及到动态求路，如有前方有障碍或突然阻塞）
比如玩star craft，随机点一个点，你的Marine就沿着最短最优路线噔噔噔就跑过去了^_^
核心算法不是问题
－－－－－－－－－－
任取一张图，任取2点a、b，判断ab是否连通（就是是否有直线曲线连接它们）并求出最短路线并以高亮或其他颜色标注出来，肯定是能够做到的，而且我想困难不是太大。
困难的是，列出a、b间所有连通路径，不过对于小规模的，也可以做到
嗯
等忙完考试静下来尝试写一下

masterhe · 发表于 2006-1-9 09:27:04

这里边有一基本CAD概念，不知道大家注意到没有，那就是CAD制图中在一张图上经常有不同比例或不按比例存在，这和GIS/游戏是不同的，不然坐标就能解决部份问题。当然可能楼主的问题不存在这一概念，不过在我从事的建筑和通信两个行业的CAD图纸中还是很常见的。

RedCAD · 发表于 2006-1-9 16:32:07

能分析出那太好了，但我还在想，问题的关键在于要分析出所有的路径，然后再找出最短的路径，但第一步的难度是相当大的，以后研究一下

little5 · 发表于 2006-1-10 11:18:55

这里边有一基本CAD概念，不知道大家注意到没有，那就是CAD制图中在一张图上经常有不同比例或不按比例存在，这和GIS/游戏是不同的，不然坐标就能解决部份问题。当然可能楼主的问题不存在这一概念，不过在我从事的建筑和通信两个行业的CAD图纸中还是很常见的。
——————————————————————
呵呵，我说的算法都是指赋权网络，坐标是赋权的一种方法。如果是同一比例，就完全能按WCS坐标自动用程序搞定，计算出相邻节点间边的距离（权）；如果不按比例，那就不能使用坐标了，要使用事先赋好的权值（不管比例是多少，2点间连上线，总该有个名义上的距离值吧？否则研究起来有什么意义？好比说a、b、c、d4个点，不知道ab、bc距离，求ad间最短路径显然是无解的）即可。
－－－－－－－－－－－－－－－－－－－－－－－－
能分析出那太好了，但我还在想，问题的关键在于要分析出所有的路径，然后再找出最短的路径，但第一步的难度是相当大的，以后研究一下
————————————————————————
其实找最短路的算法的关键，恰恰是能回避分析所有的路径^_^否则，算法是无效的，因为节点一多，2点间可能路径将呈爆炸性增长，根本不可能解决，难度当然大了，呵呵。
对图了解也不多，但看到Dijikstra的算法后，彻底拜服了。
BTW：图论就是巧妙处理这些千奇百怪的问题产生的^_^比如七桥问题、三色问题、背包问题，还有上面XD说过的邮递员问题……

RedCAD · 发表于 2006-1-10 13:47:00

楼上的兄弟是好样的，看来我这些还懂得很少啊？但我还是认为有的问题是采用数学方法无法解决的，比如在一张大的钢板上下料，每快料的形状都是千其百怪的，但其轮廓线都是可以用函数来描述，那如何来让所切下的料排得最紧密从而达到钢板的最高利用率，同是又如何来证明这是最省料的方式呢？上面的问题我也是这样认为的，当节点数增大时，可能计算机10年都算不完。

账号		自动登录	找回密码
密码			立即注册

[求助]：请教用ARX路径寻优的问题！

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

相关帖子