एक * खोज हेरिस्टिक

Question

के लिए नेटवर्कक्स/पायथन में एक्स, वाई कॉर्ड असाइन करना मैं 6 * 6 इंटरकनेक्टेड नोड ग्रिड पर पाइथन में एक * खोज एल्गोरिदम लागू करने की कोशिश कर रहा हूं, नेटवर्कक्स का उपयोग करके नोड्स और मैटलप्लॉब को प्रदर्शित करने के लिए। मुझे यह काम मिल गया है, इसलिए यह सबसे छोटा रास्ता पाता है, लेकिन ह्युरिस्टिक के बिना, यह सिर्फ क्रूर बल खोज है- जो कि बहुत महंगा है। मैं अपने नोड्स को एक्स, वाई निर्देशांक कैसे निर्दिष्ट कर सकता हूं जब मैं उन्हें बना सकता हूं या काम करने के लिए हेरिस्टिक प्राप्त करने का कोई और तरीका है? (मैं जानता हूँ कि मैं networkx इस्तेमाल कर सकते हैं इनबिल्ट एक * कार्य है, लेकिन मैं प्रदर्शन करने के लिए है कि मैं एल्गोरिथ्म को लागू कर सकते हैं)

यहाँ कोड (थोड़ा गंदा 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) 

इसके साथ, आप संपत्ति तक पहुंच सकते हैं।

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'))