是否有任何算法可以在给定的连接的无向加权图/网络中找到源和汇之间的所有路径?该网络由多个源节点和一个汇聚节点组成。路径应该没有循环下水道设计的最佳路径
3
A
回答
1
我会用一个A *算法来解决这个问题,其基本路径发现存在以下差异。
- 从信宿而不是从源开始,因为只有一个信宿
- 每个节点是一组位置,而不是一个单一的位置。在每次迭代中,将所有位置的邻居添加到队列中。还要为所有邻居创建分支,以便在下一个集合中再增加一个位置。将最大位置数限制为来源数作为优化。
- 跟踪哪些源已在每个路径到达
- 的行进成本函数应与所有分支路的总行驶距离合并
- 估计函数应结合所有剩余的源
如果正确使用A *算法,这应该给出最佳路径。
0
如果您寻找所有无回路路径,breadth-frist search应该完成这项工作。在迭代中,对于每个当前路径,只要它到达路径或接收器上已有的点,就不要继续它。
0
它看起来类似于Minimum Spanning Tree。
相关问题
- 1. 最佳路径googleMaps
- 2. 知道SD卡路径的最佳途径Android
- 3. 什么是设计路线的最佳途径?有多条路线是否好?
- 4. 最佳路径查找
- 5. 检查最佳路径
- 6. 设计最短路径算法
- 7. 设置轨道路线的URL路径
- 8. 最佳最短路径算法
- 9. 场景的最佳设计
- 10. hbase的最佳rowkey设计
- 11. 水银路径
- 12. 计算最长路径
- 13. 网格中的最佳路径
- 14. 给定图上的最佳路径
- 15. PHP路径的最佳实践
- 16. 从点列表的最佳路径C++
- 17. 设计用户路径
- 18. REST资源路径设计
- 19. 设计路径冲突
- 20. C#设计时间路径
- 21. 道场的设置路径libnrary
- 22. wcf最佳设计原则
- 23. JSON设计最佳实践
- 24. Quest系统最佳设计
- 25. 最佳VHDL设计实践
- 26. Android设计最佳实践
- 27. 最佳数据库设计
- 28. A-星算法。获取最佳路径
- 29. Golang进口路径最佳实践
- 30. 嵌套的非资源性路由的最佳API设计
hm,所有路径还是最佳路径?如果最好,最好的是什么意思? – 2010-09-28 12:22:40
如果您查看所有路径,如果图形是加权的,这是否重要? – sandris 2010-09-28 14:18:52
这是字面上的下水道吗?如果是这样,图表是直接的,因为水只是下坡。 – mtrw 2010-09-28 14:19:49