АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ
Аннотация
Рассматривается многомерная задача о назначениях, полученная из классической задачи о назначениях при дополнительных предположениях, что одного претендента можно назначить на несколько должностей и любое подмножество должностей может оказаться занятым претендентами, несовместимыми между собой на этих должностях. Показывается, что NP-трудная многомерная задача о назначениях сводится к задаче поиска в n-дольном взвешенном гиперграфе максимального полного подгиперграфа, имеющего минимальную сумму весов вершин и ребер. Предлагаются жадные алгоритмы решения задачи и алгоритмы локального поиска в окрестности начального решения.
Список литературы
1. Карпук, А.А. Задача оптимизации использования радиочастотного ресурса при присвоении частот радиолиниям / А.А. Карпук // Информатика. – 2006. – № 4 (12). – С. 5–13.
2. Сергеев, С.И. Квадратичная задача назначения / С.И. Сергеев // Автоматика и телемеханика. – 1999. – № 8. – С. 127–147.
3. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.
4. Ахо, А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман. – М.: Издательский дом «Вильямс», 2000. – 384 с.
5. Кочетов, Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации / Ю.А. Кочетов // Дискретная математика и ее приложения: сб. лекций молодежных и научных школ по дискретной математике и ее приложениям. – М.: МГУ, 2001. – С. 87–117.
6. Special software for electromagnetic compatibility simulation and frequency assignment to radio sets of fixed-mobile radio communication systems / V. Voloshin [et al.] // Proc. 4th European Symposium on electromagnetic compatibility. – Brugge, 2000. – Vol. 2. – P. 119–122.
7. Карпук, А.А. Задача о назначениях с учетом коллизий / А.А. Карпук // Информационный бюллетень Ассоциации математического программирования: тез. докл. конф. «Математическое программирование и приложения». – Екатеринбург: УрО РАН, 2007. – № 11. – С. 178.
Рецензия
Для цитирования:
Карпук А.А. АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ. Информатика. 2008;(2(18)):5-13.
Просмотров: 584
Послать статью по эл. почте 