Информатика и автоматизация (Nov 2024)
Решение задач перебора путей в сложных графах
Abstract
Моделирование различных систем связано с перебором значений параметров элементов структуры и учетом всех характеристик функционирования и взаимодействия компонентов для нахождения определенного набора решений, определяющих конфигурацию системы. Такие задачи относятся к задачам переборного типа и подразумевают, что некоторое количество очередных решений из этого набора получается из предыдущего решения в определенном порядке. Известно, что достаточно большое количество задач переборного типа решается только методами полного перебора и других методов для их точного решения пока не существует. В статье представлен новый метод перебора путей в графе – метод трансформации узлов-графов. По предварительной оценке, предложенный метод, в отличие от существующих, позволяет значительно быстрее осуществлять поиск всех простых путей в ориентированном графе произвольной структуры. В известных методах перебора в графе (Breadth First Search и Depth First Search) объектом перебора является путь. Всё количество таких путей в графе определяет размер пространства перебора. Основная идея метода трансформации узлов-графов заключается в значительном уменьшении размера пространства перебора за счет укрупнения объектов перебора. Укрупнение объектов перебора осуществляется кластеризацией путей в комбинаторные объекты, объединяющие по определенному регламенту некоторое множество путей одинаковой длины. Такие комбинаторные объекты названы узлами-графами. Узел-граф относится к центрально-периферическим комбинаторным объектам и для перебора всех путей в графе разработаны специфические операции преобразования узлов-графов, которые позволяют найти следующие пути на основе предыдущих. Метод может использоваться как базовый инструментарий для уменьшения размерности пространства поиска решений NP-полных задач, сохраняя универсальность и точность перебора.
Keywords
