ой, да что сложного-то?
задача комивояжора...P.S. простите за оффтоп... но я в восторге от этого топика...
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > GPS Навигация по городу |
| Автор: Opik 15.5.2006, 12:32 |
| Задача: Имея место нахождения(через GPS) и отметив пункт назначения, нужно по карте города построить маршрут движения до этой точки. Честно говоря не знаю даже с чего начать. Может посоветуете? |
| Автор: ALKS 15.5.2006, 12:34 |
ой, да что сложного-то? задача комивояжора...P.S. простите за оффтоп... но я в восторге от этого топика... |
| Автор: Opik 15.5.2006, 12:48 |
| ALKS, сказал бы лучше по теме. |
| Автор: batigoal 15.5.2006, 12:55 |
| Opik, так тебя интересует алгоритм, или Java-реализация? Какие у тебя есть исходные данные, в каком виде? |
| Автор: powerOn 15.5.2006, 12:56 |
| 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 Эта тема скорее к алгоритмам относится чем к Java. |
| Автор: Opik 15.5.2006, 12:57 |
| Lamer George, Алгоритм. Данных никаких нет. Вот смотрю в сторону Google Maps, и думаю, нужно ли это... Вообщем сейчас хочу понять как сие вообще сотворить, а потом уже думать над реализацией. |
| Автор: ALKS 15.5.2006, 13:06 |
| Я довольно убежденно могу предположить что Google Maps стоил милионы, а то что его делали несколько лет и очень не мало людей - это я знаю. и алгоритмы там такие которые я думаю ты в сети не найдеш. уникальные решения, хотя и базирующиеся на общедоступной математической теории. Вооще если бы у меня был достойный алгоритм, я бы его тебе не показал. я бы его продал пожалуй, даже знаю кому и за сколько... P.S. еще раз сорри в эту тему больше не пишу ибо меня колбасит... |
| Автор: Artemon 8.5.2007, 15:18 |
| Позновато я увидел эту тему. 1.Маршрут можно построить только по векторной карте. 2. GOOGLE MAPS - бесплатный картографический движок, если его не использовать в коммерческих целях. |
| Автор: Promitheus 8.5.2007, 16:04 |
| Вообще это не совсем задача комивояжера. Задача комивояжера - это обойти n точек в городе, чтобы суммарное перемещение было минимальным. (её есть более 15 вариантов в зависимости от типа графов и у каждой само собой свои тонсти). А тут, насколько я понял, мы находимся здесь, нам нужно попасть по дорогам туда-то и усё. Построение пути обхода нескольких точек, я так предполагаю не подразумевается. Первое, что пришло в голову: это влоб анализировать картинку. Скажем у дорог цвет тёмно-серый (может тёмно коричневый, смотря какая реализация, не суть важно). Сначала находим ближайшую дорогу, а потом идём по дорогам к нужному месту. Можно использовать оценочные функции и разбор нескольких вариантов, чтобы выбрать оптимальный. Во вложении небольшие художевства в конце рабочего дня на данную тему, не судите строго.  |
| Автор: SparF 9.5.2007, 11:18 | ||
Господа, давайте не будем решать уже решенные задачи, ну зачем заморачиваться с картинкой (растровой картой) если уже давно есть векторные? Добавлено через 42 секунды йййоптеть......тема-то годовалая.... |
| Автор: FireSnake 9.5.2007, 14:20 |
| Что вы ему втюхиваете задачу коммивояжера? Здесь работает алгоритм Дейкстры - поиск кратчайшего пути из одной вершины ко всем остальным. Карту города можно представить как граф, где вершины, это перекрестки дорог, а ребра это сами дороги. Вот он шикарно (очень понятно) расписан на википедии: http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B В простейшем варианте сложность составялет O(n^2) и поэтому грубо говоря поиск пути в городе из 1000 вершина 1Гц процесорре займет 1 секунду. Если использовать в реализации красно-черные деревья, то можно снизить сложность до О(NlogN), но там большая константа съедающая возможный прирост скорости поиска. |
| Автор: Promitheus 10.5.2007, 12:09 |
| Во-первых это было как вариант. А потом, я так понял нет векторного представления карты или есть ? |
| Автор: Artemon 11.5.2007, 15:56 |
| Легко сказать Алгоритм Дейкстры, а как же ты например учтешь с помощью него дороги с односторонним движением. Да и вообще роутинг на картах делается вручную, потомучто здесь не позволительны даже малейшие ошибки. Так вот если есть только растровая карта, то прочерчиваем ручками маршрут и сохраняем его координаты в файл, а потом читаем от туду по мере надоюности. |
| Автор: Lomir 12.5.2007, 12:19 | ||
А вот как карту в граф перевести, это уже проблемотично. |
| Автор: Artemon 12.5.2007, 17:07 |
| Да про ориентированный граф верно говоришь, но опятьже повторюсь - ЭТО РУЧНАЯ РАБОТА. |
