@ssneg5 авг 2008 в 07:43

Идея прокладки маршрутов

1 мин

5.3K

IT-компании

Комментарии 35

@ssneg 5 авг 2008 в 07:44

Если есть более подходящий блог, то посоветуйте :)

@BugZ 5 авг 2008 в 07:46

Где дней 5 назад обсуждались плагины к wp на основе gmaps. Там разработчики представили свой вариант вставки карт от гугл в блог + обещали в новой версии реализовать маршруты.

@BugZ 5 авг 2008 в 07:54

Вот кстати ссылка http://habrahabr.ru/blog/wordpress/47720…

@ssneg 5 авг 2008 в 07:57

Прочитал. И как это могло бы решить мою проблему?

@dmmm 5 авг 2008 в 08:00

> А жаль — это не самая сложная, зато потенциально весьма полезная функция компьютерной карты.
Вобще говоря это Задача коммивояжёра и она очень сложная для вычислений. С увеличением числа точек маршрута вычислительная сложность растет по n!, оптимизированные алгоритмы дают экспоненциальную сложность, но это тоже очень много. Так что для 1-5 точек это еще вычислимо, а далее уже становится слижком долгим процессом.

@ssneg 5 авг 2008 в 08:06

Да, точно. Совсем школьные годы забыл :)

Закон Мура нас спасет. Если услуга окажется востребованной, вычислительные мощности Гугл изыщет. Начнет с пяти точек и будет добавлять точку раз в полгода :)

НЛО прилетело и опубликовало эту надпись здесь

@alexxz 5 авг 2008 в 08:16

Не преувеличивайте 8) Задача прокладки маршрута по карте между двумя точками похожа на задачу комивояжёра. При современных вычислительных мощностях задача ничего не стоит в пределах 10 пунктов. А то что больше 10 пунктов - отличный способ монетизации сервиса.

@khim 5 авг 2008 в 08:59

Не преувеличивайте

Сказать правду - это уже значит "преувеличить"?

Задача прокладки маршрута по карте между двумя точками похожа на задачу комивояжёра.

Да, формулировки у них похожие. Ресурсы, потребные для решения - и близко рядом не лежали.

При современных вычислительных мощностях задача ничего не стоит в пределах 10 пунктов.

Ну как вам сказать... Если вы будете располагать кластером, подобным тому, который используется для обслуживания всех посетителей maps.google.com - то для 10 точек вы её решите с лёгкостью за пару секунд. Но сказать что это "ничего не стоит" вряд ли получится. Аренда такого количества ресурсов даже на пару секунд явно будет не две копейки стоить.

@the_bee 5 авг 2008 в 11:11

Да ладно. 10 точек даже процессор вашего мобильного телефона рассчитает .
И вообще - много вы знаете туристов, которые хотят за день посетить 10 музеев?
Кстати, рассчёты можно проводить на клиентской стороне, джаваскриптом.

@Gunnar 5 авг 2008 в 16:44

Уважаемый а вы вообще понимаете, о чем спорите? Для примера, если есть некая машина, которая расчитывает тривиальный маршрут (1 точка) за 1 мс то при сложности "3 в степени n" (например) две точки она будет расчитывать уже 9 мс, для трех точек 27 мс, а для 10 точек - 59 секунд (!).

Так о каком там нахер джаваскрипте может идти речь?

@Kalan 5 авг 2008 в 11:43

Никто же не заставляет перебирать все варианты. Вполне достаточно частично прикинуть несколько сотен из них. Пользователю вряд ли важно, 220 километров получится маршрут или 225, но ресурсы от этого будут сэкономлены в сравнимое с n! количество раз.

@komjah 6 авг 2008 в 08:59

И как вы себе представляете реализацию сего? Получился у нас результат 220 км, и программа должна подумать: "Черт возьми! Да ведь это-же не так уж и много." и прекратить вычисления? или посчитать еще один маршрут получить 255 и выдать любой из них?

@Kalan 6 авг 2008 в 09:06

Самое простое, что можно тут применить — генетический алгоритм. Его можно заставить и так рассуждать, конечно, но, как правило, «мысль» звучит как «ну его нафиг, я уже проанализировал n вариантов, лучший из них наверняка подойдёт».

@Chips 5 авг 2008 в 08:00

