Задача:
Имея место нахождения(через GPS) и отметив пункт назначения, нужно по карте города построить маршрут движения до этой точки.

Честно говоря не знаю даже с чего начать. Может посоветуете? 

ой, да что сложного-то?  задача комивояжора...

P.S. простите за оффтоп... но я в восторге от этого топика... 

ALKS, 
сказал бы лучше по теме. 

Opik, так тебя интересует алгоритм, или Java-реализация?

Какие у тебя есть исходные данные, в каком виде? 

Задача коммивояжёра

Эта тема скорее к алгоритмам относится чем к Java. 

Lamer George, 
Алгоритм.
Данных никаких нет. Вот смотрю в сторону Google Maps, и думаю, нужно ли это... Вообщем сейчас хочу понять как сие вообще сотворить, а потом уже думать над реализацией. 

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

P.S. еще раз сорри в эту тему больше не пишу ибо меня колбасит... 

Позновато я увидел эту тему.

1.Маршрут можно построить только по векторной карте.
2. GOOGLE MAPS - бесплатный картографический движок, если его не использовать в коммерческих целях.

Вообще это не совсем задача комивояжера. Задача комивояжера - это обойти n точек в городе, чтобы суммарное перемещение было минимальным. (её есть более 15 вариантов в зависимости от типа графов и у каждой само собой свои тонсти).

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

Первое, что пришло в голову: это влоб анализировать картинку. Скажем у дорог цвет тёмно-серый (может тёмно коричневый, смотря какая реализация, не суть важно). Сначала находим ближайшую дорогу, а потом идём по дорогам к нужному месту. Можно использовать оценочные функции и разбор нескольких вариантов, чтобы выбрать оптимальный.

Во вложении небольшие художевства в конце рабочего дня на данную тему, не судите строго.   

Присоединённый файл ( Кол-во скачиваний: 18 )
 Graph.jpg 55,52 Kb

Господа, давайте не будем решать уже решенные задачи, ну зачем заморачиваться с картинкой (растровой картой) если уже давно есть векторные?

Добавлено через 42 секунды
йййоптеть......тема-то годовалая....

Что вы ему втюхиваете задачу коммивояжера? Здесь работает алгоритм Дейкстры - поиск кратчайшего пути из одной вершины ко всем остальным. Карту города можно представить как граф, где вершины, это перекрестки дорог, а  ребра это сами дороги. Вот он шикарно (очень понятно) расписан на википедии:

Алгоритм Дейкстры

В простейшем варианте сложность составялет O(n^2) и поэтому грубо говоря поиск пути в городе из 1000 вершина 1Гц процесорре займет  1 секунду. Если использовать в реализации красно-черные деревья, то можно снизить сложность до О(NlogN), но там большая константа съедающая возможный прирост скорости поиска.

Это сообщение отредактировал(а) FireSnake - 9.5.2007, 14:21

Во-первых это было как вариант. А потом, я так понял нет векторного представления карты или есть ?

Легко сказать Алгоритм Дейкстры, а как же ты например учтешь с помощью него дороги с односторонним движением.

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

Так вот если есть только растровая карта, то прочерчиваем ручками маршрут и сохраняем его координаты в файл, а потом читаем от туду по мере надоюности.

Орентированный граф, с одностороним ребром.
А вот как карту в граф перевести, это уже проблемотично.

Это сообщение отредактировал(а) Lomir - 12.5.2007, 12:20

Да про ориентированный граф верно говоришь, но опятьже повторюсь - ЭТО РУЧНАЯ РАБОТА.