HPC.ru lite - Все форумы
Форум: PocketGPS Pro и MacCentre PocketGPS
Тема: Первые впечатления
Страницы: 1 2 3 4 [5] 6

[Ответить]
VctOs [11.05.2004 12:23] Re: 2VctOs:
Есть такой способ, когда проблему никак не получается решить, я его называю "заштукатурить".
При поиске стартовой дуги на манер западных бортовых путевых компов предлагать переместить автомобиль на ближайшую дорогу.
Финишную дугу можно предлагать уточнить "ручками".
Но при этом для прокладки маршрута к заданному адресу более чем в половине случаев будет требоваться такое уточнение + примерно секунда машинного времени будет нужна для того, чтобы проанализировать наличие препятствия. Хотя, с другой стороны на время прокладки маршрута вроде пока никто не жаловался.
AbsZero [11.05.2004 14:30] :
Вот наконец-ту удалось съездить в параздники на дачу и заодно проверить как там в области все это работает. Полное разочарование. По Ярославскому ш. машинка движется где угодно но только не по трассе (вроде как по некой синусойде окло трассы). Почему-то исчез мост с развязкой между новой Ярославкой и стырым шоссе (въезд в г.Пушкино). Как теперь на дачу попасть - не знаю!
Привязка к карте, по-моему, стала еще хуже.
Ромик [11.05.2004 15:46] :
Не, теперь Вы пришлите рисунок с стартом, финишем и запретами проезда, тогда я смогу попробовать. Пока я совершенно не понимаю исходные данные.
Посмотрите что получилось http://foto.rambler.ru/users/ntoz/2/44/
Попробуйте.
NikolaRC [12.05.2004 07:35] 2VctOs:
Ну вот, кажется с проблемой въезда и выеза на маршрут, воздушными путями, стартовыми м финишными дугами и прочими проблемами, с ними связанными, с помощью VctOs мы разобрались. В сухом остатке наших дискуссий имеем, что стартовая и финишная дуги пока уникальны и определяются кратчайшим воздушным путем, который, в свою очередь, не учитывает препятствий. Проблема препятствий на старте и финише имеет строгое математической решение, но для этого требуется поколение КПК с памятью 128 Мб. На некоторые вопросы автор ядра не ответил, но это его авторское право. Возможно, некоторые вопросы были сформулированы некорректно. Например, говоря о невозможности проложить маршрут и связывая это с препятствиями при съезде, я имел в виду тот "Бермудский треугольник", о котором сообщил PanD@, и совсем забыл, что в своем ответе на это сообщение VctOs уже объяснил эту ситуацию " тем, что стартовая или финишная дуга оторвана от дорожной сети". Ну, вот взяли и оторвались, хотя должны соединять. Не могу удержаться от новых вопросов.
1. Сразу же после появления PocketGpsPro пользователи стали требовать третью точку при прокладке маршрута. На мой взгляд, все это достаточно просто. Всего-то тебуется проложить еще один маршрут от промежуточной точки, а затем сшить два маршрута. То, что это пока не реализовано, связано с какими-то нам непонятными техническими проблемами или это маркетинговая политика?
2. Решение полной задачи коммивояжера на КПК, это реально?
PanD@ [12.05.2004 11:24] :
Я, право, не уверен насколько возможно и нужно это строгое математическое решение. Есть у меня сомнение, что эти области в стороне от дорог хоть когда-нибудь на карте будут соответствовать реальной обстановке.
Я не согласен с автором по поводу термина "заштукатурить". По-моему нормальный нересурсоемкий ход.
Я даже надеюсь, что в блишайших обновлениях это будет реализовано...
Видится такой эвристический алгоритм:
Возушную дугу с препятствием - отбрасывать, искать другую.
Выбирать из неотброшенных кратчайшую (или с учетом всего результирующего пути). Если таких нет - просить помошь зала... эээ оператора.
Ошибки могут возникать в случае: непреодолимое препятствие не полностью перекрывает путь к ближайшей дороге, а только на прямом пути. (Под "полностью перекрывает" я понимаю реальную необходимость двигаться по другим дорогам, входящим в граф).
Примеры - изгибы водоемов, ж/д, заборов, и пр. которые можно объехать по дорожкам, не нанесенным на карту.
Если на пути есть бордюр-кустарник, то все равно наверняка должен быть объезд рядом.
Все равно на карту никогда не будут нанесены дворовые шлагбаумы и заградительные бетонные блоки и столбы.
Перечень объектов-препятствий, относимых к непреодолимым и преодолимым (т.е непротяженным и объезжаемым) надо обдумать (или ввести критерии учета препятствий в настройки).
Пока все.
NikolaRC [12.05.2004 12:33] 2PanD@:
Уважаемый PanD@, вот какие моменты в ваших рассуждениях мне хотелось бы прокомментировать
1. Возможность строгого мат. решения. Поскольку мы не специалисты в геоинформационных науках, нам остается только доверять компетентности VctOs, которая, я полагаю, ни у кого не вызывает сомнения.
2. Лично у меня не вызывает никаких сомнений, что эти области в стороне от дорог никогда на карте не будут соответствовать реальной обстановке. Но это не значит, что строгое решение совершенно бесполезно. Просто в реальном мире оно перестанет быть строгим и лишь отчасти останется решением. Кстати, успех вашего эвристического алгоритма тоже в значительной степени зависит от соответствия реальной и карточной ситуации, причем уже с самого начала, при выборе воздушных дуг. Имеет ли право на существование и реализацию ваш алгоритм? А почему бы и нет, после доработки и детализации. Что лучше, строгость или эвристика? А кто знает? Я в таких неопределенных по своему результату случаях выбираю эстетичесий критерий, строгие математические решения обладают определенной красотой.
PanD@ [12.05.2004 14:00] :
Уважаемый NikolaRC

