优化图路径查找和获取特定坐标节点

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)]。