" Я тут порисую... немножко..."
(с) Лукомор 
Мы остановились на том моменте, когда я распутал для небольшого учебного примера
все явные петли, и из 17 маршрутов осталось 11 уникальных.

Далее я ввел и проиллюстрировал совершенно новое понятие: "скрытая петля",
и показал, как такие петли детектируются и распутываются.

Сейчас я выложу кликабельные превьюшки результатов детектирования скрытых петель для всех 11 маршрутов,
отсортированных в порядке возрастания длины маршрута.
Черным цветом показан сам маршрут,
Зеленые тонкие линии - соединяют пункты маршрута через один, там где они не пересекают отрезки маршрута.
Красные тонкие линии, соединяют пункты маршрута через один, и пересекают участки маршрута, выделенные жирными красными линиями.
Это пересечение показывает наличие    скрытой петли на этом участке.
Вот все 11 маршрутов:











Получилось, что скрытые петли имеют 3, 7, 10 и 11 маршруты.

Отредактировано Лукомор (2019-08-17 08:06:37)

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

Это естественно.
Полный перебор дает абсолютно лучший результат, но, зачастую, за не приемлимое время.
А эвристика, она сильно разная...
Я вот улучшил результат по конкретной предложенной задаче коммивояжера, а не могу сказать, что он абсолютно лучший.
А полный перебор - это 17!  >300000000000000 вариантов

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

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

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

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

Если вычислить 4 участка маршрута, пусть и разрозненных, то действительно останется 13! > 6000000000.
Много? да!
Но это позволит откинуть 99, 999% из всех возможных вариантов.
Остается перебрать 0.001%.

Отредактировано Лукомор (2019-08-17 12:52:23)

"Я тут порисую... немножко..."
(с) Лукомор 
Я сейчас готов рассказать о первом из двух изобретенных мной методов решения задачи коммивояжера.
Он появился, как это часто бывает, неожиданно, при рассмотрении совершенно иных вопросов.

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

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

К сожалению, самые известные из них : №1 и №2
работают с  количеством пунктов не более 14 и 15 соответственно.
Мне же нужно было решить задачу для 17 пунктов.

Я стал размышлять, как из 17 пунктов сделать 14, но так,
чтобы полученное для 14 пунктов решение можно было бы развернуть в решение для 17 пунктов
без существенной потери результата.

Первое, что мне пришло на ум:
Взять пункты, которые являются ближайшими друг для друга, и заменить их одним,
который будет находиться ровно посредине отрезка, их соединяющего.
Выбрав три пары таких пунктов, и заменив эти три пары на три таких "срединных",
лучше сказать "медианных", пункта, я получу задачу для 14 пунктов.
Решив которую на онлайн-калькуляторе я затем смогу, наверное, заменить каждый "медианный" пункт на пару исходных пунктов.
Полученный результат, поскольку каждый из пары пунктов является для другого ближайшим,
вроде бы не должен отличаться от того, как если бы онлайн-калькулятор решал задачу для 17 пунктов.,

Сказано - сделано!

Условие задачи не повторяю, я ее уже многократно здесь рассматривал.
Сначала я выбрал из матрицы расстояний для каждого из 17 пунктов ближайший к нему пункт.
Результат свел в табличку:

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

У меня получилось четыре пары таких пунктов, для которых одновременно пункт В является ближайшим к пункту А,
и пункт А является ближайшим к пункту В.
Для остальных пунктов характерно то, что пункт В является ближайшим к пункту А, но для пункта В существует пункт С, который находится ближе, чем пункт А.

Все эти отношения "ближайшести" я нанес на схему :

Зеленые "обоюдоострые" стрелки соединяют получившиеся пары "взаимно-ближайших" соседей.
Красные стрелки показывают на соседа ближайшего к данному.
Пункт №14 будет ближайшим для пункта №0, пункт №12 - ближайшим для пункта №14, а пункты №12 и №8 -ближайшими друг для друга.
И так далее.

Иными словами, изображенное на схеме можно описать так:

17 коммивояжеров одновременно стартовали из 17 городов.
Направление своего движения они выбрали по методу ближайшего соседа.
Оно показано стрелкой.
На схеме изображено то, что получилось,
когда каждый коммивояжер прошел первый участок своего маршрута
и оказался в городе, ближайшем к своему начальному.

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

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

Но...

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

Я решил узнать, куда я приду, если буду повторять придуманные мной правила снова и снова,
В пределе, если повторять объединение взаимно ближайших точек неоднократно, все пункты стянутся в один.
А потом можно будет  развернуть из одной точки обратно в 17, повторяя все действия в строго обратном порядке.
И у нас получится исходная схема но уже с кратчайшим маршрутом на ней.

Отредактировано Лукомор (2019-09-12 23:17:38)

Доктор-лектор еще... До кучи... 

Отредактировано Лукомор (2019-08-20 07:31:36)

Я продолжаю сокращать количество пунктов на плане.
Снова пересчитываю матрицу расстояний, выбираю ближайшие, для десяти оставшихся пунктов, нахожу взаимно ближайшие:

На этот раз нашлась всего одна пара.
Число пунктов сократилось до девяти.

Очередная итерация, четвертая, если не ошибаюсь:

Снова одна взаимно ближайшая пара.
Остается восемь пунктов:

Здесь я пропустил следующую по алфавиту букву I, из-за схожести с единицей,
и вновь получившийся медианный пункт обозначил буквой J.

Так, дальше пока стоп.
В заготовках нет следующего рисунка.
Щас наваяю,  и продолжим.
Но сначала выпью утренний кофе...

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

Не я такую задачу составил...

Но... мы сейчас, на следующей итерации, эту свастику - на куски...
Только с рисунком я тормознул, не сохранил, видимо, буду восстанавливать...

Отредактировано Лукомор (2019-08-20 08:19:23)