Я украл алмазы во многих разных местах.Места находятся в системе координат (x, y), где каждое место названо по имени и имеет время d, например:
Name X Y dT
1 283 248 0
2 100 118 184
3 211 269 993
4 200 200 948
5 137 152 0
6 297 263 513
7 345 256 481
8 265 212 0
9 185 222 840
10 214 180 1149
11 153 218 0
12 199 199 0
13 289 285 149
14 177 184 597
15 359 192 0
16 161 207 0
17 94 121 316
18 296 246 0
19 193 122 423
20 265 216 11
dT обозначает время, назначенное для каждого места,это фиксированное время, когда нам нужно вернуть алмазы, прежде чем вор уберет их укрытие.
Начальная точка всегда равна 1.
Мне нужно посетить все места только один раз и получитьбриллианты возвращаются так, что общая задержка сводится к минимуму.Расстояние вычисляется с евклидовым расстоянием, округленным до ближайшего целого числа.Время прибытия для каждого места рассчитывается как расстояние + предыдущее расстояние.Задержка для каждого места обусловлена прибытием, и общая задержка представляет собой сумму задержек между местами.
Если полиция может получить алмазы раньше времени, установленного для этого места, то задержка равна 0;в противном случае задержка равняется разнице между временем прибытия и временем прибытия места.
Моя миссия состоит в том, чтобы найти правильный порядок, в котором полиция может посещать каждое место один раз, что минимизирует задержку для двух более крупных случаев.
Я думаю, что я довольно близок к ответу самно я хотел бы знать, как бы вы решили ее, а также лучше понять математику, стоящую за ней, чтобы лучше ее программировать.
Вот мои коды, которые вычисляют все, единственное, чего не хватает, так этоспособ найти правильный заказ:
#------------------------------------------------------------------------
poss=[(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)] # the order
here=[]
for p in range(len(poss)):
tempos=[]
for o in range(len(index)):
point=poss[p][o]
valuez=order[point-1]
tempos.append(valuez)
here.append(tempos)
#//DUE//
due =[[item[b][3] for b in range(len(index))] for item in here]
#//DISTANCE//
x_ = [[item[b][1] for b in range(len(index))] for item in here]
y_ = [[item[b][2] for b in range(len(index))] for item in here]
z = [list(zip(x_[a],y_[a])) for a in range(len(x_))]
dis = []
for aa in range(len(poss)) :
tempor=[]
for i in range(len(index)-1):
firstpoint = z[aa][i]
secondpoint = z[aa][i+1]
distance = round(np.linalg.norm(np.array(secondpoint)-np.array(firstpoint)))
distance = int(distance)
tempor.append(distance)
dis.append(tempor)
#//ARRIVAL TIME//
#Arrival time is the sum of the pv distance.
arrival = []
for v in range(len(poss)):
forone = [0,dis[v][0],]
for r in range(len(index)-2):
sumz = dis[v][r+1] + forone[r+1]
sumz = int(sumz)
forone.append(sumz)
arrival.append(forone)
#//DELAY//
delay=[]
for d in range(len(poss)) :
tempo=[]
for q in range(len(index)):
v=arrival[d][q]-due[d][q]
if arrival[d][q] <= due[d][q]:
tempo.append(0)
else :
tempo.append(v)
delay.append(tempo)
#//ORDER//
#goal is to find the right order that minimizes the delay for two larger instances.
total = [sum(x) for x in delay]
small= min(total)
final=here[total.index(small)]
print(small)