Если не ошибаюсь, такой алгоритм называется "Алгоритм Коммивояжера"

@khizhaster 5 авг 2008 в 08:54

Смотрим на один комент выше и вспоминаем, что транспортная задача совсем не в этом заключается. Да, сами по себе задачи линейного программирования сложны вычислениями, но здесь достаточно простой алгоритм поиска пути между двумя точками, и скорее это к дискретной математике и графам, чем к линейному программированию и транспортной задаче.

@Chips 5 авг 2008 в 09:00

В университете на предмете "теория графов" мы проходили алгоритм Коммивояжера. Прогоняли этот алгоритм по ориентированному графу с ребрами имеющими стоимость.

@khizhaster 5 авг 2008 в 09:03

Я ошибся в формулировках, извиняюсь. Но суть в том, что для алгоритма коммивояжера есть много параметров и эффективные его реализации достаточно сложны, здесь же критерий самый простой.

@allseek 5 авг 2008 в 09:04

у меня курсач был такой. Занятная скажу вам тема. особенно ежели на ООП реализовывать.

@Chips 5 авг 2008 в 09:18

у нас это было в рамках лабораторной работы и предполагалось, что мы это все решаем в тетрадочке и преподу показываем. Но мы просто написали программу, которая в Word-документе формировала решение поэтапное. Далее просто переписывали и приносили.

@Gunnar 5 авг 2008 в 16:47

Кхм, я конечно извинаяюсь, но какое отношение имеет транспортная задаяа к задаче комивояжера?

@allseek 5 авг 2008 в 08:56

iGo спасет "отца русской демократии"(с)
там ставишь начальную и конечную точку в одно место, потом указываешь промежуточные точки маршрута и нажимаешь кнопочку "оптимизировать". Удачи!

@khim 5 авг 2008 в 09:01

Он наверняка какие-то эвристики считает. Хотя да, приближённое решение - лучше чем ничего...

@allseek 5 авг 2008 в 09:21

думаю, в рамках данной задачи, любой результат можно обосновано считать приближенным.

@nooze 5 авг 2008 в 10:49

Учитывая, что устройство персональное, не удивлюсь, если он банально перебирает все возможные варианты

@khim 5 авг 2008 в 11:51

Для десятка вариантов персональное устройство уже сдохнет варианты перебирать.

@nooze 5 авг 2008 в 12:42

Так они и дохнут :)

@Yarc 5 авг 2008 в 14:57

Я диплом на эту тему писал. Полностью согласен, что такие задачи точными алгоритмами решать не стоит. Зато приближенные эвристики типа генетических алгоритмов и табу-поиска дают довольно хорошие результаты за приемлемое время.

@thecoder 5 авг 2008 в 13:05

Решение этих задач с маршрутами не разрешается в лицензии google maps.
Видимо, они сами планируют разрабатывать тему до упора.

НЛО прилетело и опубликовало эту надпись здесь

@thecoder 6 авг 2008 в 14:29

Ох, видать мой английский подкачал.
Спасибо за разъяснение.

@TedBeer 6 авг 2008 в 07:47

Не знаю почему у вас не работает, у меня все замечательно работает в гуглмапс. Выбираешь Get Directions, выбираешь начальный/конечный пункты, он строит маршрут, любую часть которого можно таскать чтобы она прошла через нужную точку, остальной маршрут будет переоптимизирован, чтобы пройти через указанное место. Браузер - FF3, страна Голландия. Кстати разглядывая разные страны доступны разные сервисы - где-то доступен StreetView, а где-то нет. Может в этом собака порылась?

@ssneg 6 авг 2008 в 09:32

Я не знаю, в каком порядке мне нужно посещать точки. Я не хочу сидеть и перебирать n! вариантов, я хочу, чтобы машина делала это за меня.

@TedBeer 6 авг 2008 в 10:05

Понял вашу проблему, за 10 минут нашел кучу сервисов, предлагающие услуги в этой области. Где еще учитывается и дополнительные параметры, например, в какое время дня нужно посетить определенную точку.
Вот простой и бесплатный пример - http://www.tsp.gatech.edu/maps/index.htm…

@TedBeer 6 авг 2008 в 10:06

выберите Plan a trip

Зарегистрируйтесь на Хабре, чтобы оставить комментарий