Сетевое издание
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,940

ОПТИМИЗАЦИЯ НАБОРА ИНТЕРПОЛЯЦИОННЫХ ТОЧЕК ЛИНЕЙНОГО ОБЪЕКТА НА ОСНОВЕ ПРИНЦИПОВ ДИСКРЕТНОГО ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Беляков А.К. 1 Крицына Н.А. 2 Кулябичев Ю.П. 2 Суханов А.А. 2
1 ОАО "Концерн "СИСТЕМПРОМ"
2 Национальный исследовательский ядерный университет (МИФИ)
Рассматривается метод формирования оптимальной упорядоченной выборки М точек из общего набора интерполяционных точек кривой, обеспечивающих минимум интеграла квадрата ошибки интерполя-ции. Для решения задачи предлагается критерий, представленный в виде суммы частных интегральных критериев. Данный подход позволяет использовать для решения общей оптимизационной задачи прин-цип дискретного динамического программирования Беллмана. Предлагаемый метод разрабатывается для использования в геоинформационных системах при формировании баз данных, содержащих интер-поляционные точки линий (дорожная сеть, различные границы и прочие линейные объекты) для после-дующего их отображения на карте местности. А также для предварительной фильтрации данных, вы-званной ограничениями оперативной памяти при использовании в специализированных навигационных устройствах.
узловые точки
граф решения
критерий оптимизации
интерполяция
геоинформационная система
динамическое программирование
1. Бабич О.А. Обработка информации в навигационных комплексах. - М. : Машинострое-ние, 1991. - 512 с.
2. Крицына Н.А. Оптимизация параметров численного решения уравнений динамики // Алгоритмы цифрового оценивания, контроля и управления : сб. науч. трудов / под ред. д.т.н,, профессора Иващенко Н.Н. – М. : АТОМИЗДАТ, 1990, – 180 с.
3. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. — М. : Наука, 1978.
4. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: моде-ли и вычислительные алгоритмы : учеб. пособие. — Изд. 2-е, испр. — М. : ФИЗМАТЛИТ, 2003. — 240 с.
5. Таха Х. Введение в исследование операций : в 2-х кн. / пер. с англ. – М. : Мир, 1985. - 496 с. : ил.

В настоящее время геоинформационные системы нашли широкое применение в различных областях деятельности. Как правило, в геоинформационных системах границы областей и фронтов распространения различных физических процессов, линии уровня рельефа местности, траектории движения подвижных объектов и т.д. отображаются на карте с помощью сплайн-интерполяции выбранного порядка по упорядоченному множеству , состоящему из N точек (N - большое число). Причем многие из этих точек являются избыточными и могут быть выведены из базы данных без существенной потери точности интерполяции.

В этой связи актуальной становится задача определения упорядоченного набора M точек из первоначального множества точек , (). В качестве критерия выбора точек рационально поставить условие минимизации площади, находящейся между линией, построенной по M упорядоченным точкам (линия ), и линии, построенной по N упорядоченным точкам (линия ). Такой критерий эквивалентен интегралу квадрата отклонения точек линии от соответствующих точек линии (рис. 1).

Рис. 1. Пример формирования линии .

Для примера: N=11, M=6.

Пусть , – число точек множества между точками множества , тогда справедливы следующие соотношения:

1. - первые и последние точки множеств и совпадают;

2. - узловые точки линий и совпадают.

Так как узловые точки совпадают, то общая площадь между линиями может быть представлена в виде суммы площадей, заключенных между узловыми точками. При этом критерий оптимизации выбора точек из множества запишем в виде суммы

(1)

где - площадь фигуры, находящейся между узловыми точками. .

Так как общее число точек множества равно , то нетрудно заключить, что если первые точек последовательностей совпадают, то интервал между последними точками и будет содержать точек множества , и, наоборот, если последние точек последовательностей совпадают, то интервал между первыми точками и будет содержать точек множества . Кроме того, общее число точек – N. Таким образом, ограничения, накладываемые на аргумент оптимизации, будут иметь вид:

