Итак, суть вопроса заключается в следующем.
Для первичного ознакомления с проблемой коммивояжера я использовал методику,
которую Шарпер обозвал "складным метром".
Она заключалась в том, что для выбранного количества населенных пунктов N,
я фиксировал расстояния между N-1 пунктами, а углы между отрезками маршрута менял синхронно на одинаковый угол.
Этот метод дает наглядное представление о том, как зависит решение от формы исходного полного графа,
но ничего не говорит о способе нахождения кратчайшего пути... Проехали!
Тогда я решил рассмотреть простейшие графы с небольшим количеством пунктов.
Для трех пунктов, как ни крути, получится один цикл, точнее два цикла по формуле N!=2!=2,
но эти два цикла будут отличаться только направлением обхода - \по и \против часовой стрелки.
В общем случае получается треугольник, а кратчайший, он же длиннейший, путь будет равен периметру треугольника.
Это отправная точка нашего исследования...
Теперь зафиксируем три пункта, и зададимся следующим вопросом.
Если три пункта зафиксированы, а четвертый пункт мы можем двигать по плоскости, то
как положение четвертого пункта будет влиять на выбор кратчайшего маршрута.
Иными словами, мы нарисовали на плоскости треугольник.
Теперь нам хотелось бы раскрасить всю плоскость в три цвета так,
чтобы любая точка, лежащая в секторе своего цвета, давала бы тот же кратчайший путь,
что и любая другая точка из этого сектора.
Для выпуклых четырехугольников ответ уже известен apriori: кратчайшим путем будет периметр четырехугольника.
Я зафиксировал на плоскости три пункта А,В,С.
Стороны получившегося треугольника я продолжил за вершины вовне треугольника.
Теперь, если я выбираю любую точку в красной области, например P' , то получится трапеция AСВP' с диагоналями AB и CP'.
Кратчайшим путем в этом графе с четырьмя вершинами будет его периметр.
Аналогично, любая точка в зеленой области даст трапецию АВСР'',
с кратчайшим путем по ее периметру, и любая точка в синей области даст четырехугольник ВАСР''',
и кратчайший путь будет также по периметру его.
У нас остались четыре не закрашенных области, одна внутри треугольника АВС,
и три вне его, но между продолжениями сторон треугольника
С ними дело будет обстоять несколько сложнее.
Но об этом я расскажу уже завтра, то-есть сегодня... 
Отредактировано Лукомор (2019-03-18 01:19:00)
