Control Systems and Computers

https://doi.org/10.15407/csc.2022.01.024

Анісімов А.В. Задача локальної оптимізації графів та її застосування. Control Systems and Computers. 2022. №1. 
С. 24-31

УДК 517.7

А.В. АНІСІМОВ, доктор фіз.-мат. наук, професор, декан факультету комп’ютерних
наук та кібернетики, Київський національний університет імені Тараса Шевченка
03022, м. Київ, просп. Академіка Глушкова, 4Д, Україна,
a.v.anisimov@knu.ua

ПРО ЗАДАЧУ ЛОКАЛЬНОЇ ОПТИМІЗАЦІЇ ГРАФІВ
ТА ЇЇ ЗАСТОСУВАННЯ

Досліджується задача побудови локально-оптимального орієнтовного графа з навантаження ребрами, коли кожному ребру приписана фіксована числова вага. Локальна оптимальність або стабільний незмінний стан поточної розмітки графа дає загальний метод вирішення багатьох задач, пов’язаних з оптимізаційним пошуком в графах. Показано як із вирішення загальної задачі побудови локально-оптимального графа випливає задача знаходження шляхів найменшої ваги (вартості). Серед нових застосувань вказується вирішення проблеми асоціативного пошуку в комп’ютерній лінгвістиці (образне мислення) та швидкої взаємної автентифікації в коаліційних угрупуваннях.

Завантажити повний текст в PDF (українською).

Ключові слова: орієнтовний граф, шлях найменшої вартості, асоціативний пошук, випадковість, швидка автентифікація.

1. Deikstra Е. A note on two problems in connexion with graphs. Numer. Math. 1959. № рр. 269–271.
2. Moore E.F. The shortest path through a In Proc. an International Symposium on the Theory of Switching, Part II, Harvard University Press, 1959, pp. 285–292.
3. Pо11асk M. Solutions of the shortest-rout problems – a review. Oper. Res. 1960, N 8. рр. 224–
4. Pape U. Implementation and efficiency of Moore-algorithms for the shortest route problems. Progr, 1974, N 7. рр. 212–2.
5. Dео N., Pang С. Y., Lord R. Е. Two parallel algorithms for short est path problems. Proc. intern, conf. parallel proc. NewYork: ACM, 1980. рр. 244–53.
6. Иванов E. А., Шевченко В. П. О параллельных вычислениях на графах. Кибернетика. 1934, № 3. С. 89–94.
7. Анисимов А. В. Локальный алгоритм для задачи о кратчайшем пути из одного источника. Кибернетика. 1986. №3. С. 57–60
8. Ивахненко А. Г. Системы эвристической самоорганизации в технической кибернетике. «Техника», 1971. 371 с.
9. Анисимов А. В. Информатика. Творчество. Рекурсия. Киев: Наук. думка, 1988. 224 с.

Надійшла 06.06.2022