Методы локального поиска для одной задачи о перестановке столбцов бинарной матрицы

Abstract

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