Составители:
Рубрика:
измерителя СРНС "Navstar", а группа Э. Кракивского из канадского универ-
ситета в г. Калгари провела исследование возможности использования калма-
новской фильтрации данных одометра, компаса и ПИ РНС в алгоритмах ММ.
Прокладка оптимального маршрута.
Перед тем, как водитель НТС начнет свое передвижение из места его
расположения А в требуемую точку назначения В,
программно-математическое
обеспечение ТИУРЭС может предложить ему на электронной карте местности
маршрут следования. Для этого в БРЭК или в ПК радиооператора необходимо
ввести координаты точек А и В, критерий оптимальности маршрута, промежу-
точные точки маршрута, характеристики НТС (класс, масса, высота, ширина,
длина). С помощью электронно-картографического обеспечения процессор
ТИУРЭС строит направленный
окрашенный граф автодорожной сети города,
соответствующий данным характеристикам НТС, и запускает подпрограмму
прокладки оптимального маршрута следования (path finding) НТС из точки А в
точку В через промежуточные точки.
Первый алгоритм прокладки кратчайшей траектории на графе известен как
алгоритм Дийкстры (Dijkstra). Для реализации алгоритмов прокладки маршрута
требуется соответствующая цифровая автодорожная карта. Алгоритмы нахож-
дения оптимального маршрута движения по дорожной сети условно делятся на
строгие и эвристические.
Строгие алгоритмы обладают двумя существенными недостатками: необ-
ходимость заполнения большого объема промежуточных результатов и выпол-
нения огромного числа машинных операций.
Эвристические алгоритмы достаточно хорошо работают на простых авто-
дорожных сетях типа дорожной решетки. Однако если эта сеть разбивается
на
блоки, связанные между собой одной-двумя улицами (например, районы горо-
да, расположенные на разных берегах реки или на островах, связанных между
собой небольшим количеством мостов), или имеет тупиковые улицы, или вклю-
чает объезды клинообразных непроезжих зон типа подъездных железно-
дорожных веток, оврагов, заливов, озер и т. п., то простые
эвристические алго-
ритмы работают нерационально и выдают маршрут следования, далекий от
оптимального. В этом случае следует разбивать автодорожный граф на под-
графы и искать варианты точек выхода и входа этих подграфов; затем строить
варианты маршрутов пересечения этих подграфов и следования внутри око-
нечных подграфов к точкам А и В и, наконец
, из построенных участков
маршрута составлять варианты общего маршрута следования из точки А одного
подграфа в точку В другого и из них выбирать маршрут, имеющий наимень-
шую из построенных вариантов маршрутов длину (или время прохождения).
Разработка такого алгоритма – задача не формализуемая, а ее решение
зависит от конкретных условий применения РСДУ и
квалификации програм-
мистов, разрабатывающих программно-математическое обеспечение ТИУРЭС.
Найденное программистами решение проходит испытание на автодорожной
сети данной территории и обычно является "know how" разработчиков ПМО: их
интеллектуальной собственностью. Эффективность эвристических алгоритмов
99
Страницы
- « первая
- ‹ предыдущая
- …
- 98
- 99
- 100
- 101
- 102
- …
- следующая ›
- последняя »
