|
Вестник НГУ. Серия: Математика, механика, информатика, 2012, том 12, выпуск 1, страницы 91–101
(Mi vngu110)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Методы локального поиска для одной задачи о перестановке столбцов бинарной матрицы
Ю. А. Кочетовa, М. Г. Сивыхb, А. В. Хмелёвb, А. В. Яковлевb a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, Новосибирск, 630090, Россия
b Новосибирский государственный университет, ул. Пирогова, 2, Новосибирск, 630090, Россия
Аннотация:
Разработаны и исследованы итерационные методы локального поиска для решения известной задачи о перестановке столбцов бинарной матрицы. Эта задача является NP-трудной в сильном смысле, и для широкого класса полиномиальных алгоритмов относительная погрешность в худшем случае может оказаться сколь угодно большой величиной. В данной работе показано, что разработанные итерационные методы локального поиска быстро находят оптимальное решение или решение с малой относительной погрешностью, если число строк и столбцов матрицы не превосходит 100.
Ключевые слова:
локальный поиск, метаэвристики, сжатие информации.
Поступила в редакцию: 18.05.2010
Образец цитирования:
Ю. А. Кочетов, М. Г. Сивых, А. В. Хмелёв, А. В. Яковлев, “Методы локального поиска для одной задачи о перестановке столбцов бинарной матрицы”, Вестн. НГУ. Сер. матем., мех., информ., 12:1 (2012), 91–101
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vngu110 https://www.mathnet.ru/rus/vngu/v12/i1/p91
|
Статистика просмотров: |
Страница аннотации: | 271 | PDF полного текста: | 105 | Список литературы: | 55 | Первая страница: | 3 |
|