图论找到最佳配置

Question

想象一下，我有下面的图

A . . . B . . . C  . . . EXIT
. . . . . . . . . . . . . . 
. . . . . . . . . . . . . .
D . . . E . . . F . . . . G

我有7"；房间"；(A-B.…(和7组蚂蚁。第一组蚂蚁有7只，第二组有6只，第三组有5只，以此类推。我必须为每个房间指定一个组，以便整个组所走的距离最小。

我想使用列表排列来检查所有的组合，计算距离并进行比较。请参见下文。这个野兽在这种情况下起作用！8个排列，但在我的实际项目中，我有多达42个房间，我无法计算！42种组合。

有什么想法吗？

import pandas as pd
import math
import numpy as np
import itertools
def calculateDistance(df, porte_a, porte_b):
try:
coord_a = [(x, df.columns[y]) for x, y in zip(*np.where(df.values == porte_a))][0]
coord_b = [(x, df.columns[y]) for x, y in zip(*np.where(df.values == porte_b))][0]
except Exception as e:
print(e)
print("Couldn't find the coordinates")
return
y1, x1 = coord_a[0], coord_a[1]
y2, x2 = coord_b[0], coord_b[1]
dist = math.sqrt(((x2 - x1) **2)  + ( (y2 - y1) **2 ))
return dist
gates = [x for x in range(1, 8)]
combinations = list(itertools.permutations(gates))
overall_distances = {}
paths = {6:3,
1: 8,
2: 7,
3: 6,
4:5,
5: 4,
7:2,
8:-1
}
def calculate_path(df, i):
print(i)
distance = calculateDistance(df, i, "exit")    
for j in range(paths[i]):
distance += calculateDistance(df, i, "exit")
return distance
def calculate_distance(df, list_points):
distance = 0
for i in list_points:
distance += calculate_path(df, i)
return distance
for i in combinations:
df = pd.DataFrame()
df[0] = [i[0], 0, 0, 0, 0, i[1]]
df[1] = [i[2], 0, 0, 0, 0, i[3]]
df[2] = [i[4], 0, 0, 0, 0, i[5]]
df[3] = [i[6], 0, 0, 0, 0, "exit"]
overall_distances[i] = calculate_distance(df, i)
print(min(overall_distances.items(), key=lambda x: x[1]))
print(max(overall_distances.items(), key=lambda x: x[1]))

Answer 1

• 按距离递增的顺序对房间进行排序
• 将最大的组分配给最近的房间
• 将第二大组分配给第二近的房间

优化：由于您不关心房间的绝对距离，只关心房间的相对距离，因此您可以比较它们距离的平方，从而节省42个平方根计算。