two opt inversion
Уважаемые коллеги, добрый день Нужен алгоритм для решения TSP - 2-opt
Подскажите пожалуйста или алгоритм решения задачи или где можно почитать.
Поиск в гугле не дает нормального описания или я не там ищу.
У меня уже есть построенный маршрут по городам. Теперь нужно данный маршрут прогнать 2opt inversion, т.е. оптимизировать уже имеющийся. Написал программу, но она работает не так как нужно, поэтому нужно изучить теорию. На сайте https://tspvis.com/ нашел код (javascript ???) не все понимаю , что делает код , а мне нужна однозначность
const twoOptInversion = async path => {
path.push(path[0])
let best = pathCost(path)
let swapped = true
while (swapped) {
swapped = false
for (let pt1 = 1; pt1 < path.length - 1; pt1++) {
for (let pt2 = pt1 + 1; pt2 < path.length - 1; pt2++) {
// section of the path to reverse
const section = path.slice(pt1, pt2 + 1)
// reverse section in place
section.reverse()
// replace section of path with reversed section in place
path.splice(pt1, pt2 + 1 - pt1, ...section)
// calculate new cost
const newPath = path
const cost = pathCost(newPath)
if (cost < best) {
// found a better path after the swap, keep it
swapped = true
best = cost
self.setBestPath(newPath, best)
} else {
// un-reverse the section
section.reverse()
path.splice(pt1, pt2 + 1 - pt1, ...section)
}
}
}
}
}
Задача заключается в поиске оптимального маршрута -классическая задача коммивояжера. Я нашел маршрут с помощью жадного алгоритма, используя в качестве отправной точки перебор всех вершин и выбрав самый лучший путь. А теперь хочу прогнать этот "оптимальный" путь с помощью 2opt алгоритма, но не очень понимаю алгоритм его работы, поэтому и прошу помочь с алгоритмом (такой как на сайте по ссылке). Программа написана на VBA, но работает некорректно. Приложил сам файл. файл эксель с реализацией