Как создать карту смежности из 8 ячеек для алгоритма A * с диагональю с библиотекой networkx

Question

По умолчанию nx.grid_graph(dim) дает график сетки четырех ближайших соседей.Есть ли способ получить диагонали, а также создать карту восьми ближайших соседей или диагонали должны быть добавлены отдельно?Если да, то как это можно сделать?

Кроме того, существует ли способ взвешивания диагоналей с атрибутом длины 2**0.5 = 1.414, чтобы при поиске пути учитывались диагонали с соответствующим весом?

Этоэто первый раз, когда я использую networkx, и я попытался найти ответ в документации, но я не смог найти упоминания о соединении восьми ячеек или пример того, как по-разному взвешивать соседние ячейки сверху / вниз / влево / вправо по диагоналисоседние клетки.

Answer 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,0 до 1,1 и от 1,0 до 0,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)