使用优化算法寻找网络中的最短路径
我是算法设计和图论学科的新手。我正在模拟由数千个路由器组成的基于大型内容的网络。我正在使用“通过反向路径学习”进行路由。请求的内容名称和内容使用泛洪在网络中传播。路由器检查路由表中的匹配名称，然后回复或使用不匹配的请求内容名称和内容填充路由表。使用蚁群优化、爬山等优化算法代替反向路径学习会提高路由效率吗？
I am new to the subject of algorithm design and graph theory. I am simulating large content based network consisting of thousands of routers. I am using "Learning by reverse path" for routing. Requested content names and contents are propagated in network using flooding. Routers check for matching names in routing tables and either reply back or populate routing table with unmatched requested content name and contents. Will using optimization algorithm like Ant colony optimization, hill climbing etc instead of learning by reverse path improve routing efficiency?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果你的图满足三角不等式，即是欧氏空间，那么我建议你使用 christofides 近似算法，因为它保证最优值为 3/2。其他启发式算法（例如蚁群优化）非常快速且高效，但不是很安全。蚁群优化（以及暴力和 dp 解决方案）的一个很好的例子是 javascript 中的 google 地图 tsp 求解器。我相信空间填充曲线也是一个很好的近似，并且有一定的保证。您可以查看 z 曲线或希尔伯特曲线。您可以在尼克空间索引四叉树希尔伯特曲线博客或《黑客的喜悦》一书中找到有关希尔伯特曲线的好文章。我建议研究单调 n 元格雷码和哈密顿路径的构造。
If your graph satisfy the triangle inequality i.e. is an euklidian space then I suggest you to use the christofides approximation algorithm because it has a guarantee to be 3/2 in the optimum. Other heuristic algorithm like ant colony optimization are very fast and efficient but not very safe. A good example for an ant colony optimization (and brute force and dp solution) is the google map tsp solver in javascript. I believe a space-filling-curve is a good approximation too and has a certain guarantee. You may look into a z-curve or a hilbert curve. You can find a good article about the hilbert curve at Nick spatial index quadtree hilbert curve blog or in the book Hacker's delight. I suggest to look into constructing of monotonic n-ary gray codes and hamiltonian path either.