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

little5

呵呵，过奖了，我是门都没入的菜鸟，之所以一直JJWW个不停，就是对这些问题比较感兴趣，希望能逗引高手们出来发言，这叫什么来着，对，抛砖引玉。^_^
你的认为完全正确，你说的问题算法上叫割料问题（CSP）吧，典型的npc问题，无解，没有有效算法。所以放弃精确的搞出最小解的想法吧，呵呵。只有使用近似算法，比如什么贪婪啊遗传啊什么的……如果你能找出一个比目前算法稍好一点点点的，呵呵，那就牛啦，money滚滚而来——一个好算法，能卖很多钱的，你说的这个问题很有搞头的，你可以找找这方面的文献，深入做做。
呵呵，发现讨论到现在，重心移往算法上了，大大的跑题咯……
————————————————
其实算法确定了，比如楼主说的问题，应该用D扩散能搞定，具体实现到CAD中，工作量还是不小的。
我的想法是（假设是统一比例，按WCS坐标计算长度）：1、遍历搜索cad图，形成一个点权网络：从起点出发，沿所在线开始搜索，遇到线路分岔，开岔处即为节点。搜索完所有的线和节点，把任2点间线长作为权值，构成点权网络。2、对该网络进行计算，求出2点间最小路，并绘出（可以用颜色或高亮）路径。而且还能进行环搜索、求最小连通量等常见图算法。
所以第一步麻烦，需要一个好的遍历算法，查询交点，求交点间线的长度等等。
BTW：楼主去哪里啦？呵呵，看我的想法可行不？

RedCAD

真是感谢litt兄能给我们讲这么多高深的知识，希望你多上论坛和大家多多探讨各方面的问题

danglegedang

真的非常高兴大家对这个主题有这么大的热情
真的非常感谢各位朋友的回复
真的希望这个帖子能抛砖引玉使大家有所收获


至于算法我知道FD算法是比较好的
该算法的基本思想是：用Floyd算法求得无向图中多对顶点间的最短路径，根据最短路径模拟实施优化方案，在方案实施过程中,如果某种因素(如约束条件)发生作用,致使路径中少数顶点之间的邻接关系发生变化,这时只需确定邻接关系被改变的顶点对,再用Dijkstra算法求得这些顶点对之间的最短路径,加上其余部分路径,就能得到该图中各对顶点间新的最短路径。

只是具体到这个问题
我的ARX水平很低
不知道如何用它来描述出来

little5

感觉你的论文就不是那么简单^_^
呵呵最初以为你只要求A－B所以说用Dijikstra（我还是习惯j后加个i^_^），当然就2点间还有更有效率的A-star
要是求所有点两两间距，还是用F算法好，呵呵。当然用Dijikstra循环也可以，不过太丑了。
讨论这些算法意义不大，呵呵，都是千锤百炼的牛算法了，重点还是code实现。

你的程序是自己绘出网络图然后演示算法呢，还是直接应用程序去计算绘制好的图纸？后者稍棘手些。关键是读图元然后构成一个图类，后面算法就好办了。感觉重点还是数据存储的设计上，节点比较多，数据结构是大问题。遍历cad图，读出所有线，然后循环求出每个线和其他线的交点（intersectWith()）。对线上每相邻点，循环求出权值（getdistAtpoint）……至此，图类初始化需要的数据全部搞定（顶点坐标，阾结点集，边权……），剩下就是利用现有算法了。
我对arx也是刚接触，还是高手来说说……
BTW：RedCad，巧死了，今天上午导师给我们开会，居然问到了那个割料问题，呵呵，俺当时回答的那个快啊……