, - целое число. (2)

. (3)

Представление критерия (1) в виде суммы дает основание использовать принцип метода дискретного динамического программирования [3; 4].

Решение данной оптимизационной задачи удобно представить в виде ограниченного графа на сетке решений (рис. 2) [2; 5].

Рис. 2. Граф решения задачи методом дискретного динамического программирования.

Для примера:

Красной пунктирной линией отмечены «условно» оптимальные пути,

красной линией отмечен оптимальный путь.

По горизонтальной оси будем откладывать уровни решения задачи, причем число уровней соответствует числу точек множества ; по вертикальной оси – точки множества , в которые можно попасть на i-м уровне. Очевидно, в силу ограничений (2) и (3), каждый уровень (кроме первого и последнего) содержит точек.

Так как на первом уровне имеется единственная точка , то в точку второго уровня возможно попасть только единственным путем (рис. 2). При этом каждой точке уровня 2 будет соответствовать площадь фигуры , опирающейся на хорду между точками и (рис. 1). Значения этих площадей запоминаем.

При формировании третьего уровня в каждую точку уровня 3 возможно попасть многими путями из точек 2-го уровня (рис. 2). При этом каждому пути будет соответствовать свое значение суммы площадей

. (4)

(5)

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

, (6)

(7)

Полученные значения , запоминаем. На рисунке в качестве примера оптимальные пути для точек уровня 3 выделены красным цветом.

Описанную выше процедуру формирования точек уровня 3 повторяем для уровней В результате для уровня будем иметь следующие соотношения:

, (9)

(10)

Полученные значения , запоминаем.

Последний уровень M имеет только одну точку , попасть в которую можно из точек предыдущего уровня (рис. 2). Причем каждому пути будет соответствовать значение площади:

(11)

Найдем единственный путь, обеспечивающий минимум критерия (11):

, (12)

(13)

Используя соотношения (12), (9) и (6), пройдем весь путь по оптимальным точкам в обратном направлении:

(14)

Перечисленная в (14) последовательность будет оптимальным набором точек множества , обеспечивающих минимум критерия (1).

Зная номера точек множества , входящих в множество , нетрудно найти оптимальное число точек между узлами .

Приведенный алгоритм может быть применен в информационных системах различного назначения для «фильтрации» большого объема данных при обработке линейных объектов. В частности, маршрутов (треков), полученных с помощью автоматизированных средств записи перемещения объектов (GPS/ГЛОНАСС-приемники), для уменьшения времени обработки изображений различных линейных объектов в ГИС.

Кроме того, многие специализированные навигационные устройства позволяют загружать в память пути (треки) с ограниченным количеством точек (например, максимальное количество точек пути, которые можно загрузить в популярные устройства серии FORERUNNER производства компании GARMIN составляет 500 точек). Приведенный метод позволяет осуществлять предварительную обработку данных для загрузки в такие устройства [1]. Особенностью метода является максимальное сохранение степени кривизны исходного линейного объекта при заданном уровне фильтрации.

Рецензенты:

Загребаев Андрей Маркоянович, д.т.н., профессор, Национальный исследовательский ядерный университет (МИФИ), г. Москва.

Крянев Александр Витальевич, д.ф-м.н., профессор, Национальный исследовательский ядерный университет (МИФИ), г. Москва.


Библиографическая ссылка

Беляков А.К., Крицына Н.А., Кулябичев Ю.П., Суханов А.А. ОПТИМИЗАЦИЯ НАБОРА ИНТЕРПОЛЯЦИОННЫХ ТОЧЕК ЛИНЕЙНОГО ОБЪЕКТА НА ОСНОВЕ ПРИНЦИПОВ ДИСКРЕТНОГО ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ // Современные проблемы науки и образования. – 2013. – № 3. ;
URL: https://science-education.ru/ru/article/view?id=9371 (дата обращения: 20.09.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074