在小世界图中寻找路径的最有效方法是什么？

StackOverflow https://stackoverflow.com/questions/221311

题

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

我希望找到一种路径查找算法，该算法不会消耗处理器功率，以沿着最佳可能路径找到一条路径，其中节点的权重最有利，最快的路线不是最重要的因素。该算法还考虑了负载承载和流量重新路由。

（边注：这里可以使用神经网络吗？）

谢谢

我正在看 阿科. 。对于这种问题，有什么比 ACO 更好的方法吗？

对了 A* 算法找到成本最低或最快的路线，无需负载平衡。

可以说，最快或最短路线并不是最重要的路线，更重要的是遵循权重节点具有一定值的路径。1号。

2号。如果使用 A*，该路由上的流量就会过载，那么该路径就会突然变得冗余。尽管 A* 很酷，但它没有 ACO 的某些功能，即固有的负载平衡。

——除非我弄错并误解了 A*

那么什么打败了ACO呢？

这看起来确实像是 ACO 和 A* 之间的较量，关于 A* 有很多积极的讨论，我当然会更深入地研究它。

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

我将进一步研究 A*。但我留给你最后一个问题！

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

有帮助吗？

解决方案

一般说明

Dijkstra的算法和它优化的变体A *找到带有“the”的路径。图表中的最低成本。重要的是a）正确定义图表和b）定义适当的成本函数。

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

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

另一方面，

蚁群优化似乎在适应变化方面更加灵活成本函数，在成本函数改变之后/后继续迭代。

效率

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

其他提示

使用A *，路径成本不需要保持不变，因此您可以从下图开始：

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

我们想要从A到C.最初，路径寻找算法将选择A-C路径，因为A-B-C是2而A-C是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更昂贵，ABC为2.当用户从系统中移除时，AC路由将变为最好的选择。

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

此问题最常用的算法是 A *（A Star），这是一个广义的 Dijkstra算法搜索，增加了启发式 - 启发式的目的是指导搜索搜索目标，以便更快地完成典型搜索。

此算法有许多变体，派生版本和改进，谷歌搜索或维基百科页面应该是一个很好的起点。

绝对是A*。A* 将找到可能的最佳路径，或者如果不存在路径则根本不找到路径。例如。这艘船的路径是使用 A* 计算的

A* Example on Game Map
（来源： cokeandcode.com)

这是一个 交互式 Java 演示 和玩。请注意，该算法因睡眠而减慢，因此您会看到它的执行情况。如果没有这种减速，它将在不到一秒的时间内找到路径。

该算法很简单，但功能强大。每个节点有3个值，g是到达该节点的成本。h 是从该节点到目标的估计成本，f 是两者的总和（这是对完整路径的猜测）。A* 维护两个列表：Open 列表和 Closed 列表。Open 列表包含迄今为止尚未探索的所有节点。Closed 列出了所有已探索过的节点。如果算法已经测试了连接到该节点的每个节点，则该节点算作已探索（连接只能意味着水平和垂直，如果允许节点之间的对角线移动，则也可以对角线）。

该算法可以描述为

  1. 设P为起点
  2. 将 g、h 和 f 值分配给 P
  3. 将 P 添加到打开列表中（此时 P 是该列表上的唯一节点）。
  4. 设 B 为 Open 列表中的最佳节点（最佳 == 最低 f 值）
    • 如果B是目标节点->退出，就找到了路径
    • 如果打开列表为空->退出，则不存在路径
  5. 设C是连接到B的有效节点
    • 将 g、h 和 f 分配给 C
    • 检查 C 是否在 Open 或 Closed 列表中
      • 如果是，检查新路径是否最有效（较低的 f 值）
        • 如果是，则更新路径
      • 否则将 C 添加到打开列表中
    • 对连接到 B 的所有节点重复步骤 5
  6. 将 B 添加到关闭列表（我们探索了所有邻居）
  7. 从步骤 4 开始重复。

还可以看看 维基百科 了解实施细节。

我听说过NN实现也可以解决这类问题。因此，如果您想使用NN，您最终会找到自己的方式;-)但与“遗传算法”相比，它们必须更低。

如果计算/时间消耗是一个问题，我强烈建议使用遗传算法。这就是他们特有的问题类型。

GA基于描述您对任何给定解决方案的满意度的函数。您可以修改此功能以满足您的需求（即，您不仅可以包括路径成本，还可以包括您希望的任何因素）。

Dijkstras算法，你的小例子

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top