通过小世界图找到路径的最有效方法是什么？

我有一大堆加权节点,边缘将节点簇连接在一起.该图遵循典型的小世界布局.

我希望找到一种路径寻找算法,它在处理器功率上并不昂贵,找到沿着最佳路径的路径,其中节点是最有利的加权,最快路径不是最重要的因素.该算法还考虑了承载和流量重新路由.

(旁注:可以在这里使用神经网络吗？)

谢谢

我在看ACO.对于这类问题,还有比ACO更好的东西吗？

正确的A*算法找到成本最低或最快的路由,没有负载平衡.

假设最快或最短的路线不是最重要的路线,更重要的是遵循加权节点具有特定值的路径.NO1.

NO2.如果使用A*,该路由上的流量会过载,那么突然该路径是多余的.因此,与A*一样酷,它没有ACO的某些特性,即固有的负载平衡.

- 除非我误解和误解A*

然后是什么击败了ACO？

它真的看起来像ACO和A*之间的展示,有很多关于A*的积极谈论,我一定会更深入地了解它.

首先回应大卫; 我可以在后台运行ACO模拟并提出最佳路径,所以是的,有一个初始启动成本,但幸运的是,启动并不重要.所以我可以多次运行模拟.一个真正的麻烦是找到连接的源节点和目标节点.而A*似乎很容易就能做到这一点.现在当这个网络像数百万个节点一样变得非常大时会发生什么.A*能够轻松扩展吗？

我将进一步研究A*.但是我给你留下了最后一个问题!

A*能够和Antnet(ACO)一样扩展吗？

一般注意事项

Dijkstra的算法和它优化的变体A*通过图表找到"最小"成本的路径.重要的是a)正确定义图形和b)定义适当的成本函数.

面对不断变化的成本函数,Dijksta需要重新计算解决方案.

对于负载平衡,我会扩展Dikstra,不仅要计算最佳路径,还要使用某种泛洪填充行为来创建一组可能的路径(按成本排序)以找到替代方案.只有关于特定问题和成本函数的知识才能回答这是否以及如何起作用.

另一方面,通过在成本函数改变之后/之后继续迭代,蚁群优化在适应不断变化的成本函数方面似乎更加灵活.

效率

这在很大程度上取决于您的问题域.如果你有一个很好的启发式(参见A*文章的Complexity部分)并且很少有成本变化,那么A*的多项式运行时可能有利于重复重新计算.另一方面,ACO必须反复迭代才能收敛到近似解.如果非常频繁地发生成本变化,则以更快的速率继续迭代可能比更新A*解决方案更有效,因为信息保留在算法的状态内.ACO不承诺的最佳解决方案,但与可能在融入"好"解决方案之前,它具有更高的启动成本.同样,这在很大程度上取决于您的特定领域,图表和成本函数以及您对最优性的要求.

使用A*,路径成本不需要是常量,因此您可以从下图开始:

A---1---B---1---C
|               |
\-------1-------/

我们想要从A到C.最初,路径寻找算法将选择AC路径,因为ABC是2而AC是1.我们可以在路径中添加一个额外的术语:

A---r---B---r---C
|               |
\-------r-------/

同

r(NM) = k(NM) + users(NM) / 10

哪里

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

当用户被添加到系统中时,路由AC将比20个用户(1 + 20/10)= 3更加昂贵,ABC为2.当用户从系统中移除时,AC路由将成为最佳选择再次.

A*的实际功能是用于计算每个连接成本的启发式算法.

这个问题最常用的算法是A*(A Star),这是一个广义的Dijkstra算法搜索,增加了启发式算法 - 启发式的目的是将搜索指向搜索目标,以便典型搜索更快完成.

这个算法有很多变种,派生版本和改进,谷歌搜索或维基百科页面应该是一个很好的起点.