優化圖路徑查找和獲取特定座標節點

Question

我正在構建一個圖表類作爲一個字典。圖類用於在大型2D網格矩陣上執行路徑查找。節點被存儲爲密鑰，鄰居節點被存儲爲值。

這適用於快速路徑搜索，但我還需要從由x和y座標確定的字典中取出特定節點。

class Node(object): 
    def __init__(self, x, y): 
     self.x = x 
     self.y = y 

class Graph(dict): 
    def get_node_at(self, x, y): 
     for node in self: 
      if node.x == x and node.y == y: 
       return node 

    def set_neighbours(self): 
     pass 

graph = Graph() 

# build a 2d matrix of nodes 
for x in range(10): 
    for y in range(10): 
     graph[Node(x,y)] = [] 

# set the neighbour nodes for each node 
graph.set_neighbours() 
mynode = graph.get_node_at(6,6) # will later be executed quite often 

有沒有一種方法來優化圖類，使get_node_at方法在大型網格上表現更好？

Answer 1

將索引添加到Graph看起來像{(x,y):node}。這需要實施__setitem__將Node添加到索引，並且如果另一個Node已經存在並且__delitem__也將從索引中刪除Node，則將其刪除。這將允許get_node_at(self, x, y)只做return self.index[(x,y)]。