У Черны это "2 в 1", и делается параллельно за одну часть.
Чудо-бозоны пробежали от источника S до детектора D, и путь построен и мусор отсеян.
Расчет окончен!

Ну всё ты правильно понял!
Там заморочка в том, что количество необходимых для решения задачи бозонов, и, следовательно,
энергия для их генерации, растут экспоненциально.
И если ты ещё не начал копать котлован под электростанцию для снабжения энергией генератора бозонов, то это сильно задержит поиск решения задачи коммивояжера. 
Статью Черны я не читал, но осуждаю!
Мне, почему-то, кажется, что задачу коммивояжера, ответ в которой, для заданных мною ранее условий  будет:
"Кратчайший маршрут : А - В - С - А"
и которая требует экспоненциального  времени решения,
Черны изначально подменил на задачу, ответ в которой будет:
"Кратчайший маршрут имеет длину 700 километров",
и которая изначально решается за полиномиальное время...

Отредактировано Лукомор (2018-09-14 19:36:23)

Мьечно!

Зачем тебе четыре шпалы?!

на петлицу

"Решение линейной задачи коммивояжера за линейное время".
(с) Лукомор
     независимый исследователь.

Эпиграф:
   "Итак-а!" (с) Столбняк

Вступление:
     
     Сразу оговорюсь, что я решаю незамкнутый вариант
симметричной геометрической задачи коммивояжера.
Это означает, что маршрут коммивояжера начинается в одном городе,
проходит все остальные города ровно по одному разу,
и заканчивается в каком-нибудь другом городе,
без возврата в город, где маршрут начался.
При этом, расстояния "туда" и "обратно" между любой парой городов
равны между собой, а дороги между всеми городами являются прямыми линиями.
Следует отметить, что геометрическая задача коммивояжера с евклидовой метрикой
всегда будет одновременно и метрической,
поскольку в этом случае относмтельно длин всех рёбер выполняется неравенство треугольника.
В своем решении я нигде не использую ни манхэттенскую (квартальную метрику)
ни максимальную метрику.

Таким образом,
я НЕ решаю:
-замкнутый вариант симметричной геометрической задачи коммивояжера;
-замкнутый вариант асимметричной геометрической задачи коммивояжера;
-незамкнутый вариант асимметричной геометрической задачи коммивояжера;
Я также не решаю никакой из вариантов обобщенной задачи коммивояжера.

Постановка и решение задачи:
   В отличие от классической ненаписанной статьи проф.Белопушистого,
где автор предлагает решать задачу коммивояжера методом генерации
максимально возможного количества траекторий, которые не могут являться
маршрутами коммивояжера (т.наз. "мусорных" траекторий),
с последующим их исключением из рассмотрения,
наш оригинальный метод заключается в максимальном исключении из рассмотрения,
еще на предварительном этапе  решения задачи,
тех разрешенных маршрутов, которые, по тем или иным признакам,
не могут, в принципе, быть кратчайшими.
После максимального исключения таких маршрутов,
решение задачи коммивояжера становится тривиальным.
Выявление и исключение таких разрешенных маршрутов на предварительном  этапе решения задачи возможно, прежде всего,
исходя из геометрической формы графа расстояний, составленного на основании данных из условия задачи.

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

Задача коммивояжера проще всего решается, когда все N городов,
которые должен посетить коммивояжер, лежат на одной прямой линии".

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

Таким образом, для Линейной Задачи Коммивояжера с количеством городов равным N,
общее количество арифметических операций сложения, необходимых для нахождения
кратчайшего пути равно (N-1) и линейно растет с ростом N.
Для нахождения самого кратчайшего маршрута необходимо выполнить только сортировку расстояний от каждого города до остальных городов.
Два города с максимальным расстоянием между ними будут начальным и конечным на кратчайшем маршруте,
остальные будут иметь наименьшие расстояния до соседних с ними городов вдоль всего маршрута.

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

Для проверки решения данные из условия задачи были внесены
в матрицу расстояний онлайн калькулятора для задачи коммивояжера:
https://math.semestr.ru/kom/index.php

В результате работы калькулятора был получен результат:

Калькулятор считает только замкнутые маршруты.
Чтобы получить кратчайший незамкнутый маршрут, нужно исключить самый длинный отрезок,
в данном случае (6,1)=FA, получится незамкнутый маршрут  (1,2), (2,3), (3,4), (4,5), (5,6) длиной 700.
Результаты расчета совпали (только вручную быстрее...    ).

Отредактировано Лукомор (2018-09-16 11:03:50)

там нечего обсуждать
все понятно

вот если б с какой нибудь заебучинкой
это да

лично я
отметаю линейность
и не потому
что прям
ключевым словом в названии задачи ЗАДАЧА КОММИВОЯЖЕРА
является не слово ЗАДАЧА
на красный плащ которой мы мечемся с чувством положительного содрогания
а слово КОММИВОЯЖЕРА -

нуу
как бы вам обьяснить

путь может быть коротким или длинным
или его не может быть вообще

идеальный вариант
кратчайший
не вставая с места Сыт, пьян и нос в табаке

Это как задача водолаза
задача мясника
задача боксера

А осень еще не кончилась.

Приложение №2. к "Решению линейной задачи коммивояжера за линейное время".

Задача №2.

В рассматриваемой в этом приложении задаче, сохранены расстояния между соседними городами,
а именно:
AB=100, BC=120, CD=140, DE=160, EF=180.
Однако каждый последующий отрезок повернут по часовой стрелке, относительно предыдущего.
Таким образом углы:
ABC=BCD=CDE=DEF=150 (градусов).
Соответственно все расстояния между городами, за исключением соседних городов,
будут меньше чем в линейной задачи, и вычисляются из соответствующих треугольников.
После такого преобразования задача перестает быть линейной, и становится обычной задачей коммивояжера.

Условие задачи (Граф и матрица расстояний).

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

Кратчайшие замкнутые маршруты:

A - B - C - D - E - F - A       
Длина пути = 100 + 120 + 140 + 160 + 180 + 530,06 = 1230,06

A - F - E - D - C - B - A
Длина пути = 530.06 + 180 + 160 + 140 + 120 + 100 = 1230,06

Кратчайшие незамкнутые маршруты:

A - B - C - D - E - F       
Длина пути = 100 + 120 + 140 + 160 + 180 = 700
A - F - E - D - C - B - A
Длина пути = 180 + 160 + 140 + 120 + 100 = 700

Кратчайшие незамкнутые маршруты получаются исключением из кратчайшего замкнутого маршрута исключением самого длинного звена.

Решение задачи методом ветвей и границ с помощью онлайн-сервиса "Задача коммивояжера".

Матрица расстояний:

Результат расчета:

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

Отредактировано Лукомор (2018-09-16 18:08:09)