Я об этом сразу сказал, что большинство калькуляторов обрабатывают максимум 14 - 15 пунктов.

Отредактировано Лукомор (2019-10-01 07:51:05)

Нет такого алгоритма.
Метод ближайшего соседа: задан начальный пункт.
От него - находим ближайший пункт, если из больше одного - подбрасываем монетку.
Переходим по кратчайшему пути, и снова находим ближайший пункт, в котором еще не были.
И так далее N раз.

Метод термоусадки.
Сразу очерчиваем внешний периметр.
Это заготовка будущего маршрута. 
16 отрезков сразу.
И 9 пунктов внутри периметра.
Находим детуры каждого отрезка периметра с каждым свободным пунктом.
Таблица 16х9.
В ней находим минимальный элемент.
Отрезок, который ему соответствует - убираем, строку из таблицы вычеркиваем.
Пункт, который этому значению соответствует, соединяем с концами удаленного отрезка.
Получилось два новых отрезка, и этот пункт между ними.
Столбец в таблице вычеркиваем, Две новых строки добавляем.
Отрезков маршрута стало на 1 больше, свободных пунктов - на 1 меньше, таблица 17х8.
Продолжаем, пока не закончатся свободные пункты,  таблица станет 25х0, соответственно, сам собой проложится маршрут из 25 отрезков.

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

Нет. Это верно только для наименее эффективных методов.
Метод ближайшего соседа действительно требует расчета для  N начальных точек маршрута.
Метод ветвей и границ, для N(N-1) возможных вариантов нумерации вершин.
Два метода лукомора от выбора начальной точки не зависят никак.

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

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

Метод ближайшего соседа лажает по полной.
Я его 25 раз запустил, с каждой точки, -
и ни одного варианта без явных петель.
Вот самый короткий из 25, он начинается от пункта №13 вниз:

И он не кратчайший ни разу.

Но до кратчайшего его можно допилить вручную, просто распутав петлю:

Отредактировано Лукомор (2019-10-01 19:06:05)

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

найти кратчайший маршрут через 4 точки из этих 20.

И не является ли это знание кратчайшего маршрута через 20 точек
(кстати, он далеко не единственный возможный)
бесполезным,
подобно тому, как является бесполезным знание длины кратчайшего маршрута в алгоритме им. Шарпера?

Отредактировано Лукомор (2019-10-02 06:18:19)

Ко мне какие претензии?!
Это онлайн калькулятор...
Пропетлял и пропетлял, это не наказуемо...
Может он пролетел над точкой, мы этого не знаем.

Сделаем, конечно сделаем!
Только вот как мы это сделаем?!
Мы этого пока не сделали и в первом случае, напоминаю, что алгоритм запустил шикарную петлю.
А то что я довернул его в рукопашную - это не алгоритм, это естественный интеллект! 

Который из них недоработанный?

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