Рассмотрим 0-1 матрицу, каждой строке которой приписан неотрицательный вес. Вычислим для каждой строки число столбцов, находящихся между первой и последней единицей в этой строке. Взвешенная сумма этих величин по всем строкам является целевой функцией задачи. Эта величина зависит от перестановки столбцов. В задаче требуется найти такую перестановку, при которой значение целевой функции минимально. Известно, что эта задача является NP-трудной. Для ее решения в работе предлагается алгоритм поиска с запретами. В алгоритме используются несколько случайных окрестностей квадратичной мощности для локального улучшения. Применяются различные виды списков запретов. Для повышения эффективности поиска в алгоритм включены процедуры диверсификации и интенсификации. Приводятся результаты численных экспериментов на тестовых примерах с известным оптимальным решением. Проводится сравнение с другими эвристическими алгоритмами.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарии Обратная связь |
[Головная страница] [Конференции] |
© 2009, Институт Вычислительной Математики и Математической Геофизики СО РАН, Новосибирск
© 1996-2009, Сибирское отделение Российской академии наук, Новосибирск
Дата последней модификации: 06-Jul-2012 (11:52:52)