#p96670,лукаш написал(а):а меня стращал
что мол в каждый город разрешается входить единожды (((
а когда он идет обратно он и В и С заходит повторно
и не надо про транзит
Стращать вас таких не перестращать!
Я уже тут распин овыв ался,
и про проблему эту рассказывал,
и как я ее обошёл аккуратно.
Действительно, это большая проблема.
Когда я увеличиваю или уменьшаю углы между соседними участками маршрута в интервале
от 0 до 180 градусов, в пределе, в крайних точках этого интервала города выстраиваются
в одну прямую линию.
Конечно, можно просто выкинуть эти крайние случаи,
и рассматривать интервал углов от 1 до 179 градусов,
в котором уже всё чинно - благородно, если бы не одно большое НО.
Даже два больших НО-НО.
Во-первых этот случай интересен сам по себе.
Там получается, что единственный кратчайший путь в окрестности конца интервала
остаётся кратчайшим и при этом предельном значении.
Но, именно в пределе когда вся ломаная линия уже выпрямилась, вдруг оказывается,
что для четырех городов сразу два маршрута, этот и еще один, становятся равными по длине.
Соответственно, для пяти городов их будет четыре - один и еще три.
Для шести городов -этот и еще четыре и три, всего восемь...
Для N городов - 2 в степени (N-3).
Во-вторых, могут быть еще случаи,
когда три или более городов окажутся на одной прямой линии чисто случайно.
Я такой случай изучил сразу после линейного, и случая выпуклого многоугольника.
Здесь пока не выложил, но если доживу, обязательно выложу.
Для примера:
Пять городов, три из которых образуют треугольник,
а два других лежат на одной или двух сторонах этого треугольника.
При такой замысловатой конфигурации,
кратчайший замкнутый путь всё равно будет проходить по периметру треугольника.
Действительно, если города стоят на одной линии, то АC = АВ + ВС.
И действительно, в каждый город нужно зайти и выйти не более одного раза.
Моё решение проблемы.
1. Коммивояжер передвигается в этом случае на вертолёте, и попадает из города А в город С минуя город В, но не заходя в него.
2. Альтернативный вариант - коммивояжер двигается пешком, на подводе, на автомобиле,
но вокруг каждого города есть объездная кольцевая дорога, по которой можно миновать город, не посетив его.
Даже лучше будет не так.
Трасса от А до D - прямая, безо всяких кольцевых, а города В и С чуточку в стороне от трассы, ещё лучше - прилегают к ней в одной точке.
А посещением города считать только если с трассы свернул, типа в центр города.
3. Или коммивояжер едет транзитным поездом из А в С, который проходит через В, но без остановки.
Так понятно?!
Отредактировано Лукомор (2019-01-16 01:59:39)
ошибаетесь
