Карпов Дмитрий Анатольевич, кандидат технических наук, заведующий кафедрой общей информатики Института искусственного интеллекта
119454, Москва, пр-т Вернадского, д. 78
Dmitry A. Karpov, Cand. Sci. (Eng.), Head of the General Informatics Department, Institute of Artificial Intelligence
78, Vernadskogo pr., Moscow, 119454
Струченков Валерий Иванович, доктор технических наук, профессор, профессор кафедры общей информатики Института искусственного интеллекта
119454, Москва, пр-т Вернадского, д. 78
Valery I. Struchenkov, Dr. Sci. (Eng.), Professor, General Informatics Department, Institute of Artificial Intelligence
78, Vernadskogo pr., Moscow, 119454
Цели. Методы сплайн-аппроксимации последовательности точек на плоскости получают все более широкое применение в различных областях. Сплайн рассматривается как однозначная функция с известным числом повторяющихся элементов. Наиболее широкое применение получили полиномиальные сплайны. Применительно к проектированию трасс линейных сооружений приходится рассматривать задачу с неизвестным числом элементов. Алгоритм решения задачи применительно к проектированию продольного профиля реализован и опубликован ранее. В этой задаче элементами сплайна являются дуги окружностей, сопрягаемые отрезками прямых, и сплайн представляет собой однозначную функцию. Однако при проектировании плана трассы в общем случае сплайн является многозначной функцией. Поэтому разработанный ранее алгоритм не пригоден для решения этой задачи, даже в случае использования тех же элементов сплайна. Цель настоящей статьи – обобщение полученных результатов на случай аппроксимации многозначных функций с учетом особенностей проектирования трасс линейных сооружений. На первом этапе работы было определено число элементов аппроксимирующего сплайна с помощью динамического программирования. В статье рассматривается следующий этап решения задачи.
Методы. Для оптимизации параметров сплайна используется новая математическая модель в виде модифицированной функции Лагранжа и специальный алгоритм нелинейного программирования. При этом удается вычислять аналитически производные целевой функции по параметрам сплайна при отсутствии ее аналитического выражения через эти параметры.
Результаты. Разработаны математическая модель и алгоритм оптимизации параметров сплайна (как многозначной функции), состоящего из дуг окружностей, сопрягаемых отрезками прямых. Начальным приближением является сплайн, полученный на первом этапе.
Выводы. Двухэтапная схема сплайн-аппроксимации при неизвестном числе элементов сплайна, предложенная ранее, пригодна и для аппроксимации многозначных функций, заданных последовательностью точек на плоскости, в частности для проектирования плана трасс линейных сооружений.
Objectives. Methods for spline approximation of a sequence of points in a plane are increasingly used in various disciplines. A spline is defined as a single-valued function consisting of a known number of repeating elements, of which the most widely used are polynomials. When designing the routes of linear structures, it is necessary to consider a problem with an unknown number of elements. An algorithm implemented for solving this problem when designing a longitudinal profile was published earlier. Here, since the spline elements comprise circular arcs conjugated by line segments, the spline is a single-valued function. However, when designing a route plan, the spline is generally a multivalued function. Therefore, the previously developed algorithm is unsuitable for solving this problem, even if the same spline elements are used. The aim of this work is to generalize the obtained results to the case of approximation of multivalued functions while considering various features involved in designing the routes of linear structures. The first stage of this work consisted in determining the number of elements of the approximating spline using dynamic programming. In the present paper, the next stage of solving this problem is carried out.
Methods. The spline parameters were optimized using a new mathematical model in the form of a modified Lagrange function and a special nonlinear programming algorithm. In this case, it is possible to analytically calculate the derivatives of the objective function with respect to the spline parameters in the absence of its analytical expression.
Results. A mathematical model and algorithm were developed to optimize the parameters of a spline as a multivalued function consisting of circular arcs conjugated by line segments. The initial approximation is the spline obtained at the first stage.
Conclusions. The previously proposed two-stage spline approximation scheme for an unknown number of spline elements is also suitable for approximating multivalued functions given by a sequence of points in a plane, in particular, for designing a plan of routes for linear structures.
The authors declare that there are no conflicts of interest present.