Как найти навигационный путь

Когда вы пользуетесь навигатором, вы указываете точку А и точку Б, и дальше навигатор как-то сам строит маршрут. Сегодня посмотрим, что лежит в основе алгоритма, который это делает. Просто ради интереса. 

Графы и «задача коммивояжёра»

Ещё до появления навигаторов у людей была такая же проблема: как найти кратчайший путь из одного места в другое, если есть ограниченное количество промежуточных точек? Или как объехать ограниченное количество точек, затратив минимальные усилия. В общем виде это называется «задачей коммивояжёра», и мы уже рассказывали, в чём там идея:

Если взять просто города и расстояния между ними, то с точки зрения математики это называется графом: города будут вершинами графа, а дороги между ними — рёбрами графа. Если мы знаем длину каждой дороги, то это будет значением (весом) рёбер графа. Этой теории нам уже хватит, чтобы понять, как работает навигатор в машине.

Алгоритм Дейкстры — ищем самый быстрый путь

Как только появилось решение полным перебором, математики стали искать другой подход, который работал бы гораздо быстрее и не требовал бы вычисления такого огромного объёма данных. В 1959 году Эдсгер Дейкстра придумал свой алгоритм, которым пользуются до сих пор. Идея его в том, чтобы не перебирать все варианты, а находить самый короткий путь только между соседними графами — и так, шаг за шагом, продвигаться к конечной точке.

Допустим, у нас есть улицы, перекрёстки и мы знаем время пути между ними. Нарисуем это в виде графа, а чтобы было проще ориентироваться — сделаем визуально всё одинаковой длины:

Чтобы найти самый быстрый путь из А в Б, мы смотрим сначала, какие пути у нас выходят из точки А. Видно, что поехать вниз будет быстрее, чем поехать направо:

Значит, выбираем путь вниз. Теперь делаем то же самое для этой точки — смотрим, где быстрее: справа или внизу. Вниз быстрее (1 меньше, чем 4), поэтому едем по ней:

При этом мы не отбрасываем уже сделанные вычисления (всё равно уже посчитали), а запоминаем их на всякий случай. Из нижней точки есть только одна дорога — направо, поэтому едем по ней:

А теперь у нас получилась интересная ситуация: в центральную точку мы можем попасть как сверху, так и снизу, при этом и там, и там у нас одинаковое время — 3 минуты. Значит, посчитаем оба варианта — вдруг сверху будет быстрее и нам нужно будет перестроить маршрут заново:

Оказывается, снизу ехать до центра быстрее, чем сверху — 4 минуты вместо 6, поэтому оставляем нижний маршрут. Наконец, из центральной точки до точки Б всего один путь — направо, поэтому выбираем его:

Как видите, нам не пришлось считать все варианты со всеми точками, а до некоторых мы просто не добрались. Это сильно сэкономило время и потребовало меньше ресурсов для вычисления.Такой алгоритм и лежит в основе автомобильных навигаторов — с вычислениями справится даже бюджетный смартфон.

Что ещё учитывает навигатор

Чтобы алгоритм оставался простым и работал только со временем, все остальные параметры дорог тоже привязывают ко времени. Покажем, как это работает, на паре примеров.

Комфорт. Если нам нужно построить не самый быстрый, а самый комфортный маршрут, то мы можем отдать предпочтение автомагистралям и дорогам с несколькими полосами — на них обычно и асфальт получше, и резких поворотов поменьше. Чтобы навигатор выбирал именно такие дороги, им можно присвоить коэффициент 0,8 — это виртуально сократит время на дорогу по ним на 20%, а навигатор всегда выберет то, что быстрее. 

С просёлочными и грунтовыми дорогами ситуация обратная. Они редко бывают комфортными, а значит, им можно дать коэффициент 1,3, чтобы они казались алгоритму более долгими и он старался их избегать. А лесным дорогам можно поставить коэффициент 5 — навигатор их выберет, только если это единственная дорога то точки назначения.

Сложность маршрута и реальное время. Маршрут из А в Б почти никогда не бывает прямым — на нём всегда есть повороты, развороты и съезды, которые отнимают время. Чтобы навигатор это учитывал, в графы добавляют время прохождения поворота — либо коэффициентом, либо отдельным параметром. Из-за этого алгоритм будет искать действительно быстрый маршрут с учётом геометрии дорог.

Пробки. Если есть интернет, то всё просто: навигатор получает данные о состоянии дорог и добавляет разные коэффициенты в зависимости от загруженности. Иногда навигатор ведёт дворами, когда трасса свободна — это не ошибка навигатора, а его прогноз на время поездки: если через 10 минут в этом месте обычно собираются пробки, то там лучше не ехать, а заранее поехать в объезд.

