Чтобы плавно перейти от случая трех городов к случаю четырех городов,
выпишу в явном виде формулу для единственного замкнутого контура в случае трех городов.
По условию задачи, которую я здесь рассмотрел выше, маршрут представляет собой треугольник, в котором известны и постоянны две стороны
(обозначим их a и b) и угол γ между ними, который изменяется от 0 до 180 градусов.
Тогда третью сторону с, которая зависит от значения угла γ, можно найти по теореме косинусов:

А весь путь коммивояжера будет равен:

Минимальное значение длины этого пути будет при γ=0, когда третье слагаемое будет равно b-a (при b>a).
тогда весь путь будет равен :

L=a+b+b-a=2b

Максимальное значение будет при  γ=180 градусов,
при этом третье слагаемое будет равно b+a,
и длина пути составит:

L=a+b+b+a=2b+2a

При промежуточных значениях угла значение длины пути будет монотонно, но не равномерно, возрастать, с ростом величины угла.
И это все, что нужно знать о случае трех городов.

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

Так пока еще никакого перебирания-то и не было. 
Один вырожденный случай N=3 ничего не даёт для построения универсальных решений...
Вот сейчас посмотрим пристально на N=4...
а дальше будет видно.

Отредактировано Лукомор (2018-12-26 12:11:37)

Вот свежая новость про задачу коммивояжера как раз.
ИИ на марше...

https://m.habr.com/post/434236/

"Нейросеть с амёбой решили задачу коммивояжера для 8 городов"

Отредактировано Лукомор (2018-12-28 10:39:52)

Это логично, да!
Если дважды два - это стеариновая свечка,
то дважды три - бильярдный стол!
Почему нет?! 

/ представил ползающие шары 

Отредактировано Лукомор (2018-12-28 15:13:58)

По погоде, которая сегодня дождь и отвратительна, собрался я выложить быстренько иллюстрации для случая N=4, которые я полагал уже готовыми.
Внезапно оказалось, что они существуют только в тетради карандашом, а в компьютере я их не порисовал.
Что ж делать, буду рисовать и выкладывать по одному, что сильно задержит весь процесс...

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

Неизвестные стороны находим,
как обычно,
по теореме косинусов.

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

Известную величину угла я,
по аналогии со случаем  N=3,
обозначу γ,
а известные стороны:
АВ= а
ВС= b
CD= c.

Тогда из треугольника АВС по теореме косинусов найдем сторону АС:

$$\large AC=\sqrt{a^2+b^2-2ab\cos\gamma}$$

Из треугольника BCD найдем сторону BD:

$$\large BD=\sqrt{b^2+c^2-2bc\cos\gamma}$$

Теперь, точно так же, можно найти оставшуюся сторону АD,
из треугольника ABD по известной АВ, и уже найденной BD.
Правда нужно еще найти угол $$\large\angle ABD=\gamma-\angle CBD$$.
При этом угол СВD нужно было найти раньше, сразу после стороны  BD,
по той же теореме косинусов:

$$\large\angle CBD=\arccos{\frac{c^2+(BD)^2-b^2}{2b(BD)}}$$

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

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