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

Всё ж таки, попробую...

В качестве испытательного полигона я выбрал задачу, которую приволок сюда когда-то Шарпер с сайта Московского энергетического института.

http://twt.mpei.ac.ru/MCS/Worksheets/nva.xmcd

Там, среди прочего, есть пример с координатами 17 точек, между которыми нужно найти кратчайший маршрут, я его уже ранее здесь рассматривал:

Буду рассматривать этот пример в качестве базового и далее.
Там же есть онлайн калькулятор, который находит якобы кратчайший маршрут методом ближайшего соседа.
И сам метод ущербный, хотя и экстремально быстрый, и калькулятор кривобокий.

К калькулятору, собственно, претензия одна:
Когда наш коммивояжер приходит в точку, из которой  есть равные кратчайшие расстояния до двух или нескольких соседних точек,
программа весело выбирает точку с меньшим номером, и без оглядки ломится туда.
Как это выглядит на практике?
Если я выберу в качестве стартовой точки точку за номером  13, то коммивояжер бодро допетляет до точки с номером 15 (через точки 5, 6, и 4),
и встанет перед буридановым выбором: расстояния от точки №15 до точки №7 и до точки №8 равны между собой
и оба являются наименьшими из расстояний до не пройденных еще точек.
Наш не буриданов коммивояжер, естественно, выберет дальнейшее направление движения в точку №7, просто потому что 7 < 8...

И будет ему счастье, поскольку в таком случае он финиширует с результатом L = 463,194.
Это не лучший результат, но выше среднего.

А мы ему сделаем подляну: оставим все точки на тех же местах, но поменяем номера двух точек №? и №8.
Теперь из точки №15 коммивояжер направится в совершенно другом направлении, в новую точку №7', бывшую ранее №8.

В результате длина его нового маршрута увеличится до L = 570.702, и это наихудший возможный результат для данного метода и данных начальных условий.

Отредактировано Лукомор (2019-07-30 10:29:50)

Это только в плохих алгоритмах...

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

Гораздо больше претензий к самому алгоритму решения задачи коммивояжера по "Методу ближайшего соседа".

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

Вот как выглядит результат работы алгоритма
применительно к конкретному примеру для маршрута с 17 пунктами, приведенному выше.
(Пунктирной линией показан последний отрезок маршрута, по которому коммивояжер возвращается в исходный пункт).

Самый короткий маршрут получается, если начать движение с пункта №4, или с пункта №15, его длина составит
L=457.504.

Следующие по длине маршруты будут от пунктов №0 и №14.
Их длина равна L = 458.662.

Замыкает пятерку самых коротких маршрутов маршрут, стартующий с пункта № 7.
Его длина: L = 460.445.

Дальше идут маршруты стартующие с пунктов № 1 и № 13 (они одинаковые).
Длина каждого из них равна L = 463.194.

Отредактировано Лукомор (2019-08-03 16:45:14)

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

Отредактировано Лукомор (2019-08-04 22:14:26)

Не по этой причине отвергаем!
А по причине, что в объявлении "Секретный код для связи" начинается на 09, а мой - с 06... 

Отредактировано Лукомор (2019-08-05 09:05:29)

Следующий шаг, который необходимо сделать при анализе полученных выше маршрутов,
мне видится в том, чтобы забыть на время, каким методом они получены, и о направленности маршрутов,
и рассматривать полученные фигуры, просто как замкнутые 17-угольники, иногда имеющие самопересечения.
Мы выяснили, что у всех этих семнадцати 17-угольников 6 сторон совпадают,
я их сейчас нанесу на план местности...

Мы выделили то общее, что есть в каждом маршруте.
Все остальные 11 сторон 17-угольника будут варьироваться от маршрута к маршруту.

Еще более общее свойство всех 17 маршрутов заключается в том, что отрезок 4-15 во всех 17 маршрутах соединяется с отрезком 5-6,
а отрезок 14-0 всегда соединяется с отрезком 12-8.
Других таких пар нет.
Более того, отрезок 4-15 всегда соединяется с отрезком 5-6 строго из пункта №4, и никогда - из пункта №15.
То-есть, во всех 17 маршрутах есть либо отрезок 4-5, либо 4-6, но никогда нет 15-5 или 15-6.
Аналогично, всегда есть 14-8 либо 14-12, но никогда - 0-8, либо 0-12.
С учетом этого наблюдения таблицу для сравнения маршрутов удобно переделать так, чтобы она начиналась  для всех маршрутов с пункта №4, затем сразу пункт №15,
и заканчивалась либо  последним пунктом №5, при этом предпоследним будет пункт №6, либо наоборот, последним пунктом №6, а предпоследним -пункт №5.
Возможен второй вариант: все маршруты начинаются с пункта №14 и сразу за ним пункт №0, а заканчиваются пунктом  №12, либо пунктом №8.
Других вариантов нет.

Я выбрал последний вариант - все маршруты привести к виду: стартуем с пунктов 14 и 0, финишируем в пункте 12, либо 8.
Получилась новая таблица, в которой более наглядно различие между вариантами маршрутов, найденных методом ближайшего соседа.

Жирная подчеркнутая цифра в каждой строке, пункт с которого начинался маршрут в исходной таблице.

Отредактировано Лукомор (2019-08-08 11:38:34)