Задача коммивояжёра

[BOBA]

Скажи, Квит. А ты в конторе или лично у себя какую то базу знаний ведешь? Ты ж поди не рядовой сотрудник, а уже задумываешься о трансляции опыта от кого то к кому то?

[квит]

Сообщение от BOBA

Скажи, Квит. А ты в конторе или лично у себя какую то базу знаний ведешь? Ты ж поди не рядовой сотрудник, а уже задумываешься о трансляции опыта от кого то к кому то?

интересно...)))

ну пока вживую передаем, молодым , при личном общении, а вот чтоб как то зафиксировать, даже не задумывался)))

а как это выглядит, что то типа вики? даже пока представить не могу, как опыт хотя бы одного человека, если он специалист широкого профиля , можно структурировать

[BOBA]

Конкретно у фирмы confluence

Да типа вики. И жира для задач

[квит]

Сообщение от BOBA

Конкретно у фирмы confluence

Да типа вики. И жира для задач

вики ведем, но это больше в разрезе проектов, а не в плане передачи опыта от спецов молодняку, поделись, если делали, как это выглядит

для задач использовали трелло, ее тоже атласиан перекупил, но пару месяцев назад они сказали, что из рф акаунты будут блокировать, поэтому постепенно переходим на кайтен, вроде отечественная разработка)))

[квит]

Сообщение от квит

в планах - запилить коммивояжера жадным алгоритмом, отжигом, генетическим)))

продолжаем...

"Жадный алгоритм" - идея простая, и для понимания алгоритма и для его реализации - "идём в ближайший непосещенный город"

На псевдокоде:
1. создаем два списка, в первом - посещенные города, начиная с начальной вершины, во втором - оставшиеся точки, из которых будем выбирать и включать в маршрут
Инициализация, в первый пишем вершина0, во второй остальные
listChoosePoints <- Point0
listRestPoints <- listPoints remove Point0

2. В цикле с кол-вом итераций numPoints-2
2.1 берем текущую точку - это последняя из первого списка
2.2 считаем расстояния от нее до всех из второго списка
2.3 находим минимум и соответствующую ему точку
2.4 включаем эту точку в первый список, исключаем из второго

3. После цикла во втором списке осталась одна точка, включаем ее в конец 1го списка

4. Считаем длину маршрута, из последней точки маршрута делаем еще возврат в точку0

[квит]

Алгоритм простой, но не оптимальный - сначала он ищет "локально оптимальные" решения, но на последней точке, или нескольких последних - возникает "плата за жадность" - когда вариантов выбора мало или совсем не остается, остаются длинные ребра в графе, которые вынуждены включать в маршрут

tsp3.JPG

[квит]

На тех же данных Алгоритм случайной перестановки пары вершин находит лучше решение

его длина маршрута - 99 условных километров против 118 у жадного алгоритма

tsp4.JPG

[квит]

Сообщение от квит

его длина маршрута - 99 условных километров против 118 у жадного алгоритма

причем этот результат можно еще улучшить - если развязать пересечение ребер между 2-12 и 13-0

это делает алгоритм 2-Opt
https://translated.turbopages.org/pr...org/wiki/2-opt

его смысл - развязать пересечение двух ребер, доказано, что такая перестановка всегда улучшает длину маршрута

т.е. из конфигурации
--A..B--
.. \/
.. /\
--C..D--

переходим в конфигурацию
--A----B--
--C----D--

[квит]

Сообщение от квит

причем этот результат можно еще улучшить - если развязать пересечение ребер

почему при перестановках этот вариант не находит - не могу пока понять, либо очень редкий вариант, и на него за заданное кол-во итераций не выходит, либо что-то накосячил в реализации, и поэтому на какие-то видимо граничные варианты не выходит

[Tytgrom]

Я бы в другую сторону закрутила. из 0 в 5 потом 2, а потом 13, далее против круга и из 12 возврат в 0

Потому что не люблю пересечений

ну или 2 - 12 - 13, а в 0 из 8