Динамическое программирование как метод сплайн-аппроксимации в САПР линейных сооружений

Аннотация

В статье рассматриваются математические модели и алгоритмы решения задач, возникающих при автоматизации проектирования трасс линейных сооружений. Принципиальная особенность этих задач состоит в том, что план и продольный профиль трассы состоят из элементов заданного вида. В зависимости от вида сооружения в проектной практике используются отрезки прямых, дуги окружностей, парабол и клотоид. В любом случае необходимо получить гладкую кривую, состоящую из нужной последовательности элементов заданного вида. На стыках элементы имеют общую касательную, а в наиболее сложном случае и общую кривизну. При этом параметры элементов должны удовлетворять техническим ограничениям, которые формализуются в виде системы неравенств. Такого рода кривые принято называть сплайнами. Важно подчеркнуть, что число элементов искомого сплайна, как правило, неизвестно и определяется в процессе решения задачи. Это обстоятельство существенно усложняет и не позволяет применить для решения методы нелинейного программирования, так как неизвестна ее размерность. Кроме того, искомый сплайн – это экстремаль некоторого функционала. Ранее была решена задача аппроксимации плоской кривой, заданной последовательностью точек, сплайном, состоящим из отрезков парабол. В данной статье рассматривается сплайн, включающий элементы различного вида, в том числе и наиболее сложная задача поиска сплайна, состоящего из последовательности отрезков: прямая+клотоида+окружность+клотоида+прямая и т.д. Этот сплайн в статье называется сплайн с клотоидами. Приводится оригинальная формализация задачи, которая для поиска сплайнов позволяет применять динамическое программирование, а также новый алгоритм.