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

АВ = 100
ВС = 120
CD = 140
AC = 156,2
BD = 184,4
AD = 126,5

Это полное условие задачи коммивояжера.
Приступим к ее решению.

Отредактировано Лукомор (2018-12-28 21:55:33)

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

Что же интересного можно заметить в этих трех чертежах?!

Прежде всего, каждый график имеет восемь имен, все - уникальные.
Чтобы не путаться, первый граф буду обозначать всегда ABCDA - от буквы А по часовой стрелке. 
А второй и третий, соответственно, от буквы А перестановкой пары букв: ABDCA и ACBDA.
Это, кстати, интересная особенность:
перестановкой пары городов получаем другой гамильтонов цикл,
то-есть, найдя любой полный замкнутый цикл, перестановками пары соседних городов будем получать все время новые и новые циклы.
Это нам в дальнейшем пригодится...

Это - Самсунг: то гнутый монитор, то гнутый телевизор, то гнутый телефон... 

Еще одна интересная особенность.
Я здесь перечислю сейчас все 12 незамкнутых маршрутов, причем в левом столбце будут шесть самых коротких в возрастающей  последовательности,
а во втором столбце шесть самых длинных в убывающей последовательности.
В правом столбце будет сумма  двух соседних чисел.
Эта сумма постоянна, и равна сумме всех шести отрезков.
$$S= AB+AC+AD+BC+BD+CD = 827,1$$

CBAD=346,5            ACDB=480,6            S=827,1
ABCD=360,0            BDAC=467,1            S=827,1
BADC=366,5            ACBD=460,6            S=827,1
ADCB=386,5            CABD=440,6            S=827,1
BACD=396,2            ADBC=430,9            S=827,1
BCAD=402,7            ABDC=424,4            S=827,1

135 градусов, поехали!

Всё аналогично.

Исходные данные:

Полное условие задачи коммивояжера:

Здесь:
AB=100
BC=120
CD=140
AC=203,4
BD=240,3
AD=291,1

И сумма всех шести отрезков:

$$\large S=100+120+140+203,4+240,3+291,1=1094,8$$

Первый гамильтонов цикл ABCDA=651,1

Второй цикл ABDCA=683,7

Третий цикл ACBDA=854,8

Отредактировано Лукомор (2018-12-28 21:56:17)

А теперь сравниваем, что изменилось при увеличении пары углов с 90 до 135 градусов.
Вот два чертежа:

Три отрезка не изменились, ибо таковыми я их задал:
AB=100
BC=120
CD=140.
длины еще трех отрезков увеличились:
AC= 156,2 ==> 203,4
BD= 184,4 ==> 240,3
AD= 126,5 ==> 291,1

Особенно сильно выросла длина четвертой стороны AD,
более чем в два раза, или на 164,6 в абсолютных цифрах.
Диагонали подросли гораздо скромнее:
AC на 47,2
BD на 55,9.
То-есть даже в сумме две диагонали дали прирост 103,1.
Это меньше, чем одна сторона АD.
Это повлияло прежде всего на те два цикла, в которые входит эта сторона.

Цикл ABCDA увеличился на эти самые 164,6.

Еще сильнее вырос цикл ACBDA, который и так был самый длинный.

В этот цикл входят и обе диагонали, и сторона AD.

А вот цикл ABDCA увеличился не на много, только на прирост двух диагоналей, поскольку сторона AD в этот цикл не входит.

В итоге, самый длинный цикл (синий) увеличился значительно больше других.
Кратчайший цикл (красный) увеличился сильно, но остался кратчайшим.

Самое интересное поведение у зеленого цикла.
Он был намного длиннее красного, и только лишь чуть короче синего.
Он увеличился меньше , чем два других, и теперь он значительно короче синего, и лишь немного длиннее красного.

Ситуация поменялась радикально, и теперь у нас суперфинал:
Красный цикл против зеленого.
Синий безнадежно отстал.

Пока красный опережает в соревновании на звание кратчайшего цикла, но у зеленого лучше динамика.
Ох, чувствую, решать будет фотофиниш. 

Отредактировано Лукомор (2018-12-28 23:47:48)

С лицом серьезного Шурика, и в костюме Гордона Фримена из ХалфЛайфа...

Ибо изначально аватарка моя была с несколько другим лицом, вот такая:

И была она довольно долго.
До того момента, когда инопланетянин unreal

пересадил голову Шурика на туловище Гордона Фримена...
Без наркоза...

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

Итак, пристегните ремни, ПОЛЕТЕ-Е-ЛИ-И-И!!!
Линейный вариант, четыре города вдоль одной прямой.

Расстояния:
АВ = 100
ВС = 120
CD = 140
AC = 220
BD = 260
AD = 360

Снова три гамильтоновых цикла:

ABCDA = 720

ABDCA = 720

ACBDA = 960

Теория сильна своей предсказательной силой.

Как мы и предположили ранее, синий цикл снова стал самым длинным, причем отрыв еще более увеличился.

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

Я завтра (сегодня уже), прежде чем двинуться от 90 градусов в другую сторону, в сторону нуля,
рассмотрю, казалось бы, постороннюю небольшую задачку, которую я на днях придумал,
и которая наглядно показывает  роль и значение углов в решении задачи коммивояжера.

Отредактировано Лукомор (2018-12-29 01:58:31)

Уже никто ничего не хотел!