Есть такое замечательное выражение:
"За деревьями  леса не видеть !"
Как раз тот случай...

Я до сих пор рассматривал только выпуклые графы,
для которых кратчайший маршрут совпадает с периметром графа по определению.

Для любого такого графа с шестью вершинами будет всего два кратчайших замкнутых маршрута по Черны:
с обходом вершин "по часовой стрелке" и "против часовой стрелки"
(A-B-C-D-E-F-A и A-F-E-D-C-B-A).
Из них, отбрасывая самый длинный участок,
получаем два кратчайших незамкнутых пути по Шарперу:
"туда" и "обратно" (например, A-B-C-D-E-F и F-E-D-C-B-A).
Всего же разрешенных путей будет
6!=720,
что по Шарпру, что по Черны.

Из них:
Кратчайших замкнутых по Черны будет всего 12,
но все они совпадают, и отличаются лишь точкой, в которой начинается и заканчивается маршрут.
Поскольку в задаче Черны эта точка задается условием,
те десять, которые начинаются в остальных пяти точках мы не рассматриваем.
Также мы отбрасываем сразу те 708 разрешенных маршрутов, которые содержат хотя бы одну диагональ шестиугольника.

Кандидатов на кратчайший незамкнутый маршрут по Шарперу также 12.
Они получаются выбрасыванием одного участка пути из кратчайшего маршрута по Черны.
Кратчайший маршрут по Шарперу получится отбрасыванием
из кратчайшего замкнутого маршрута по Черны самого длинного участка.
Остальные 708 разрешенных маршрутов также a priori не могут рассматриваться кандидатами в кратчайшие,
поскольку содержат хотя бы одну диагональ шестиугольника.

Если к 720 прибавить еще 2405 "мусорных" маршрутов - получится классическая задача Черны.
А если к 720 прибавить 46 536 "мусорных" маршрутов - получится классическая задача Шарпера.
Правда, проблема отбрасывания "мусорных " маршрутов у Черны как-то решена,
а проблема отбрасывания "мусорных " маршрутов у Шарпера, пока, - не очень... 

Отредактировано Лукомор (2018-09-21 10:49:40)

Во мне проснулся перфекционист, и начал нудить, что по два графа на каждую задачу - это занадто,
что можно же объединить их в один, изобразив красными линиями кратчайший путь по Шарперу,
и, замкнув маршрут всего лишь одной черной линией, получить красно-черный маршрут по Черны.
Знаю я этого перфекциониста, он будет душу вынимать, пока я всё не поправлю, после чего уснёт опять... 
Так что, исправляюсь:
"Линейный вариант":

/И вот тут меня встретила засада:
Через кноповачку "Изображение"
никакие изображения не грузятся.
По окончании загрузки выдается
сообщение:"HTTP Error"/

Будем подождать! 
 

Да и хрен с ним...
"Линейный вариант":

Повернули все прямые на 30 градусов:

Еще на 15 градусов:

И еще на 15 градусов:

А решение осталось прежним...
Вот основные численные результаты расчетов (углы и расстояния) по всем четырем задачам, сведенные в таблицу:

Отредактировано Лукомор (2018-09-21 22:44:24)

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

уважаю
но лишнее надо убрать

Пробовал! Вообще не видно никакой картинки... 

/привычно

- "А чего сразу Лукомор?!"
(с) Лукомор 

"Потому что гладиолус!" (с) КВН. Уральские пельмени

Я нашел закономерность: Все выпуклые графы имеют кратчайший маршрут по периметру.
Теперь эту закономерность я довожу до абсурда, сгибаю периметр всё сильнее, пока одна из точек не уйдёт внутрь многоугольника.
Тогда кратчайший маршрут перестанет лроходить по периметру, он будет другой.
А какой?
Я уже знаю ответ на этот вопрос.
И вам всем расскажу.
Терпение!

А если изгибать змейку как попало,
то какая нибудь точка может сразу попасть внутрь многоугольника,
и получится ерунда, а закономерность никакая не получится...

Отредактировано Лукомор (2018-09-21 23:10:29)

таблички убрать !
картинки убрать !
голосом
ГОЛОСОМ
и убедительной интонацией !

Может, тогда мультик лучше в топик про нераскрытие темы?

Поэтому я прямо сейчас перехожу к задаче №5.
Мне теперь нужно, чтобы точка А, которая уже приблизилась в последней задаче к прямой BF,
совпала с этой прямой, так чтобы угол BAF стал развернутым (180 градусов).
Это будет предельный случай, нечто среднее между выпуклым и впуклым случаем.
Знаю, что во мне опять проснется перфекционист, но искать точное значение,
при котором все углы многоугольника, кроме угла BAF будут равны между собой, нудно и долго
(оно где-то между 115 и 120 градусами).
Поэтому я  сжульничаю! 
Я оставлю все углы, как в предыдущей задаче, равными 120 градусов,
а точку А просто пододвину до касания с прямой BF, при этом только углы CBA и EFA слегка уменьшатся,
и станут равны, соответственно, углам СBF и EFB из прошлой задачи, 105,08 и 74,92 градуса, соответственно.
То-есть, сделаю вот так:

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

При этом, сторона АВ останется равной 100 км., как во всех предыдущих задачах, для единообразия.
Снова рассчитаем расстояния между всеми точками,
и полученную матрицу расстояний скормим онлайн-калькулятору "Задача Коммивояжера"6

Довольно поурчав, калькулятор выплюнул ответ:

Кратчайшие пути будут выглядеть так:

Видим, что даже в этом, предельном, случае решение не изменилось.
По-прежнему, кратчайший маршрут пролегает по периметру многоугольника,
а диагональные участки пути всё еще не при делах.

После проведенной манипуляции кратчайший путь по Черны
A-B-C-D-E-F-A
уменьшился с 874,34 до 869,06 км.,
а кратчайший путь по Шарперу
F-A-B-C-D-E
с 694,34 до 689,06 км.

Отредактировано Лукомор (2018-09-22 12:15:50)

Схема Hyperloop им. Lookormore, тогда уж...
Чего мелочиться-то?! 

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

Это ведь дети могут просматривать. С интересом!

Детям развиваться надо!
Главное, чтобы не только с интересом, но и с пользой!!!

Отредактировано Лукомор (2018-09-23 12:40:41)

От скуки...

Действительно, чего это я? 
Захватил чужую тему, и почти раскрыл ее. 
Если тебя это напрягает, я могу прекратить "это делать"! 

Отредактировано Лукомор (2018-09-24 05:22:30)

Да, да, ждем продолжения