RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский журнал чистой и прикладной математики // Архив

Вестн. НГУ. Сер. матем., мех., информ., 2012, том 12, выпуск 1, страницы 91–101 (Mi vngu110)

Эта публикация цитируется в 1 статье

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

Ю. А. Кочетовa, М. Г. Сивыхb, А. В. Хмелёвb, А. В. Яковлевb

a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, Новосибирск, 630090, Россия
b Новосибирский государственный университет, ул. Пирогова, 2, Новосибирск, 630090, Россия

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

Ключевые слова: локальный поиск, метаэвристики, сжатие информации.

УДК: 519.21

Поступила в редакцию: 18.05.2010



© МИАН, 2024