Написать пост

beaver-4ever

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

Итак ситуация.... по работе срочняком озадачили. Имеем 92 адреса, которые нужно обьехать и сфотографировать. Все адреса в пределах 4 районов Санкт-Петербурга. Подскажите как лучше сделать? Есть какой нибудь сервис с картами, где хотя бы можно просто отметить точки на карте, маршрут то я уж сам на глаз проложи.
На все про все у меня 2 дня - суббота и воскресенье....
Какие у кого идеи?
29 комментариев 1нравится избранное
bm9701
  • bodan6666
    11 апр 2014 в 22:52
    Идеи? с таким объемом надо летать как сраный веник а не у копма совета выжидать
    • beaver-4ever
      11 апр 2014 в 22:53
      да успеть то успею, невпервой, хочеться оптимизировать процесс..
  • Lexa33
    3 11 апр 2014 в 22:54
    Добавь точки на яндекс картах и всё увидишь, потом сохрани их и обьезжай по навигатору
    • bodan6666
      11 апр 2014 в 22:56
      согласен, тоже так делал.
    • beaver-4ever
      1 11 апр 2014 в 23:00
      можно чуть поподробнее? точки выгрузить куда то надо?
  • stasyatr
    2 11 апр 2014 в 22:57
  • mkot
    6 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
        Мы должны решать программно, а не вручную
      • OlegTar
        2 12 апр 2014 в 01:11
        оу, вики пишет "Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет."
        • rusabakumov
          12 апр 2014 в 01:33
          Я про это и говорю
  • OlegTar
    11 апр 2014 в 23:43
    Дай мне набор точек, может помогу...
    • beaver-4ever
      11 апр 2014 в 23:53
      вот сейчас на яндекс карту наношу..
  • EmmGold
    1 12 апр 2014 в 00:45
    • OlegTar
      12 апр 2014 в 00:56
      это понятно, но надо решить, при том здесь и сейчас
  • sh
    12 апр 2014 в 00:55
    Дели на районы по территориальному признаку, внутри ориентируйся по яндекс-картам. Начни с самой дальней точки.
  • OlegTar
    12 апр 2014 в 01:24
    Короче, я бы решал так:
    Стоишь в изначальной точке А, выбираешь следующую точку, до которой минимальное расстояние, например, это точка D.
    Переходишь в неё, потом опять выбираешь следующую точку, до которой минимальное расстояние, допустим это B.
    и т.д.
    • rusabakumov
      2 12 апр 2014 в 01:35
      Лол, алгоритмика на кадабре) Теперь сам придумай контр-пример, например)
      • OlegTar
        12 апр 2014 в 01:41
        да понятно, что бывает нужно выбрать сначала длинный путь, зато потом сэкономишь.
        в крайнем случае можно смотреть на 2 или 3 шага вперед.
  • vo1kov
    12 апр 2014 в 02:11
    Удобно отметить и посмотреть на точки SAS.Planet. С оффсайтом какаято беда вот прямой линк на скачивание
  • beaver-4ever
    1 12 апр 2014 в 02:27
    в общем как то так...... http://maps.yandex.ru/?um=lymxGJOlcQn0yKykmLBTbKtZqQQFn2TC&l=sat%2Cskl
    завтра иду на подвиг!
  • beaver-4ever
    12 апр 2014 в 02:29
    теперь вопрос как быть с навигатором....
  • Dar4eG
    12 апр 2014 в 09:36
    Вроде как igo умеет эту тему из коробки
  • ShpurloS
    12 апр 2014 в 10:23
    Ура фото-челлендж! )
  • fearmer
    12 апр 2014 в 10:43
    Мне почему-то вспомнилась GTA...
  • PingWin
    12 апр 2014 в 10:52
    Для начала кластеризуешь, чтобы в одном кластере получалось не больше 15-20 точек. Маршруты между кластерами прикинь руками. А дальше для каждой пары точек внутри кластера считаешь вес (маршрут и его длину) например этим, а дальше - классика, задача коммивояжёра.
Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста, или зарегистрируйтесь.