在networkx/python中分配x，y坐标* *搜索启发式

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

下面的代码（有点凌乱从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()

来源

2017-04-22 fianchi04

您可以为每个节点分配一个位置：

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

由此，您可以访问该属性。

for n, data in G.nodes(data=True): 
    print(n, data['pos']) 
# (0, 0) 
# (0, 1) 
# (0, 2) 
# ...

编辑：对于谁找到在未来，这是有用的，如前所述，这可能是人绘制有以下几点：

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

来源

2017-04-22 16:32:15

谢谢你 - 这允许我补充坐标，你知道我如何让matplotlib来绘制它们吗？有了您的代码建议，程序仍然使用默认的光谱布局进行绘制。如果我删除行“pos = nx.spectral_layout（G”，我得到的错误： nx.draw_networkx_nodes（G，pos，node_size = 300） NameError：名称'pos'未定义“ – fianchi04

没关系，我做了他们使用“pos = nx.get_node_attributes（G，'pos'）” – fianchi04

在networkx/python中分配x，y坐标* *搜索启发式

回答

相关问题