О вычислении веса подзадач при вершинной минимизации недетерминированных конечных автоматов методом ветвей и границ

Актуальность и цели. Рассматриваются различные аспекты построения итерационных аnytimе-алгоритмов для решения задачи вершинной минимизации недетерминированных конечных автоматов. Хотя данная задача была поставлена еще в 60-е гг. ХХ в., она является NР-трудной, поэтому разработка эффективных алгоритмов ее решения остается актуальной проблемой. Цель исследования: анализ влияния выбора различных вариантов весовых характеристик подзадач метода ветвей и границ на эффективность базового варианта алгоритма и его модификаций, использующий различные эвристики. Материалы и методы. Исследование основано на анализе численных экспериментов, выполненных с использованием программной реализации описанных алгоритмов. Программа реализована на языке С# 6.0 для платформы .NЕТ Frаmеwоrk. Результаты. Результатами являются выявленные закономерности, связанные с выбором весовых характеристик подзадач в методе ветвей и границ для алгоритма вершинной минимизации недетерминированных конечных автоматов. Выводы. Определены варианты весовых характеристик, являющиеся оптимальными как для базового алгоритма, так и для его модификаций, снабженных дополнительными эвристиками. Также показано, что применение этих весовых характеристик совместно с дополнительными эвристиками позволяет существенно повысить эффективность разработанных алгоритмов.