输入图:我有一个字典,代表一个有向图,其中键是一个节点,值是它指向的节点。

输入英雄:所有节点的集合

此方法用于查找所有节点组合之间的最大分离度。

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_heros矩阵:

 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的顺序包含最远的英雄。

10-06 08:36