Одиннадцатый маршрут...

Здесь четыре точки пересечения, и пять отрезков, которым принадлежат эти точки.
Выкидываем эти пять отрезков.
Остается основная цепочка из 10 отрезков от пункта 9 до пункта 15,
два изолированных отрезка: 1 - 13  и  3 - 11, и два изолированных пункта №7 и №16 .

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

На самом деле, мы поторопились исключить отрезок 7 - 16, который мы определили, как базовый, видообразующий.

Если его вернуть, то окажется, что пункт 15 можно соединить, только с отрезком 13 - 1, причем только со стороны отрезка 13.
Все остальные варианты:
15 - 1 - 13, 15 - 7 -16, 15 - 16 - 7, 15 - 3 - 11, 15 -11 -3, дадут пересечение отрезков.
Точно также, после 15 -13 - 1, коммивояжер сможет двинуться только либо в 7 -16, либо в 16 - 7.
и в заключение, из 7 или 16, он может выбрать два маршрута: либо 3 -11 - 9, либо 11 - 3 - 9.

Итого получается всего два двоичных ветвления, всего 4 варианта.
если же мы пожертвуем отрезком 7 - 16, и будем заходить еще куда - то, после прохождения пункта 7, и до прохождения пункта 16,
то пункт 7 будет пройден либо вторым, тогда возможно лишь 2 маршрута без самопересечений:
сначала строго 15 - 7 - 13 - 1 - 16 а потом либо 16 - 11 - 3 - 9, либо 16 - 3 - 11 - 9;
либо пункт 7 будет предпоследним на единственном маршруте : 15 -13 - 1 - 16 - 3 - 11 - 7 - 9.
Любые другие маршруты от пункта 15 до пункта 9 будут иметь самопересечения.

Для начала замечаем, что сумма отрезков 16 - 3 - 11 - 9, длиннее, чем сумма 16 - 11 - 3 - 9.
Остается всего 4 маршрута для сравнения:
15 - 13 - 1 - 7 - 16 - 11 - 3 - 9
15 - 13 - 1 - 16 - 7 - 11 - 3 - 9
15 - 7 - 13 - 1 - 16 - 11 - 3 - 9
15 - 13  - 1 - 16 - 3 - 11 - 7 - 9.
В сравнении первого и второго маршрута отбрасываем первый, т.к.
1 - 7 - 16 - 11 длиннее, чем
1 - 16 - 7 - 11.
Точно так же, находим, что второй маршрут короче четвертого.
У нас осталось два наиболее маршрута - второй или третий.
Кто кого заборет?

И все-таки второй маршрут самый короткий!
Соединив все пункты так, как предписано вторым маршрутом, получаем еще и новый рекорд -
новый кратчайший маршрут, о существовании которого мы до сих пор не подозревали!

И, да! - отрезок 7 - 16 можно было не удалять, хотя на нем и было пересечение.
По поводу инверсий генома: сначала идет инверсия участка (11 - 3 - 13 - 1),
А затем, независимо друг от друга две инверсии: участка (7 - 16 - 1 - 13) и, собственно, участка (3 - 11).
Этих трех инверсий достаточно, чтобы распутать все петли в этом особо запутанном случае.

Отредактировано Лукомор (2019-08-09 17:06:15)

Я решаю ту задачу, которая сформулирована.
Веса узлов разные, но их сумма постоянна в данной задаче.
Если коммивояжер продаст в пункте А 30 единиц товара, а потом в пункте Б - 70 единиц, то это будет всего 100 единиц,
ровно столько же будет продано, если он сначала продаст 70 в пункте Б, а затем 30 - в пункте А.
А вот затраты коммивояжера мы в этой задаче пытаемся минимизировать, ребра имеют вес,
и сумма денег, потраченнах на проезд, пропорциональна сумме длин всех участков маршрута.

Да!
Когда ты заливаешь в бак бензин на заправке, ты решаешь задачу оператора АЗС.
Ведь это его выручка.

Отредактировано Лукомор (2019-08-09 15:25:29)

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

Отредактировано Лукомор (2019-08-09 16:55:50)

Не-не-не!

Всего лишь трилогия:
- "Тень коммивояжера"
- "Вторая тень"
- "Другая тень".

Публикуется эксклюзивно в научно-лирическом альманахе "Амальгама".
Тираж 100 000 просмотров.

Это слишком долго... Я столько не проживу... 

Когда были уже исчерпана заглавная тема "Тень коммивояжера",
я задался вопросом как нумеровать темы продолжения дальше.

Почти идеально, но уже не оригинально.

Следующая идея была порядковое числительное поставить перед словом "тень".

Тоже не плохо, но как-то однообразно.

Третья тема именовалась уже по другому принципую
Второе слово , естественно, "тень".
Первое слово произвольное прилагательное,
но первая буква следует в алфавитном порядке от темы к теме,
возможно с пропусками.
Так-что,
"Вторая тень"
букву " Г " я благоразумно пропустил. 
"Другая тень"
Следующая тема, которой, скорее всего, не будет, соответственно, будет называться:
"Еще одна тень". 

Отредактировано Лукомор (2019-08-10 08:20:57)