输入图:我有一个字典,它表示一个有向图,其中键是一个节点,值是它指向的节点。
输入英雄:所有节点的集合
此方法用于寻找所有节点组合之间的最大分离度。
def largestDegreeOfSeparation(graph, heroes):
q = deque()
currentHighestDoS = 0
DoS = 0
for hero in heroes:
path = (hero,)
q.append(path)
visited = set([hero])
while q:
path = q.popleft()
last_node = path[-1]
for node in graph[last_node]:
if node not in visited:
visited.add(node)
q.append(path + (node,))
DoS = len(path) - 1
if DoS > currentHighestDoS:
currentHighestDoS = DoS
currentHero = path[0]
currentHerosDestination = last_node
print str(currentHero) + 't' + str(path) + 't' + str(currentHighestDoS)
这个程序找到了4和5的分离度,然后它就继续运行,我想是因为它花了太长时间。有没有办法让这个方法运行得更快?
你可以创建一个包含每个英雄位置的numpy
(np)数组,它的存储顺序与另一个包含英雄对象的数组的存储顺序相同。假设你有英雄坐标:
pos_heros = np.array( [hero.coordinates for hero in heros], dtype='float64' )
array_heros = np.array( [hero for hero in heros], dtype = object )
然后计算距离矩阵
dist = np.subtract.outer( pos_heros[:,0], pos_heros[:,0] )**2
dist += np.subtract.outer( pos_heros[:,1], pos_heros[:,1] )**2
dist += np.subtract.outer( pos_heros[:,2], pos_heros[:,2] )**2
现在,您将通过获取对距离矩阵排序的索引来找到距离最近的每个英雄:
a = np.argsort( dist, axis=1 )
您可以使用np.take
有效地获得排序后的pos_heroes矩阵:
matrix_heros = np.take( array_heros, a )
matrix_heros中的每一行将代表一个英雄,第一列将是第一个最接近的英雄,第二列是第二个,依此类推…
例如,要获取第10列中离某个英雄最近的第一个和第二个英雄:
matrix_heros[9,0] # 9--> hero 0--> first closest hero
matrix_heros[9,1] # 9--> hero 1--> second closest hero
找到你想要的,这才是最遥远的英雄:
ans = matrix_heros[:,-1]
ans
将以与创建array_heros
相同的顺序包含距离最远的英雄。