Задача коммивояжёра

[квит]

т.е. еще есть варианты - из 15 точки идти в 16, тогда может хвост быть
15 16 26 27 28 24 25 18 17 20 19 23 22 21

или из 15 идти в 17, тогда
15 17 16 26 27 28 24 23 25 18 19 20 23 22 21

[BOBA]

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

[Tytgrom]

Сообщение от квит

мой вариант - визуально примерно как то так

Вложение 43432


может правда в левом верхнем углу можно еще пооптимизировать

домой доеду, запущу программку

Блин, я лопухнулась. Неправильно оси дала. У меня нулевая точка верхний левый угол (ну т.е. я шла с запада на восток, потом спускалась южнее и следующий ряд)
1 2 3 4

2

3

4

У меня 17 пункт мешается. При чем по игре тоже. Он последний присоединяется

P1460591.JPG

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

[квит]

Сообщение от BOBA

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

ну, алгоритма универсального всё еще нет, есть группы алгоритмов, основанные на разных принципах, которые решают ЗК все с какой-то точностью... т.е. оптимальное решение могут и не найти, находят субоптимальное - близкое к оптимальному... это первое)))

во вторых, диспетчера тоже нормально решить не могут, особенно с ростом количества точек - это даже по примеру Тутгром видно, а когда точек больше...

вот к примеру, у нас в городе миллионнике доставка питьевой воды в бутылках - от 1000 до 3000 адресов в сутки надо доставить... собственно, проект возник, когда диспетчера перестали справляться... появилась потребность в автоматизации...)))

и в модель все эти особенности - пробки, заправки, пересменки, обед водителя на маршруте - тоже закладываются, есть норматив, например, на обед и есть допуск плюс-минус, который тоже учитывается, условно 30 мин обед +- 10 мин - с этим уже можно работать

ну и в третьих, к ЗК сводятся не только транспортные задачи, много еще какие есть, где пробок нету, а задачу решать уметь надо)))

[квит]

к задаче коммивояжера (ЗК) сводятся задачи:

- выполнение операций станком с чпу - например сверление отверстий в детали в определенных координатах, или пайка схем, - с минимальным суммарным путем перемещения привода станка

- есть промышленное оборудование, которое может выпускать несколько типов изделий, задача определения оптимальной последовательности выпуска изделий с минимальным временем переналадки оборудования - сводится к ЗК

- в биоинформатике

Секвенирование ДНК. Здесь города представляют собой фрагменты ДНК, а расстояние представляет собой меру сходства между двумя фрагментами ДНК

- планирование сеансов связи - в каком порядке связываться объектам, с целью минимизации интервала времени, когда произойдет связь каждый-с-каждым (например, спутники на орбите, тут уже динамическая задача, т.к. не все видят друг друга одновременно)

ну и еще куча всяких приложений из разных предметных областей)))

[квит]

Сообщение от Tytgrom

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

так это не принципиально, просто зеркально точки отразить, на расстояниях то это не скажется

[квит]

переделал картинку под оси

tsp_tytgrom2.PNG

еще вариант оптимального маршрута:

0 -> 2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 26 27 28 24 25 18 17 20 19 23 22 21 -> 0

[Tytgrom]

Спасибо. Попробую. Картинка хорошая получилась.

[квит]

а что за игра то хоть? и зачем там нужно учитывать длину маршрута?

[Tytgrom]

Игра Фаллаут -4. Учитывать длину маршрута на фиг не надо, но мне удобнее посещать поселения в определенном порядке (поселенцы обижаются, если к ним долго не приходить, ну и потом надо их одеть, что-то им построить, сами они только фермерствовать могут). По алфавиту неудобно - приходилось прыгать по всей карте. По порядку присоединения тоже. Поэтому я решила сделать последовательность по территориальному признаку (если нет перегруза, то я пешком иду, если с грузом, то телепортируюсь). Оптимизация моя личная блажь

Народ вообще без поселений играет, только воюет А я воюю ради ресурсов дя поселений ....