Подскажите кто знает формулу или метод как найти наименьшее растояние между точками на карте. Карта содержит множество точек на карте города. Точка содержит информацию (№точки, x, y, [пересекание каких улиц ]). Ети точки такще можна прязать к широте и долготе. Но все процедуры з данными использует програма для такси. Например :
-----------------------------------
в табл. улиц
15 - ул. Большевиков
74 - ул. Красная
33 - просп. Большой
------------------------------------
в таблице точек
точка № 152 = 152, 1765, 452, 15, 33, 0, 0, 0 --- означает что точка под номером 152 с коорд. 1765, 452 находится на пересичение улиц 15 и 33 (Большевиков и посп. Большой).
===============================================================
При поиске наименьшего растояния я делаю цикл в котором я ищу наименьшее пересекание улиц от начальной точки к конечной. Но есть одно но, поиск должен производится быстро, а если перебирать все варианты - ето занимает много времени. Я уже отсекаю от поиска все пройдены улицы, при возврате с тупика создаю список тупиковых пройденых улиц - и следущий заход на них пропускаю. Может кто знает какой то иной метод поиска. ПОДСКАЖИТЕ ПОЖАЛУСТА !!!!!!
наименьшее растояние между точками города
-
- Новоприбывший
- Сообщения: 2
- Зарегистрирован: 03 июн 2009, 00:57
- Репутация: 0
-
- Гуру
- Сообщения: 977
- Зарегистрирован: 27 янв 2009, 22:57
- Репутация: 258
Re: наименьшее растояние между точками города
Рекомендую прочитать книжечку:
Т.Кормен. Алгоритмы: построение и анализ.
Методы: поиск в ширину, глубину, Дейкстра, A*
Я проверял методы поиск в ширину и алгоритм Дейкстра - очень быстро работают.
Основное время тратится на загрузку данных в массив.
На википедии есть примеры этих алгоритмов на разных языках программирования (только вики надо открывать на английском, а не ее урезанный русский вариант)
Т.Кормен. Алгоритмы: построение и анализ.
Методы: поиск в ширину, глубину, Дейкстра, A*
Я проверял методы поиск в ширину и алгоритм Дейкстра - очень быстро работают.
Основное время тратится на загрузку данных в массив.
На википедии есть примеры этих алгоритмов на разных языках программирования (только вики надо открывать на английском, а не ее урезанный русский вариант)
-
- Новоприбывший
- Сообщения: 2
- Зарегистрирован: 03 июн 2009, 00:57
- Репутация: 0
Re: наименьшее растояние между точками города
bim2010 БОЛЬШОЕ СПАСИБО !!!!!!!!!!
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 3 гостя