Preview

Информатика

Расширенный поиск

АЛГОРИТМЫ РЕШЕНИЯ МНОГОМЕРНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ

Полный текст:

Аннотация

Рассматривается многомерная задача о назначениях, полученная из классической задачи о назначениях при дополнительных предположениях, что одного претендента можно назначить на несколько должностей и любое подмножество должностей может оказаться занятым претендентами, несовместимыми между собой на этих должностях. Показывается, что 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.

For citation:


. . Informatics. 2008;(2(18)):5-13. (In Russ.)

Просмотров: 33


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)