在NetworkX / Python中为A *搜索启发式分配x，y坐标

Question

我试图在一个6*6互连节点网格上用python实现a*搜索算法，使用networkx组织节点并显示matplotlib。我已经让它工作，所以它找到了最短的路径，但没有启发式，它只是蛮力搜索-这是太昂贵的。 当我创建节点时，如何将x，y坐标分配给节点，或者有其他方法让启发式算法发挥作用？ （我知道networkx有一个我可以使用的内置a*函数，但我想证明我可以实现该算法）

以下是代码（StackOverflow格式有点混乱）：

import networkx as nx
G=nx.Graph()

import matplotlib.pyplot as plt


def add_nodes():
    G.add_nodes_from([0, 1, 2, 3, 4, 5, \
         6, 7, 8, 9, 10, 11, \
         12, 13, 14, 15, 16, 17, \
         18, 19, 20, 21, 22, 23, \
         24, 25, 26, 27, 28, 29,\
         30, 31, 32, 33, 34, 35])


    c = 0
    for y in range (0,5):
        for x in range (0,5):
            G.add_node(c, pos=(x/10,y/10))
            c=c+1
#http://stackoverflow.com/questions/477486/how-to-use-a-decimal-range-step-value
#prev code for brute force search:
#https://pastebin.com/DT76bvw5
#node pos: http://stackoverflow.com/questions/11804730/networkx-add-node-with-specific-position
#http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
#http://zurb.com/forrst/posts/A_algorithm_in_python-B4c



for a in G.nodes():
    if a not in (5, 11, 17, 23,29, 35):
        G.add_edge(a, a+1)
    if a not in (30, 31, 32, 33, 34, 35):
        G.add_edge(a, a+6)
    if a not in (5, 11, 17, 23, 29, 30, 31, 32, 33, 34, 35):
        G.add_edge(a, a+7)
    if a not in (0, 6, 12, 18, 24, 30, 31, 32, 33, 34, 35):
        G.add_edge(a, a+5)

def heuristic(a, b):
    (x1, y1) = a
    (x2, y2) = b
    return abs(x1-x2) + abs(y1-y2)

#def cost (from_node, to_node):


def a_star_search(graph, start, end):    
    #initialise open list
    open_nodes = []
    #initialise closed list
    closed_nodes = {}
    #put starting node on open list
    open_nodes.append(start)
    #initialise cost list
    cost_so_far = {}
    #no previous path
    closed_nodes[start] = None
    cost_so_far[start] = 0


    #lists for colour:
    eVisited= []
    ePath = []


    #while open list is not empty
    while (len(open_nodes) != 0):
        #pop q off the open list
        current = open_nodes.pop()


        #for each neighbour

        for next in G.neighbors(current):
            new_cost = cost_so_far[current] + G[current][next]['weight']
            print('cost between '+ str(current) + ' and ' + str(next) + ' = ' + str(new_cost))
            if next not in cost_so_far or new_cost< cost_so_far[next]:
                cost_so_far[next] = new_cost
                print('minimal cost for start to ' + str(next) +  ' found')

                #assign colour to show it's been added
                eVisited.append((current, next))

                #priority = new_cost + heuristic(end, next)
                open_nodes.append(next) #(next, priority)
                closed_nodes[next] = current
                print('node connected: ' + str(next))

    print(closed_nodes)
    v = closed_nodes[end]
    ePath.append((end, closed_nodes[end]))
    while v != start:
        ePath.append((v, closed_nodes[v]))
        v = closed_nodes[v]
    print(ePath)
    return ePath, eVisited

add_nodes()
ePath, eVisited = a_star_search(G, 18, 3)
pos=nx.spectral_layout(G) #positions for all nodes(?)

#draw nodes
nx.draw_networkx_nodes(G, pos, node_size=300)


#draw edges
nx.draw_networkx_edges(G, pos, width=3)
nx.draw_networkx_edges(G, pos, edgelist=eVisited, width = 6, edge_color='g')
nx.draw_networkx_edges(G, pos, edgelist=ePath, width = 6, edge_color='b')

#labels
nx.draw_networkx_labels(G, pos, font_size=10, font_family='sans-serif')

plt.grid('on')

#disable axis
plt.axis('off')
#draw graph
plt.show()

Answer 1

可以为每个节点指定位置：

for n in G:
    x, y = n // 6, n % 6  # row and column coordinates
    G.node[n]['pos'] = (x, y)

这样，你就可以访问这个属性了。在

^{pr2}$

编辑：如前所述，对于那些将来觉得这很有用的人来说，可以将其绘制成以下内容：

nx.draw(G, pos=nx.get_node_attributes(G, 'pos'))