Эпсилон-сетевой алгоритм минимизации функционалов на комплексах элементов

Аннотация

в данной работе представлен ε-сетевой алгоритм минимизации функционалов на комплексах элементов с заданной ранговой структурой. Основной проблемой при анализе высокодетализированных комплексов является рост вычислительной сложности, связанный с увеличением пространства состояний. Для ее сокращения предложен метод факторизации множества состояний с использованием ε-сетей, позволяющий заменить исходную структуру укрупненным графом. Элементы нулевого ранга объединяются в классы по заданной метрике, а классы элементов старших рангов формируются по классам составляющих их элементов. В статье использована лексикографическая оптимизация целевого функционала, при которой сначала минимизируется число переходов между ε-классами, а затем — длина маршрута в исходном комплексе. Работа алгоритма показана на примере полиэдрального комплекса при решении задачи маршрутизации в информационной модели реального здания. Рассматриваемая модель включает узлы, ребра, грани и пространственные ячейки здания. Программная реализация обеспечивает построение исходного и факторизованного графов, поиск обычного, ε-классового и лексикографического маршрутов, а также их визуальное сравнение. Предложенный подход может быть применен к другим функционалам, заданным на комплексах элементов, при выборе меры близости и правил формирования классов.