Форум: PocketGPS Pro и MacCentre PocketGPS
Тема: МАРШРУТ: предложения и пожелания.
Страницы: [1] 2
[Ответить]
mdw75 [17.08.2005 00:44] МАРШРУТ: предложения и пожелания.:
1. Про то, что желательна возможность создания маршрута из неограниченного количества точек уже говорилось.
2. Возможность создания нескольких маршрутов и их сохраниения и восстановления. Немного напрягает тот момент, что при закрытии программы проложенный маршрут уничножается.
3. Возможность оптимальной прокладки маршрута при задании серии точек. То есть необходимо посетить несколько пунктов. Мы создаём их список, и программа связывает их оптимальным образом. При этом можно задавать любым точкам: порядковый номер в маршруте, последовательность (либо точка В должна следовать строго за точкой А, либо точка В должна быть после точки А, причём во втором случае допускается построение точки С между А и В), временное ограничение (посетить точку до указанного времени, после или в интервале). После этого происходит просчёт точек без ограничений и с менее жесткими ограничениями.
-=Sorrow=- [17.08.2005 08:15] Re: МАРШРУТ: предложения и пожелания.:
вово - отсутвие возможности - сохранять/открывать маршруты - сильно напрягает.
Пикс [17.08.2005 08:26] Re: МАРШРУТ: предложения и пожелания.:
- mdw75 писал(а):
1. Про то, что желательна возможность создания маршрута из неограниченного количества точек уже говорилось.
2. Возможность создания нескольких маршрутов и их сохраниения и восстановления. Немного напрягает тот момент, что при закрытии программы проложенный маршрут уничножается.
3. Возможность оптимальной прокладки маршрута при задании серии точек. То есть необходимо посетить несколько пунктов. Мы создаём их список, и программа связывает их оптимальным образом. При этом можно задавать любым точкам: порядковый номер в маршруте, последовательность (либо точка В должна следовать строго за точкой А, либо точка В должна быть после точки А, причём во втором случае допускается построение точки С между А и В), временное ограничение (посетить точку до указанного времени, после или в интервале). После этого происходит просчёт точек без ограничений и с менее жесткими ограничениями.
-=Sorrow=- [17.08.2005 08:30] Re: МАРШРУТ: предложения и пожелания.:
- "По второму пункту: на закладке "Файлы" можно поставить галочку "сохранять маршрут при выходе".
Спасибо. вот уж не заметил, так не заметил
BreQwaS [17.08.2005 10:26] :
- 3. Возможность оптимальной прокладки маршрута при задании серии точек. То есть необходимо посетить несколько пунктов.
Алгоритмическая сложность этой задачи (оптимальный маршрут через много точек) AFAIR гораздо выше сложности алгоритма Дейкстры (только старт и финиш). Если поиск маршрута Дейкстрой занимает несколько секунд (по компьютерным меркам - это очень много), то сколько времени потребуеся на решение ЗК?
Но если порядок посещения точек укажет пользователь, то можно просто последовательно применить Дейкстру, и тогда длительность поиска в среднем возрастёт примерно во столько раз, на сколько отрезков разбит маршрут этими точками. Это ещё терпимо.
Alligator. [17.08.2005 11:04] :
по пункту 3 и "задаче коммивояжера"
если точек много, тогда сложность задачи большая
если точек только две (точка 1 и точка 2), тогда просто надо пустить существующий механизм с промежуточными точками 1,2 и 2,1 и выбрать оптимальную последовательность точек
всего в два раза дольше, имхо терпимо
если же будет 3 промежуточные точки, то возможных вариантов будет 6: 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1
на мощной машинке наверное тоже терпимо, хотя часто пересчитывать не захочется, имхо
при 4 промежуточных точках будет 24 варианта, это уже будет долго ...
хотя, возможно, можно ещё оптимизировать собственно алгоритм прокладки оптимального пути от точки А до точки Б ...
да и КПК всё быстреют и быстреют ...
в любом случае, я бы сказал, что такую функцию было бы неплохо реализовать
но дать пользователю возможность выбора - надо ли определять порядок прохождения точек, надо ли это делать при каждом обновлении пробок или только по нажатии кнопки и т.д.
BreQwaS [17.08.2005 11:12] :
Alligator.
Можно. Или можно посчитать расстояние между точками по прямой и исходя из этого получить порядок обхода точек - с высокой вероятностью он будет верным.
Но есть подозрение, что это не самая приоритетная задача для разработчиков сейчас
Alligator. [17.08.2005 12:07] :
- BreQwaS писал(а):
Alligator.
Можно. Или можно посчитать расстояние между точками по прямой и исходя из этого получить порядок обхода точек - с высокой вероятностью он будет верным.
Но есть подозрение, что это не самая приоритетная задача для разработчиков сейчас
приоритет - естественно не высокий, я потому и написал
- такую функцию было бы неплохо реализовать
Но имхо её сделать не очень сложно, а было бы приятно ...
BreQwaS [17.08.2005 12:13] :
- расстояние по прямой имхо часто может давать неправильный порядок
- Но имхо её сделать не очень сложно
Alligator. [17.08.2005 12:38] :
- BreQwaS писал(а):
- Но имхо её сделать не очень сложно
- сейчас есть функция прокладки маршрута с промежуточными точками в заданном порядке
- надо несколько раз её запускать, давая ей точки в разном порядке
- каждый раз запоминать длину маршрута, потом выбрать ту последовательность, которая дала минимальную длину
[Ответить]
[Вперед >]