Первые впечатления

[NikolaRC]

Уважаемый PanD@, вот какие моменты в ваших рассуждениях мне хотелось бы прокомментировать
1. Возможность строгого мат. решения. Поскольку мы не специалисты в геоинформационных науках, нам остается только доверять компетентности VctOs, которая, я полагаю, ни у кого не вызывает сомнения.
2. Лично у меня не вызывает никаких сомнений, что эти области в стороне от дорог никогда на карте не будут соответствовать реальной обстановке. Но это не значит, что строгое решение совершенно бесполезно. Просто в реальном мире оно перестанет быть строгим и лишь отчасти останется решением. Кстати, успех вашего эвристического алгоритма тоже в значительной степени зависит от соответствия реальной и карточной ситуации, причем уже с самого начала, при выборе воздушных дуг. Имеет ли право на существование и реализацию ваш алгоритм? А почему бы и нет, после доработки и детализации. Что лучше, строгость или эвристика? А кто знает? Я в таких неопределенных по своему результату случаях выбираю эстетичесий критерий, строгие математические решения обладают определенной красотой.

[PanD@]

Уважаемый NikolaRC

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

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

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

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

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

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

По-моему, у нас выводы одинаковые?

[NikolaRC]

ОК! Согласен.

[VctOs]

Посмотрите что получилось http://foto.rambler.ru/users/ntoz/2/44/
Попробуйте.

Попробовал.
Ситуация полностью аналогичная описаной NikolaRC: запрет проезда по стартовой дуге.

[VctOs]

На некоторые вопросы автор ядра не ответил, но это его авторское право.

Вопросов в каждом посте было много, поэтому, возможно, я что-то упустил.

Ну, вот взяли и оторвались, хотя должны соединять.

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

1. Сразу же после появления PocketGpsPro пользователи стали требовать третью точку при прокладке маршрута. На мой взгляд, все это достаточно просто. Всего-то тебуется проложить еще один маршрут от промежуточной точки, а затем сшить два маршрута. То, что это пока не реализовано, связано с какими-то нам непонятными техническими проблемами или это маркетинговая политика?

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

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

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

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

2. Решение полной задачи коммивояжера на КПК, это реально?

Не столько для Вас, сколько для других читателей напомню, что полная задача коммивояжера пока решается только полным перебором всех возможных вариантов. А всего таких вариантов может быть 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

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

Добавлю, что этой задачи пока в планах развития ядра почти не стоит.

[VctOs]

Я не согласен с автором по поводу термина "заштукатурить". По-моему нормальный нересурсоемкий ход.

Алгоритм хороший, но практически настолько же уязвимый для критики, как и существующая ситуация. Возможно, даже более уязвим: "Вот объявили, понимаешь, о фиксе, а глюки как были так и остались, время прокладки маршрута увеличилось и начало требоваться дополнительное вмешательство пользователя".

Перечень объектов-препятствий, относимых к непреодолимым и преодолимым (т.е непротяженным и объезжаемым) надо обдумать (или ввести критерии учета препятствий в настройки).

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

[Ромик]

Посмотрите что получилось http://foto.rambler.ru/users/ntoz/2/44/
Попробуйте.

Попробовал.
Ситуация полностью аналогичная описаной NikolaRC: запрет проезда по стартовой дуге.

Но при такой прокрадке маршрута - пользоваться нельзя

[PanD@]

Алгоритм хороший, но практически настолько же уязвимый для критики, как и существующая ситуация. Возможно, даже более уязвим: "Вот объявили, понимаешь, о фиксе, а глюки как были так и остались, время прокладки маршрута увеличилось и начало требоваться дополнительное вмешательство пользователя".

Согласен, что он не идеален. Но ведь и более строгое решение задачи приведет к такому же эффекту (по упомянутым причмнам) и тоже будет уязвимо, только еще больше. "Вот еще и ресурсов потребовали немеряно, а ... далее по тексту "

Писать надо не "Исправлена", а "Улучшена"

Перечень объектов-препятствий, относимых к непреодолимым и преодолимым (т.е непротяженным и объезжаемым) надо обдумать (или ввести критерии учета препятствий в настройки).

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

А кому сейчас легко?
Я думаю, что наверняка можно выбрать дефолтный набор, который будет устранять самые вопиющие ситуации. Ну а если кто боится и бордюров- кустарников, тому придется чаще помогать программе ручками (как будто он лучше знает где там можно проехать...).