Если интернета нет, то алгоритм просто использует усреднённую модель пробок на этом участке. Эта модель скачивается заранее и постоянно обновляется в фоновом режиме.

Как построить маршрут по всей России

Если нам нужно построить маршрут из Брянска в Тулу, то с точки зрения компьютера это безумно сложная задача: ему нужно перебрать десятки тысяч улиц и миллионы перекрёстков, чтобы понять, какой путь выбрать. С этим плохо справляется даже обычный компьютер, не говоря уже о телефоне.

Если мы в Яндекс Картах построим такой маршрут, то навигатор нам предложит сразу 4 варианта:

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

Например, если мы поедем в Тулу не из Брянска, а из Синезёрок, то поменяется только начальный маршрут по трассе М3, а всё остальное останется прежним:

Получается, что навигатору не нужно всё пересчитывать — он находит только ключевые точки пути, а маршрут между ними уже просчитан до этого. Этот приём работает и при перестроении маршрута во время движения: навигатор смотрит, как нужно поменять путь, чтобы вернуть вас на уже известную дорогу.

Что дальше

Следующий этап — напишем алгоритм Дейкстры сами и посмотрим, как он работает по шагам.

Установить навигационный путь. Или не знаете как это делается? В таком случае помогает чтение мануала на железо.

Это самый лучший ответ…

Я с рук купил навигатор, проехал с ним 5 000км и всё было хорошо, потом мне сказали что его нужно обновить, на вопрос “как,” было сказало “navitel.ru там всё найдешь”, я нашел “Navitel Navigator Update Center” с моей версии 7 было предложено обновить до 9, после проследования инструкциям очень долго ждал пока сохраняли резервную копию, потом скачивали карты, потом их устанавливали, и когда всё это наконец закончилось я отключаю навигатор от ПК, нажимаю “Навигация” и вижу “!Установите навигационный путь!”….

Очень долго просм перед всеатривая а интернете подобные случаи я узнал, чтом этим надо было зарегестрировать устройство на сайте, а ключи хранились в корневой папке навигатора, там был текстовый фаил с серийным номером и ключом активации, после установки обновления у меня в навигаторе осталось только две папки “Navitel” “NavitelContent”

Мне надо найти и установить навигационный путь, что бы найти свой ключ, что бы включить этот чертов навигатор

P.S. востанавливать резервную копию уже пробовал, всё те же две папки и всё тот же “!Установите навигационный путь!”

Изменено 8 ноября 2015 пользователем NFoX33

Поздравляем вас с приобретением GPS-навигатора. Если это ваше первое устройство GPS (система глобального позиционирования), то вероятно у вас возникнут вопросы по его использованию. В статье в краткой форме даны советы как правильно пользоваться GPS-навигатором.

Четыре основные функции GPS-навигатора.

Практически у каждого портативного GPS-приёмника доступны четыре основные функции:

• Отображение местоположения: На основе данных со множества спутников GPS-навигатор точно определяет ваше местоположение в виде координат — широты и долготы, а также в системе координат UTM.
• Навигация от точки к точке: Место расположения или назначения называется «точка трека». Например, вы можете установить отправную точку маршрута с помощью функции отображения месторасположения. И если вам известны координаты места назначения, взятые с обычной или компьютерной карты, рекламного буклета, интернета и других источников, то GPS-навигатор может отобразить маршрут по прямой линии и расстояние к пункту назначения. Но так как маршруты редко идут по прямой линии, то по мере передвижения эта линия будет изменяться. Также с приближением к цели будет уменьшаться расстояние к месту назначения.
• Навигация по маршруту: Вы можете задать несколько промежуточных точек маршрута и передвигаться от точки к точке. На каждом этапе показывается направление и расстояние до следующей точки маршрута. То есть, как только вы достигнете первой заданной точки маршрута, GPS-приёмник автоматически направит вас к следующей точке или же вы сможете сделать это вручную.
• Запись маршрута: К одной из самых полезных функций GPS-навигатора относится его способность записывать маршрут в виде пройденных точек. Эта функция отличается от функции навигации по маршруту, которая подробно указывает в каком направлении вы идёте. Вы можете настроить GPS-навигатор так, чтобы он автоматически отмечал пройденные точки маршрута через определённые промежутки времени или расстояния. Чтобы пройти маршрут в обратном направлении, просто следуйте назад по записанной GPS-навигатором последовательности точек маршрута.

