Подскажите как составить маршрут из 92 точек????

Итак ситуация.... по работе срочняком озадачили. Имеем 92 адреса, которые нужно обьехать и сфотографировать. Все адреса в пределах 4 районов Санкт-Петербурга. Подскажите как лучше сделать? Есть какой нибудь сервис с картами, где хотя бы можно просто отметить точки на карте, маршрут то я уж сам на глаз проложи.
На все про все у меня 2 дня - суббота и воскресенье....
Какие у кого идеи?

Личный опыт: Интересный случай, Разное

28 комментариев 1нравится избранное #

bodan6666 11 апр 2014 в 22:52

Идеи? с таким объемом надо летать как сраный веник а не у копма совета выжидать
- beaver-4ever 11 апр 2014 в 22:53
  
  да успеть то успею, невпервой, хочеться оптимизировать процесс..
3 Lexa33 11 апр 2014 в 22:54

Добавь точки на яндекс картах и всё увидишь, потом сохрани их и обьезжай по навигатору
- bodan6666 11 апр 2014 в 22:56
  
  согласен, тоже так делал.
- 1 beaver-4ever 11 апр 2014 в 23:00
  
  можно чуть поподробнее? точки выгрузить куда то надо?
6 mkot 11 апр 2014 в 23:01

теория графов в помощь...
- B-Vladi 11 апр 2014 в 23:29
  
  Как выгрузить граф дорог? Может Open Street Maps как-то поможет, там вроде вменяемое апи. Ну или другие API карт посмотреть.
OlegTar 11 апр 2014 в 23:41

Решай перебором с возвратами
- rusabakumov 12 апр 2014 в 00:21
  
  Долго ж ты будешь для 92 точек перебирать)
  - OlegTar 12 апр 2014 в 01:09
    
    Мы должны решать программно, а не вручную
  - 2 OlegTar 12 апр 2014 в 01:11
    
    оу, вики пишет "Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет."
    - rusabakumov 12 апр 2014 в 01:33
      
      Я про это и говорю
OlegTar 11 апр 2014 в 23:43

Дай мне набор точек, может помогу...
- beaver-4ever 11 апр 2014 в 23:53
  
  вот сейчас на яндекс карту наношу..
1 EmmGold 12 апр 2014 в 00:45

класика же - Задача коммивояжёра
http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0
- OlegTar 12 апр 2014 в 00:56
  
  это понятно, но надо решить, при том здесь и сейчас
sh 12 апр 2014 в 00:55

Дели на районы по территориальному признаку, внутри ориентируйся по яндекс-картам. Начни с самой дальней точки.
OlegTar 12 апр 2014 в 01:24

Короче, я бы решал так:
Стоишь в изначальной точке А, выбираешь следующую точку, до которой минимальное расстояние, например, это точка D.
Переходишь в неё, потом опять выбираешь следующую точку, до которой минимальное расстояние, допустим это B.
и т.д.
- 2 rusabakumov 12 апр 2014 в 01:35
  
  Лол, алгоритмика на кадабре) Теперь сам придумай контр-пример, например)
  - OlegTar 12 апр 2014 в 01:41
    
    да понятно, что бывает нужно выбрать сначала длинный путь, зато потом сэкономишь.
    в крайнем случае можно смотреть на 2 или 3 шага вперед.
vo1kov 12 апр 2014 в 02:11

Удобно отметить и посмотреть на точки SAS.Planet. С оффсайтом какаято беда вот прямой линк на скачивание
1 beaver-4ever 12 апр 2014 в 02:27

в общем как то так...... http://maps.yandex.ru/?um=lymxGJOlcQn0yKykmLBTbKtZqQQFn2TC&l=sat%2Cskl
завтра иду на подвиг!
beaver-4ever 12 апр 2014 в 02:29

теперь вопрос как быть с навигатором....
- 3 Ke4 12 апр 2014 в 03:11
  
  Возьми готовые фото и не мучайся) http://maps.yandex.ru/?um=lymxGJOlcQn0yKykmLBTbKtZqQQFn2TC&ll=30.368190%2C59.793842&spn=1.304626%2C0.395882&z=10&l=sat%2Cskl%2Cpht%2Csat
Dar4eG 12 апр 2014 в 09:36

Вроде как igo умеет эту тему из коробки
ShpurloS 12 апр 2014 в 10:23

Ура фото-челлендж! )
fearmer 12 апр 2014 в 10:43

Мне почему-то вспомнилась GTA...
PingWin 12 апр 2014 в 10:52

Для начала кластеризуешь, чтобы в одном кластере получалось не больше 15-20 точек. Маршруты между кластерами прикинь руками. А дальше для каждой пары точек внутри кластера считаешь вес (маршрут и его длину) например этим, а дальше - классика, задача коммивояжёра.