使用优化算法寻找网络中的最短路径

Question

我是新兴的算法设计和图论的主题。我正在模拟由数千个路由器组成的大型内容网络。我正在使用“通过反向路径学习”进行路由。请求的内容名称和内容使用泛洪在网络中传播。路由器检查路由表中的匹配名称，并回复或使用不匹配的请求内容名称和内容填充路由表。将采用蚁群优化，爬山等优化算法代替反向路径学习提高路由效率？

Answer 1

如果你的图满足三角不等式，即是一个euklidian空间，那么我建议你使用christofides近似算法，因为它有最佳保证3/2。其他启发式算法（如蚁群优化）非常快速且高效，但不是很安全。一个蚂蚁殖民优化（和蛮力和dp解决方案）的一个很好的例子是JavaScript中的谷歌地图tsp解析器。我相信一个空间填充曲线也是一个很好的近似值，并且有一定的保证。您可以查看Z曲线或希尔伯特曲线。你可以在尼克空间索引四叉树希尔伯特曲线博客或黑客的喜悦中找到一篇关于希尔伯特曲线的好文章。我建议研究单调n元格雷码和哈密尔顿路径的构造。