Д.М. Силин – руководитель группы, ООО «Гейзер-Телеком»

E-mail: dsln@mail.ru

По результатам анализа публикаций на тему задачи назначения частот выявлено, что задача назначения частот с условиями взаимных влияний общего вида исследуется только для специального вида условий возникновения взаимных влияний. Рассмотрена задача назначения частот радиоэлектронным средствам при условии, что взаимные влияния могут возникать при назначении любых заданных комбинаций частот. Показана NP-полнота задачи назначения частот с такими условиями взаимных влияний. Предложен эвристический алгоритм назначения частот за полиномиальное время, присваивающий частоты в первую очередь средствам с высоким приоритетом.

1. Audrey D., Andréa L., Christian A., Dominique F., Philippe M., Michel V. The Dynamic Frequency Assignment Problem // European Journal Of Operational Research. Elsevier. 2008. URL: https://hal-univ-tlse3.archives-ouvertes.fr/hal-00119537/document. 
2. Соловьев В.В. Методы оптимального присвоения частот. М.: Изд-во «НПФ «Гейзер». 2000.
3. Koster A.M.C.A. Frequency Assignment. Models and Algorithms // Proefschrift Universiteit Maastricht. 1999. URL: https://www.math2.rwth-aachen.de/files/mitarbeiter/koster/Koster1999.pdf.
4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир. 1979.
5. Харари Ф. Теория графов, М.: Мир. 1972.
6. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы. Построение и анализ. М.: Вильямс. 2005.
7. Кристофидес Н. Теория графов (алгоритмический подход). М.: Мир. 1978.
8. Корбут А.А., Филькенштейн Ю.Ю. Дискретное программирование. М.: Наука. 1969.
9. Gerardo M., Cristian P., Lucas R., Sergio N. A Parallel Evolutionary Algorithm applied to the Minimum Interference Frequency Assignment Problem // Workshop on Agents and Intelligent Systems. 2006. URL: https://www.fing.edu.uy/~sergion/ PEA_MIFAP.pdf.
10. Karen I. Aardal, Stan P.M. Van Hoesel, Arie M.C.A. Koster, Carlo Mannino, Antonio S. Models and Solution Techniques for Fre-quency Assignment Problems // Konrad-Zuse-Zentrum für Informationstechnik Berlin. 2001.URL:http://home.deib.polimi.it/capone/radiomobili/materiale/frequency-assignment2.pdf.