Я пытаюсь спроектировать 2-opt локальную эвристику поиска для TSP в Java, но мой алгоритм, кажется, ошибочен. Учитывая ближайшую соседнюю цепь, как при входе, она каким -то образом усугубляет цепь. Мой код ниже. Что не так с моей реализацией? Местоположение [] Местоположение - это просто список узлов «График», каждый из которых имеет широту, долготу и расстояние расстояния между ним и другим узлом. < /P>
public HamiltonianCircuit execute(Location[] locations) {
long startTime = System.currentTimeMillis();
while (true) {
for (int i = 0; i < locations.length; i++) {
for (int k = 0; k < locations.length; k++) {
if (System.currentTimeMillis() - startTime >= 10000) {
return new HamiltonianCircuit(locations);
}
Location a = locations;
Location b = locations[(i + 1) % locations.length];
Location c = locations[k];
Location d = locations[(k + 1) % locations.length];
double distanceab = a.distanceBetween(b);
double distancecd = c.distanceBetween(d);
double distanceac = a.distanceBetween(c);
double distancebd = b.distanceBetween(d);
double change = (distanceab + distancecd) -
(distanceac + distancebd);
if (change > 0) {
locations[k] = a;
locations = c;
}
}
}
}
}
Подробнее здесь: https://stackoverflow.com/questions/136 ... ementation
