|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Математика
О вычислении веса подзадач при вершинной минимизации недетерминированных конечных автоматов методом ветвей и границ
М. Э. Абрамян Южный федеральный университет, Ростов-на-Дону, Россия
Аннотация:
Актуальность и цели. Рассматриваются различные аспекты построения итерационных аnytimе-алгоритмов для решения задачи вершинной минимизации недетерминированных конечных автоматов. Хотя данная задача была поставлена еще в 60-е гг. ХХ в., она является NР-трудной, поэтому разработка эффективных алгоритмов ее решения остается актуальной проблемой. Цель исследования: анализ влияния выбора различных вариантов весовых характеристик подзадач метода ветвей и границ на эффективность базового варианта алгоритма и его модификаций, использующий различные эвристики. Материалы и методы. Исследование основано на анализе численных экспериментов, выполненных с использованием программной реализации описанных алгоритмов. Программа реализована на языке С# 6.0 для платформы .NЕТ Frаmеwоrk. Результаты. Результатами являются выявленные закономерности, связанные с выбором весовых характеристик подзадач в методе ветвей и границ для алгоритма вершинной минимизации недетерминированных конечных автоматов. Выводы. Определены варианты весовых характеристик, являющиеся оптимальными как для базового алгоритма, так и для его модификаций, снабженных дополнительными эвристиками. Также показано, что применение этих весовых характеристик совместно с дополнительными эвристиками позволяет существенно повысить эффективность разработанных алгоритмов.
Ключевые слова:
недетерминированные конечные автоматы, минимизация, метод ветвей и границ, эвристический алгоритм, программная реализация.
Образец цитирования:
М. Э. Абрамян, “О вычислении веса подзадач при вершинной минимизации недетерминированных конечных автоматов методом ветвей и границ”, Известия высших учебных заведений. Поволжский регион. Физико-математические науки, 2021, № 2, 45–62
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivpnz28 https://www.mathnet.ru/rus/ivpnz/y2021/i2/p45
|
Статистика просмотров: |
Страница аннотации: | 39 | PDF полного текста: | 23 | Список литературы: | 14 |
|