Расширенный поиск  

Новости:

Автор Тема: Задача коммивояжера  (Прочитано 3197 раз)

0 Пользователей и 1 Гость просматривают эту тему.

FFFF

  • Новичок
  • *
  • Оффлайн Оффлайн
  • Сообщений: 28
  • ОЗТ: 175
Задача коммивояжера
« : Июль 03, 2009, 11:54:48 »

Господа, давно интересно было, а есть ли какая навигационная программа, в которой реализовано решение задачи коммивояжера? Т.е. указывается несколько точек и строится кратчайший маршрут, проходящий через все точки.
« Последнее редактирование: Июль 03, 2009, 11:55:01 от serg »
Записан
 

M.F.

  • Administrator
  • Легенда
  • *****
  • Спасибо: 108 раз(а)
  • Оффлайн Оффлайн
  • Сообщений: 8.440
  • ОЗТ: 423975
Задача коммивояжера
« Ответ #1 : Июль 03, 2009, 12:06:03 »

Так это почти все программы в определённом виде умеют. Я так понял речь о маршруте с указанием в ручную промежуточных точек.
Записан
Координатор внешних узлов карт проекта rusnavi.org, также в недалёком прошлом один из координаторов проекта ASNP.
Считаешь что твой родной населённый пункт плохо обрисован или хочешь рисовать карты в качестве хобби для себя и людей, тогда напиши мне в личку!
 

chauchau

  • Новичок
  • *
  • Оффлайн Оффлайн
  • Сообщений: 30
  • ОЗТ: 1454592
    • www.hr-v.ru
Задача коммивояжера
« Ответ #2 : Июль 03, 2009, 12:53:41 »

я думаю, что задача такова:
1. задаются точки старка и финиша
2. задаются в произвольном порядке несколько точек на карте
задача устройства на выходе выдать маршрут, начинающийся с точке старта, оканчивающийся в точке финиша и проходящий через все точки на карте в наиболее оптимальном порядке (по времени или длинне маршрута)

то есть, цель не только в кратчайшем расстоянии между точками, но и в оптимальной расстановке точек на маршруте
Записан
 

luckybeggar

  • Новичок
  • *
  • Оффлайн Оффлайн
  • Сообщений: 10
  • ОЗТ: 12759
Задача коммивояжера
« Ответ #3 : Июль 03, 2009, 13:51:46 »

Такое может программка GarminMobilePC при работе с будущем маршрутом.
Указываются место старта, финиша,  промежуточные точки маршрута.
Записан
 

FFFF

  • Новичок
  • *
  • Оффлайн Оффлайн
  • Сообщений: 28
  • ОЗТ: 175
Задача коммивояжера
« Ответ #4 : Июль 03, 2009, 14:46:33 »

garmin moblie pc под рукой не было. Попробовал в garmine mobile xt. Проходит промежуточные точки в том порядке, в котором они задавались. никак не оптимизирует.
Записан
 

dr.b

  • Легенда
  • ******
  • Спасибо: 3 раз(а)
  • Оффлайн Оффлайн
  • Сообщений: 1.943
  • ОЗТ: 209797
  • Кемерово
Задача коммивояжера
« Ответ #5 : Июль 03, 2009, 23:50:46 »

Так и есть. При планировании маршрута последовательность прохождения точек определяет пользователь. У него голова больше. А навигатор прокладывает между ними оптимальный путь.
Записан
 

vv

  • Житель
  • ****
  • Оффлайн Оффлайн
  • Сообщений: 269
  • ОЗТ: 14483
Задача коммивояжера
« Ответ #6 : Июль 04, 2009, 09:50:56 »

FFFF, тебя не понимают ... тут собрались практики навигации, а не разъездной торговли и даже не прикладной математики.
Интересно, что есть такой вид спорта, где необходимо решать слегка модифицированную задачу коммивояжера: "ориентирование по выбору", или его частный случай - рогейн. Но, поскольку там, я подозреваю, использование навигаторов запрещено, то производители и не закладывают такие функции в приборы :)
Собственно, нет проблемы сделать такую внешнюю утилитку в дополнение к навигационной программе с известным форматом хранения карты и точек, но готовая она вряд ли есть, ибо никому не нужна (1) и на реальных данных будет работать непомерно долго (2) если нужно именно точное решение.
Записан
 

SM

  • Administrator
  • Легенда
  • *****
  • Спасибо: 3 раз(а)
  • Оффлайн Оффлайн
  • Сообщений: 2.019
  • ОЗТ: 109077
  • г. Томск
Задача коммивояжера
« Ответ #7 : Июль 04, 2009, 20:41:23 »

Цитата: vv

...есть такой вид спорта ... "ориентирование по выбору", или его частный случай - рогейн...


В молодости занимался спортивным радиоориентированием, или как его тогда называли "Охота на лис"
Там надо было используя коротковолновой приёмник с поляризованой антенной найти спрятаные в лесу радиопередатчики. Из дополнительных материалов можно было использовать только карту местности.

Так готовили поисковиков диверсантских групп или партизанов (слова террорист тогда ещё не употребляли)  ;)
Записан
Ericsson T10s -> Nokia 3310 -> Siemens A52 -> Siemens M55 -> Siemens M65 -> Nokia 6630 -> Nokia N73 -> Samsung Galaxy SII -> Samsung Galaxy Note II
Автомобильная навигация: HP iPAQ hx4700 -> Mitac Mio C725
 

andrey

  • Новичок
  • *
  • Оффлайн Оффлайн
  • Сообщений: 15
  • ОЗТ: 340
Задача коммивояжера
« Ответ #8 : Июль 05, 2009, 01:25:46 »

http://www.ingit.ru/articles/index.php?id=4  
транспортная логистика, вроде как для ББ, зайди почитай
Записан
 

FFFF

  • Новичок
  • *
  • Оффлайн Оффлайн
  • Сообщений: 28
  • ОЗТ: 175
Задача коммивояжера
« Ответ #9 : Июль 06, 2009, 09:50:36 »

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

serg

  • Дух форума
  • ******
  • Спасибо: 42 раз(а)
  • Оффлайн Оффлайн
  • Сообщений: 1.314
  • ОЗТ: 274862
Задача коммивояжера
« Ответ #10 : Июль 09, 2009, 23:51:06 »

Попробывал в GarminMobileХТ добавить 2 промежут очные точки к заданной финишной. Сначала маршрут проложила в порядки задания точек, но после того, как разрешил сортировку, то маршрут был перепроложен (хотя и не как мне надо, финиш оказался посередине) так, что между точками было минимальное расстояние поездки.
Записан
 

matahary

  • Новичок
  • *
  • Оффлайн Оффлайн
  • Сообщений: 2
Записан
 
 

Страница сгенерирована за 0.029 секунд. Запросов: 23.