|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
КАК НАЙТИ НАИМЕНЬШЕЕ РАСТОЯНИЕ ТОЧЕК НА КАРТЕ (прога для такси)
КАК НАЙТИ НАИМЕНЬШЕЕ РАСТОЯНИЕ ТОЧЕК НА КАРТЕ. ЕСТЬ БАЗА ДАНИХ КОТОРАЯ СОСТОИТ ИЗ КООРДИНАТ ТОЧЕР РАСПОЛОЖЕНЫХ НА КАРТЕ ГОРОДА. ФОРМАТ ТОЧКИ (№п/п, X, Y, улица1, улица2, улица3, улица4, улица5). улицы.. ОБОЗНАЧАЮТ ПЕРЕХРЕСТОК С УЛИЦ. НАПРИМЕР ТОЧКА (125, 1786, 2050, 25, 3, 0, 0, 0) - ЭТО ПЕРЕХРЕСТОК С ДВУХ УЛИЦ 25 и 3 С КООРДИНАТАМИ [1786,2050] № 125.
ВОПРОС : КАК МОЖНА ОТОБРАТЬ НАИМЕНЬШИЙ ПУТЬ ОТ ТОЧКИ №1 К ТОЧКИ №2. ЗАГВОЗДКА В ТОМ ЧТОБЫ ЭТО РАБОТАЛО БЫСТРО. Я ПРОБЫВАЛ ГРУПИРОВАТЬ ТОЛЬКО ПЕРЕХРЕСТКИ, ОТДЕЛЬНО УЛИЦЫ (с подальшей обработкой по точкам) - ИХ НАМНОГО МЕНЬШЕ ЧЕМ ПЕРЕХРЕСТКОВ. Я ШОЛ КАК ПО ЛАБИРИНТУ УНИЧТОЖАЯ ОТРЕСКИ УЛИЦ ПО КОТОРЫМ ПРОШОЛ. ПЕРВУЮ УДАЧНЫЙ ПОХОД К КОНЦЕВОЙ ТОЧКИ Я БРАЛ КАК МИНИМАЛЬНЫЙ, И СЛЕДУЮЩИЙ ПОХОД Я КОРЕКТИРОВАЛ К МИНИМАЛЬНОЙ И ПРИ ПЕРЕБОРЕ ДЕЛАЛ ВОЗВРАТ НА ПРЕДИДУЩУЮ ТОЧКУ / ПОВОРОТ / УЛИЦУ (испытал три способа) С ПОДАЛЬШИМ ОТБОРОМ СЛЕДУЮЩЕЙ ТОЧКИ. МОЖЕТ КТОТО ЗНАЕТ ЕЩО КАКОЙТО СПОСОБ ? |
#3
|
||||
|
||||
почитай что такое граф, потом про поиск минимального пути, потом подточи под свою задачу уже известные алгоритмы. Садиться же и делать тебе слегка специфичную лабу как то неохота
PS> а для начала и вправду, не мешает и правила почитать PPS> за лабу извиняюсь) работу чужую делать не хочется) вот ещё, вершины графа - перекрёстки. тебе нужно найти путь -во 1х, самый короткий (экономим бензин) -во 2х, с наименьшим кол-вом перекрёстков (на перекрёстках долго стоять, и топлива больше тратим. Это конечно можно добавить, но ты с первым разберись для начала) Далее - работай сам, задача элементарная. первокурсусы и то сложнее делают) Нет повести печальнее на свете, чем повесть о заклиневшем Resete. Последний раз редактировалось Ferra, 30.03.2009 в 17:06. |
#4
|
|||
|
|||
СПАСИБО ЗА ПОМОЩЬ !!!!
|