14

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

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

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

谢谢

我在看ACO。对于这种问题，有什么比 ACO 更好的吗？

正确的A*算法在没有负载平衡的情况下找到成本最低或最快的路线。

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

没有2。如果使用 A*，那条路由上的流量就会超载，那么这条路径突然就变得多余了。因此，尽管 A* 很酷，但它没有 ACO 的某些特性，即固有的负载平衡。

-- 除非我弄错和误解了 A*

那么什么比 ACO 更胜一筹？

这看起来真的像是 ACO 和 A* 之间的一场对决，关于 A* 的正面讨论太多了，我一定会更深入地研究它。

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

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

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

4

7 回答 7

12

一般注意事项

Dijkstra 的算法及其优化的变体 A* 通过您的图形找到具有“最低”成本的路径。重要的是 a) 正确定义图表和 b) 定义适当的成本函数。

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

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

另一方面，蚁群优化在适应不断变化的成本函数方面似乎要灵活得多，方法是在成本函数变化之后/同时继续迭代。

效率

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

于 2008-10-21T11:07:34.310 回答
8

使用 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

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

A* 的真正威力是您用来计算每个连接成本的启发式方法。

于 2008-10-21T10:55:58.730 回答
7

这个问题最常用的算法是A* (A Star)，它是一种广义的 Dijkstra 算法搜索，添加了启发式算法 - 启发式算法的目的是将搜索引导到搜索目标，以便典型搜索更快地完成。

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

于 2008-10-21T09:46:03.943 回答
3

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

A* 游戏地图示例
（来源：cokeandcode.com）

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

该算法简单但功能强大。每个节点有 3 个值，g 是该节点的成本。h 是从该节点到目标的估计成本，f 是两者的总和（这是对完整路径的猜测）。A* 维护两个列表，打开列表和关闭列表。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 步开始重复。

还可以查看Wikipedia了解实现细节。

于 2008-10-21T10:13:33.700 回答
0

普通的 Dijkstra 还不够吗？

http://improve.dk/generic-dijkstras-algorithm/

于 2008-10-21T09:47:17.747 回答
0

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

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

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

于 2008-12-24T01:33:23.127 回答
0

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")
于 2018-05-03T08:06:42.240 回答