Поскольку ураган мыслей легко, как пушинку,
унес бегемота в новую Волшебную страну Оз,
продолжать коммивояжерскую тему в топике "Эврика эврической эврики"
стало окончательно невозможно.
Переезжаем сюда все, кого волнуют еще проблемы коммивояжеров.
Следует отметить особую заслугу Шарпера в возникновении этой темы.
За годы общения, Шарпер оказал огромное воздействие на систему моих взглядов,
поэтому два из трех краеугольных камней,
которые я полагаю в основание этой темы, этой гигантской пирамиды,
которую я здесь возведу,
и которая затмит своей мощью пирамиды египетские и финансовые, -
принадлежат Шарперу.
Третий камень, самый краеугольный, мой собственный.
Итак, в основании этой темы лежат три идеи.
!. "Наилучшим решателем задачи является физическая система, для которой она составлена"
(с) Р. Фейнман в пересказе Шарпера.
Физическая система, для которой составлена задача коммивояжера, - это карта автомобильных дорог, или железных дорог, или авиалиний, короче, дорожная карта.
Вот эта карта, а в более простом геометрическом варианте, геометрический чертёж,
и будет наилучшим решателем задачи коммивояжера.
2. Поскольку в качестве геометрической интерпретации дорожной карты мы здесь используем геометрический чертёж, я буду применять для решения задачи коммивояжера идею движения, которая в геометрии применяется теперь не часто.
Идея движения, или непрерывного преобразования, в геометрии, восходит еще к Евклиду. При доказательстве равенства треугольников, например, он говорил : "Наложим один треугольник на другой", - и это не означало у него то, что треугольник нужно вырезать из плоскости, и приложить его сверху к другому треугольнику. Отнюдь, нет!
Это были именно движения на плоскости - движения поступательные и вращательные, которые переводили одну фигуру в другую.
Когда-то давно я решил таким способом движения пару геометрических задач, одну совсем простую, другую, относительно сложную, когда-нибудь, на досуге, я здесь об этом расскажу.
Третьей геометрической задачей, которую я буду решать здесь и сейчас, используя идею движения в геометрии (буквально, это - кинематика), будет задача коммивояжера.
3. Третья идея, она опять же привнесена сюда Шарпером, это идея эволюции, сочетание наследования признаков, изменчивости, и естественного отбора.
Эту идею я уже применял в исходной теме следующим образом.
Наследственность у меня моделировалась неизменностью некоторых начальных условий от задачи к задаче.
Это были длины всего лишь пяти участков дорог между городами:
АВ = 100
ВС = 120
СD = 140
DE = 160
EF = 180.
Остальные 10 участков вычислялись в каждой задаче по известным пяти участкам, и четырем известным углам.
Изменчивость определялась изменением угла поворота последующего участка пути к предыдущему. Имеются в виду углы между известными участками пути: АВС, BCD, CDE,DEF. Остальные 56 углов между участками пути вычисляются по известным четырем углам и пяти сторонам.
Естественный отбор в этой задаче интерпретируется появлением новых "видов", качественно новых кратчайших маршрутов, при достижении некоторых критических углов поворота.
Я успел в исходной теме исследовать пять вариантов:
При углах поворота 0 градусов (линейный вариант),
30, 45, 60 и 68 градусов.
Здесь я планирую довести решение задачи коммивояжера до логического завершения.
Я предвижу что развитие метода, основанного на трех представленных выше идеях,
может дать решение задачи коммивояжера за 
шагов, то есть за полиномиальное время.
Отредактировано Лукомор (2018-09-25 11:08:16)
