astar_path

astar_path(G, source, target, heuristic=None, weight='weight', *, cutoff=None)

使用 A* (“A-star”) 算法返回源节点与目标节点之间的最短路径中的节点列表。

可能存在多条最短路径。此函数只返回其中一条。

参数:

GNetworkX 图

source节点

路径的起始节点

target节点

路径的结束节点

heuristic函数

一个函数，用于评估从节点到目标的估计距离。该函数接受两个节点作为参数，并且必须返回一个数字。如果启发式函数不可接受（即它可能高估从节点到达目标的成本），则结果可能不是最短路径。由于算法会缓存每个节点的首次启发式计算结果，因此不支持更新同一节点的启发式值。

weight字符串或函数

如果这是一个字符串，则通过具有此键的边属性访问边权重（即，连接 u 到 v 的边的权重将是 G.edges[u, v][weight]）。如果不存在此类边属性，则假定边的权重为 1。如果这是一个函数，则边的权重是函数返回的值。该函数必须接受恰好三个位置参数：边的两个端点以及该边的属性字典。该函数必须返回一个数字或 None 以表示隐藏的边。

cutoff浮点数，可选

如果提供了此参数，则搜索将限制在此值内。也就是说，如果评估函数对于节点 n 超过此值，则该节点将不会进一步扩展并会被忽略。更正式地说，设 h’(n) 是启发式函数，g(n) 是从源节点到达 n 的成本。那么，如果 g(n) + h’(n) > cutoff，则不会进一步探索该节点。请注意，如果启发式函数不可接受，即使路径满足截止值，也可能会被忽略。

引发:

NetworkXNoPath

如果源节点与目标节点之间不存在路径。

另请参阅

shortest_path, dijkstra_path

说明

边的权重属性必须是数字。距离计算为遍历的加权边的总和。

权重函数可以通过返回 None 来隐藏边。例如 weight = lambda u, v, d: 1 if d['color']=="red" else None 将找到最短的红色路径。

示例

>>> G = nx.path_graph(5)
>>> print(nx.astar_path(G, 0, 4))
[0, 1, 2, 3, 4]
>>> G = nx.grid_graph(dim=[3, 3])  # nodes are two-tuples (x,y)
>>> nx.set_edge_attributes(G, {e: e[1][0] * 2 for e in G.edges()}, "cost")
>>> def dist(a, b):
...     (x1, y1) = a
...     (x2, y2) = b
...     return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
>>> print(nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight="cost"))
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]