如何使用networkx库为对角启用的A *算法创建8个单元格邻接映射

问题描述 投票:1回答:1

默认情况下,nx.grid_graph(dim)给出四个最近邻居网格图。是否有一种方法可以获得对角线以创建八个最近邻居地图或者是否必须单独添加对角线?如果是这样,怎么办呢?

另外,有没有一种方法可以用2**0.5 = 1.414的长度属性来衡量对角线,这样寻路可以考虑对角线的适当加权?

这是我第一次使用networkx,我试图在文档中找到答案,但我找不到任何关于八个小区连接的提及或如何权衡来自对角线邻近的不同上/下/左/右邻居小区的示例细胞。

python networkx
1个回答
1
投票

Networkx没有内置函数,因此您应手动添加这些边。幸运的是,networkx.grid_2d将节点构造为具有笛卡尔坐标的点。它极大地简化了我们的代码。这里是:

# Create 4x4 grid graph
G = nx.grid_2d_graph(4,4)
G.nodes

    # Here you can see that nodes are just points with coordinates
    NodeView(((0, 1), (1, 2), (3, 2), (0, 0), (3, 3), (3, 0), (3, 1), (1, 1), (2, 1), (0, 2), (2, 0), (1, 3), (2, 3), (2, 2), (1, 0), (0, 3)))

# Set all weights to 1
for edge in G.edges:
    G.edges[edge]['weight'] = 1

如果你有4分:

0,0    1,0


0,1    1,1

你需要创建从0,01,1以及从1,00,1的边缘。所以我们用weight=1.4创建它们:

G.add_edges_from([
    ((x, y), (x+1, y+1))
    for x in range(3)
    for y in range(3)
] + [
    ((x+1, y), (x, y+1))
    for x in range(3)
    for y in range(3)
], weight=1.4)

并绘制图表:

nx.draw(G)

enter image description here

© www.soinside.com 2019 - 2024. All rights reserved.