Comments 35
Если есть более подходящий блог, то посоветуйте :)
Где дней 5 назад обсуждались плагины к wp на основе gmaps. Там разработчики представили свой вариант вставки карт от гугл в блог + обещали в новой версии реализовать маршруты.
Вот кстати ссылка http://habrahabr.ru/blog/wordpress/47720…
> А жаль — это не самая сложная, зато потенциально весьма полезная функция компьютерной карты.
Вобще говоря это Задача коммивояжёра и она очень сложная для вычислений. С увеличением числа точек маршрута вычислительная сложность растет по n!, оптимизированные алгоритмы дают экспоненциальную сложность, но это тоже очень много. Так что для 1-5 точек это еще вычислимо, а далее уже становится слижком долгим процессом.
Вобще говоря это Задача коммивояжёра и она очень сложная для вычислений. С увеличением числа точек маршрута вычислительная сложность растет по n!, оптимизированные алгоритмы дают экспоненциальную сложность, но это тоже очень много. Так что для 1-5 точек это еще вычислимо, а далее уже становится слижком долгим процессом.
Да, точно. Совсем школьные годы забыл :)
Закон Мура нас спасет. Если услуга окажется востребованной, вычислительные мощности Гугл изыщет. Начнет с пяти точек и будет добавлять точку раз в полгода :)
Закон Мура нас спасет. Если услуга окажется востребованной, вычислительные мощности Гугл изыщет. Начнет с пяти точек и будет добавлять точку раз в полгода :)
Не преувеличивайте 8) Задача прокладки маршрута по карте между двумя точками похожа на задачу комивояжёра. При современных вычислительных мощностях задача ничего не стоит в пределах 10 пунктов. А то что больше 10 пунктов - отличный способ монетизации сервиса.
Не преувеличивайтеСказать правду - это уже значит "преувеличить"?
Задача прокладки маршрута по карте между двумя точками похожа на задачу комивояжёра.Да, формулировки у них похожие. Ресурсы, потребные для решения - и близко рядом не лежали.
При современных вычислительных мощностях задача ничего не стоит в пределах 10 пунктов.Ну как вам сказать... Если вы будете располагать кластером, подобным тому, который используется для обслуживания всех посетителей maps.google.com - то для 10 точек вы её решите с лёгкостью за пару секунд. Но сказать что это "ничего не стоит" вряд ли получится. Аренда такого количества ресурсов даже на пару секунд явно будет не две копейки стоить.
Да ладно. 10 точек даже процессор вашего мобильного телефона рассчитает .
И вообще - много вы знаете туристов, которые хотят за день посетить 10 музеев?
Кстати, рассчёты можно проводить на клиентской стороне, джаваскриптом.
И вообще - много вы знаете туристов, которые хотят за день посетить 10 музеев?
Кстати, рассчёты можно проводить на клиентской стороне, джаваскриптом.
Уважаемый а вы вообще понимаете, о чем спорите? Для примера, если есть некая машина, которая расчитывает тривиальный маршрут (1 точка) за 1 мс то при сложности "3 в степени n" (например) две точки она будет расчитывать уже 9 мс, для трех точек 27 мс, а для 10 точек - 59 секунд (!).
Так о каком там нахер джаваскрипте может идти речь?
Так о каком там нахер джаваскрипте может идти речь?
Никто же не заставляет перебирать все варианты. Вполне достаточно частично прикинуть несколько сотен из них. Пользователю вряд ли важно, 220 километров получится маршрут или 225, но ресурсы от этого будут сэкономлены в сравнимое с n! количество раз.
Если не ошибаюсь, такой алгоритм называется "Алгоритм Коммивояжера"
Смотрим на один комент выше и вспоминаем, что транспортная задача совсем не в этом заключается. Да, сами по себе задачи линейного программирования сложны вычислениями, но здесь достаточно простой алгоритм поиска пути между двумя точками, и скорее это к дискретной математике и графам, чем к линейному программированию и транспортной задаче.
В университете на предмете "теория графов" мы проходили алгоритм Коммивояжера. Прогоняли этот алгоритм по ориентированному графу с ребрами имеющими стоимость.
Кхм, я конечно извинаяюсь, но какое отношение имеет транспортная задаяа к задаче комивояжера?
iGo спасет "отца русской демократии"(с)
там ставишь начальную и конечную точку в одно место, потом указываешь промежуточные точки маршрута и нажимаешь кнопочку "оптимизировать". Удачи!
там ставишь начальную и конечную точку в одно место, потом указываешь промежуточные точки маршрута и нажимаешь кнопочку "оптимизировать". Удачи!
Он наверняка какие-то эвристики считает. Хотя да, приближённое решение - лучше чем ничего...
думаю, в рамках данной задачи, любой результат можно обосновано считать приближенным.
Учитывая, что устройство персональное, не удивлюсь, если он банально перебирает все возможные варианты
Я диплом на эту тему писал. Полностью согласен, что такие задачи точными алгоритмами решать не стоит. Зато приближенные эвристики типа генетических алгоритмов и табу-поиска дают довольно хорошие результаты за приемлемое время.
Решение этих задач с маршрутами не разрешается в лицензии google maps.
Видимо, они сами планируют разрабатывать тему до упора.
Видимо, они сами планируют разрабатывать тему до упора.
Не знаю почему у вас не работает, у меня все замечательно работает в гуглмапс. Выбираешь Get Directions, выбираешь начальный/конечный пункты, он строит маршрут, любую часть которого можно таскать чтобы она прошла через нужную точку, остальной маршрут будет переоптимизирован, чтобы пройти через указанное место. Браузер - FF3, страна Голландия. Кстати разглядывая разные страны доступны разные сервисы - где-то доступен StreetView, а где-то нет. Может в этом собака порылась?
Я не знаю, в каком порядке мне нужно посещать точки. Я не хочу сидеть и перебирать n! вариантов, я хочу, чтобы машина делала это за меня.
Понял вашу проблему, за 10 минут нашел кучу сервисов, предлагающие услуги в этой области. Где еще учитывается и дополнительные параметры, например, в какое время дня нужно посетить определенную точку.
Вот простой и бесплатный пример - http://www.tsp.gatech.edu/maps/index.htm…
Вот простой и бесплатный пример - http://www.tsp.gatech.edu/maps/index.htm…
выберите Plan a trip
Sign up to leave a comment.
Идея прокладки маршрутов