读书人

求图论里的算法解决办法

发布时间: 2012-03-08 13:30:13 作者: rapoo

求图论里的算法
一个大概30阶的图,要求过指定的节点,不是全部遍历,而且可以折返
发现而且没有规定两点间的直接路程最短/(可能存在V12> V13+V32)
不知道用什么算法可以把最小路径算出来
起始节点和最终节点没有要求
最好是在一起拉~求回路

[解决办法]
这个好象比较复杂.我的一个想法不知道行否,供参考.
把所有无关的节点(除了起始最终节点和指定节点以外的节点)都去掉.当然,前提是要在留下来的节点之间加上一些边. 例如A,B,C三点,有边AB=10, BC=20. 如我们要去掉B保留AC,就要加一条边AC=30. 这样问题就变成了图论中经典的销售员问题(Travelling salesman problem)了.不难在教科书和网上找到关于它的算法.

读书人网 >软件架构设计

热点推荐