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

Авторы

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

Московский государственный технический университет им. Н.Э. Баумана, 2-я Бауманская ул., 5, стр. 1, Москва, 105005, Россия

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

Аннотация

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

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

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