Базовые принципы использования GPS-навигатора.

GPS-приёмник не может заменить карту и компас, а также навыки по их использованию. Технологии GPS улучшают навигационные способности, но вы всё равно должны купить компас и подробную карту местности.

Не полагайтесь только на GPS-навигатор. Всегда носите с собой карту и компас.

GPS-приёмник необходимо использовать совместно с картой. Наиболее полезны топографические карты с масштабом 1:24000.

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

Основные навыки эксплуатации GPS-навигатора.

Как поймать спутники.

Чтобы GPS-навигатор мог предоставить надёжные навигационные данные, в том числе ваши координаты, он должен получать хорошие сигналы по крайней мере от четырёх спутников. Чтобы «словить» спутник, включите GPS-навигатор и перейдите на экран спутники:

1. Отобразится текущая конфигурация спутников и мощность их сигналов. На установление связи со спутниками GPS-устройству может потребоваться несколько минут, так что наберитесь терпения.
2. Если GPS-навигатор «видит» только несколько спутников со слабыми сигналами, то указаниям GPS-навигатора доверять нельзя. Пользуйтесь только компасом и картой.
3. GPS-приёмник лучше всего «видит» спутники на фоне чистого неба. Получению сигнала могут препятствовать деревья, высокие здания и каньоны.
4. Чтобы быстрее поймать спутники, отключите и включите опять GPS-устройство.
5. Убедитесь, что батарея полностью заряжена.

Интерпретация координат.

Система координат используется с целью упрощения навигации по карте. Сетка координат на карте определяет конкретное место, указывая его положение по направлениям север / юг и восток / запад. Чтобы выбрать используемую систему координат, перейдите к экрану настроек. Наиболее распространенные системы координат, используемые в GPS-навигации:

• DMS (градусы / минуты / секунды): Это стандартный метод указания широты и долготы:
  Пример: N47° 37′ 12″ W122° 19′ 45″.
  В этом примере N47° 37′ 12″ означает, что по направлению север/юг вы находитесь на 47 градусов, 37 минут и 12 секунд к северу от экватора, а W122° 19′ 45″ указывает по направлению восток/запад на 122 градусов, 19 минут и 45 секунд к западу от нулевого меридиана (Гринвич, Англия).
• DDM (градусы/минуты): Это десятичная версия DMS. Используется во время игр с использованием GPS-устройств.
  Пример: N47° 37,216′ W122° 19,75′.
  Аналогично указывает координаты в направлениях север/юг и восток/запад. Различие состоит только в том, что секунды отображаются в десятичной системе, то есть делятся на 60.
• UTM (система координат UTM): Это военная система координат, не привязанная к широте и долготе. Карта делится на квадраты шириной по 1000 метров. На большинстве топографических карт нанесены линии UTM. Система работает на базе метрической системы и не требует преобразования минут и секунд.
  Пример: 10Т 0550368 5274319.
  Здесь «10Т» указывает зону карты, «восточный» номер «0550368» показывает расположение в направлении восток / запад, а «северный» номер «5274319» в направлении север / юг.
  
  Система координат UTM.

GPS-навигатор способен автоматически отображать координаты в любой из выбранной вами систем. Также он может преобразовывать координаты из одной системы в другую. Это полезно, если у вас есть координаты в одной системе (например, UTM), но вы хотите перейти в другую (например, DDM).

Навыки навигации.

Ввод точек маршрута.

Построить маршрут с помощью точек совсем несложно. Необходимо просто нажимать кнопку ТОЧКА (на некоторых устройствах требуется нажать и удерживать кнопку ВВОД). Отметить текущую точку маршрута можно всего лишь одним нажатием кнопки. Вы также можете добавить различное описание: название (например «начало маршрута» или «водопад»), координаты, высоту и даже короткую заметку. Это особенно полезно, если вы ещё дома отметите точки маршрута.

В качестве точек маршрута можно отметить ориентиры местности.

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

Следование по точкам маршрута.

Имея введённые точки маршрута, GPS-навигатор может направлять вас от точки к точке. Используйте кнопки НАЙТИ и ИДТИ ДО, чтобы определить конкретную целевую точку маршрута. Затем переключитесь на экран КОМПАС, где GPS-навигатор укажет направление движения, приблизительно оценит расстояние и время движения.

Запись маршрута.

Если вы совершаете поездки из базового лагеря по незнакомой местности без заранее утверждённого маршрута, то одной из самых полезных функций GPS-приёмника является «отслеживание маршрута». При задействовании функции отслеживания маршрута GPS-устройство начинает автоматически наносить точки маршрута по мере вашего движения, то есть создаёт цепочку посещённых точек.

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

