Теория и практика решения NP-трудной задачи структурного синтеза программными средствами

Авторы

Анисимов А. В.^*, Романова Т. Н.^**

ФГБОУ ВПО «Московский государственный технический университет имени Н. Э. Баумана», 105005, Москва, 2-я Бауманская ул., д. 5, с. 1

*e-mail: alan_mephi@mail.ru
**e-mail: rtn@bmstu.ru

Аннотация

В статье приводится пример решения NP-трудной задачи структурного синтеза, которая возникает при автоматизации промышленных предприятий. Формулируется оптимизационная постановка задачи, описывается программная реализация трёх методов поиска приближённого решения и одного метода поиска точного решения для такого класса задач. Приводятся структуры данных, использованные при реализации методов, а также сравнение аналитических и расчетных оценок точности и сложности оптимизационных методов.

Ключевые слова:

структурный синтез; NP-трудность; приближённый метод; метод локальных улучшений; полный перебор; жадный алгоритм Радо-Эдмондса; комбинаторно-оптимизационная задача; асимптотическая оценка вычислительной сложности