Компетентность VctOs не обсуждается.

Я позволю себе процитировать его высказывание:

"Поэтому можно говорить о том, что решение этой проблемы сводится к полному решению "проблемы Pand@" - поиску непрямого выезда на дорогу из заданной точки с учетом изображенных на карте препятствий и ограничений. Но к сожалению, пока нет никаких практически приемлемых идей как реализовать оптимальную трассировку в многосвязанном свободном пространстве силами карманного компьютера"

Здесь нет ни слова о строгом математическом решении.

"... С учетом изображенных на карте препятствий". А как мы выяснили на карте далеко не все изображено, что может мешать проезду. В таких условиях оптимальное решение (на основе имеющихся исходных данных и критериев оптимальности, пусть математически строгое) может быть не совсем, мягко говоря, адекватным.
В условиях большой неопределенности такое строгое решение может не иметь никаких преимуществ перед более простым решением, выполненным по упрощенному алгоритму, основанному не на строгих математические понятиях, а реальных предположениях о возможной структуре препятствий в г. Москве и её окрестностях.

Красива математическая модель сферического коня в вакууме. Но на практике бесполезна.

По-моему, у нас выводы одинаковые?
NikolaRC [12.05.2004 14:15] 2PanD@:
ОК! Согласен.
VctOs [12.05.2004 16:44] :
Попробовал.
Ситуация полностью аналогичная описаной NikolaRC: запрет проезда по стартовой дуге.
VctOs [12.05.2004 17:27] Re: 2VctOs:
Вопросов в каждом посте было много, поэтому, возможно, я что-то упустил.

Совершенно, кстати, обычное явление. Нерусские программы, которые используют картографы не имеют опции "склеивания" узлов, но требуют точного совпадения координат для учета дуг как соединенных.

Могу Вас уверить, что все это время без дела никто не сидел.
Сразу после выпуска первой версии был опубликован список "Изменений, ожидаемые в следующих версиях"
http://www.pocketgps.ru/products/specs.shtml
Последним пунктом в нем именно то, о чем Вы спрашиваете:
Поправьте меня если я ошибаюсь - это единственный не реализованный на сегодня пункт опубликованного плана развития.

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

Не столько для Вас, сколько для других читателей напомню, что полная задача коммивояжера пока решается только полным перебором всех возможных вариантов. А всего таких вариантов может быть N!, где N - количество посещаемых точек.
! - это знак математической операции факториал.
1! = 1
2! = (1!)*2 = 2
3! = (2!)*3 = 6
4! = (3!)*4 = 24
5! = (4!)*5 = 120
6! = (5!)*6 = 620
***
10! = 3628800
20! = 2432902008176640000
25! = 15511210043330985984000000

Для трех-четырех точек - наверняка реально.
Для пяти-шести - надеюсь.
Для двенадцати - точно нереально, нужно использовать эвристики.

Добавлю, что этой задачи пока в планах развития ядра почти не стоит.
[Ответить]
[< Назад]  [Вперед >]