Дополнительные полезные возможности GPS-навигатора.

Датчики.

GPS-навигатор содержит два типа датчиков: барометрический высотомер и магнитный компас.

• Барометрический высотомер: Все GPS-устройства способны рассчитывать высоту на основе спутниковых данных. Но барометрическому высотомеру не требуются сигналы от спутников. Когда спутниковые сигналы становятся настолько слабыми, что на них нельзя полагаться, барометрический высотомер по прежнему показывает точную высоту. Так как барометрический высотомер измеряет давление воздуха, то по графику атмосферного давления вы можете спрогнозировать погоду.
  
  Барометрический высотомер отображает вашу высоту и помогает спрогнозировать погоду.
• Магнитный компас: Магнитный компас работает аналогично классическому компасу. Так как обычный магнитный компас в отличие от встроенного в GPS-навигатор не потребляет электричества, то с целью увеличения времени работы GPS-устройства от аккумулятора вы можете отключить встроенный компас и пользоваться обычным компасом. Это не повлияет на навигационные возможности GPS-навигатора, которые зависят от сигналов со спутников.
  

  Экран компаса предоставляет множество полезной информации.

Карты памяти.

Кроме предустановленных карт многие GPS-устройства позволяют загружать дополнительные карты с помощью программного обеспечения, идущего в комплекте на CD-ROM дисках. Некоторые GPS-навигаторы могут использовать сменные карты памяти microSD. На предустановленные карты обычно уже записана вся необходимая информация. Также вы можете отдельно купить карту памяти и с помощью компьютера загрузить на неё данные. Обязательно постарайтесь выбрать GPS-навигатор, позволяющий использовать карты памяти, так как это значительно упростит и облегчит работу с картами. Например, вы можете записать на карту памяти множество различных карт городов, топографических, морских и других карт.

Полезные советы по использованию GPS-навигатора.

Одна из самых распространенных жалоб от людей, которые только приобрели свой первый GPS-приёмник, заключается в сложностях приёма стабильного сигнала. Если вы испытываете подобные проблемы, то обратитесь к руководству пользователя или обратите внимание на следующее:

Установка связи со спутниками: Постарайтесь «поймать» спутники ещё перед заходом в лес, где добиться устойчивого приёма будет куда сложнее.

Расположение GPS-устройства: Чтобы обеспечить GPS-приёмнику беспрепятственный доступ к небу, прикрепите его к ремню рюкзака. Если вы несёте GPS-устройство в руках, то старайтесь не размахивать ими, чтобы не дезориентировать приёмник.

Избегайте препятствий: Точность и польза от GPS-приёмника полностью зависит от его способности принять чёткие сигналы от четырёх и более спутников. Если небо закрыто, то получить сигналы со спутников будет сложно и на данные GPS-устройства нельзя полностью полагаться. В этом случае просто постарайтесь подняться выше на открытый участок местности. Одновременно выключите энергосберегающий режим. GPS-навигаторы, оснащённые современными микросхемами, такими как SiRF Star III, позволяют практически в любых условиях получить мощный и стабильный сигнал.

Инициализация: Выполните эту простую процедуру, если ваш новый GPS-приёмник даже при чистом небе не очень хорошо принимает сигналы со спутников. Так как большинство GPS-навигаторов производится в Азии, то при первом включении он «помнит» азиатские спутники. При инициализации GPS-навигатор учтёт текущую обстановку и загрузит информацию с новых спутников, что поможет быстрее и эффективнее ловить спутники в будущем.

Инструкцию по инициализации вашего GPS-устройства можно получить из руководства пользователя.

Батареи: Перед началом путешествия убедитесь, что аккумулятор полностью заряжены и обязательно возьмите запасные. С целью экономии заряда батареи отключите ненужные функции, такие как прокладывание маршрута или подсветка.

Совет: Лучшим выбором для GPS-навигатора являются литий-ионные аккумуляторы из-за их долговечности. Однако следует учитывать, что совершенно новые литий-ионные аккумуляторы могут вызывать кратковременные скачки напряжения, что приводит к образованию неприятных горизонтальных полос на экранах некоторых GPS-навигаторов. Чтобы решить данную проблему, перед тем, как вставить литиевый аккумулятор в GPS-устройство, просто используйте их в других электронных устройствах в течение нескольких минут.

Цена вопроса: 0 ₽
Пробег: 14 000 км