Методика оптимізації пошуку шляху в графі за рахунок відкидання зайвих вузлів
DOI:
https://doi.org/10.18372/2310-5461.37.12364Ключові слова:
пошук шляху, оптимізація, транзитивне замикання, кластерний аналіз, оптимальний шлях в графіАнотація
У статі запропоновано методику оптимізації пошуку оптимального шляху в графі за рахунок відкидання зайвих вузлів на основі кластерного аналізу з використанням транзитивного замикання матриці відношення. Проаналізовано існуючі методи оптимізації пошуку шляху, в результаті чого запропоновано методику, що реалізує ідею зменшення кількості вузлів в поточному обрахунку, як результат відбувається зменшення кількості задіяних ресурсів. Розглянуто застосування методики на практиці, та зроблено висновки щодо подальших досліджень в цьому напрямку. Для перевірки працездатності та оцінки ефективності методики розроблено програмне забезпечення на мові програмування високо рівня С++. Отримані результати свідчать про досить високу ефективність оптимізації для статичних вузлів, які не змінюють своїх властивостей певний період часу.
Посилання
Юдін О. К. Аналіз загроз державним інформаційним ресурсам / О. К. Юдін, С. С. Бучик // Проблеми інформатизації та управління. – 2013. – №4 (44). – С. 93 – 99.
Land A. H. An Automatic Method of Solving Discrete Programming Problems / A. H. Land, A. G. Doig – [Електронний ресурс]. – Режим доступу: http://jmvidal.cse.sc.edu/library/land60a.pdf.
Newell A. Computer Science as Empirical Inquiry: Symbols and Search. / A. Newell, H. A. Simon // – [Електронний ресурс]. – Режим доступу: http://delivery.acm.org/10.1145/370000/360022/a1975-newell_simon.pdf.
Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. – [Електронний ресурс]. – Режим доступу: http://mat.uab.cat/~alseda/MasterOpt/Judea_Pearl-Heuristics_Intelligent_Search_Strategies_for_Computer_Problem_Solving.pdf
Данчук В. Д. Оптимізації пошуку шляхів по графу в динамічній задачі комівояжера методом модифікованого мурашиного алгоритму / В. Д. Данчук, В.В. Сватко // Системні дослідження та інформаційні технології – 2012. – № 2. – С. 78 – 86. – [Електронний ресурс]. – Режим доступу: http://journal.iasa.kpi.ua/article/viewFile/71975/66948.
Обзор алгоритмов кластеризации данных. – [Електронний ресурс]. – Режим доступу: https://habrahabr.ru/post/101338/.
Кофман А. Введение в теорию нечетких множеств / А. Кофман – М.: «Радио и связь», 1982. – 432 с.
Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. / Ф. А. Новиков – СПб.: Питер, 2009. – 384 c.
Алгоритм Дейкстры. – [Електронний ресурс]. – Режим доступу: https://ru.wikipedia.org/wiki/Алгоритм_Дейкстры
Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе. – [Електронний ресурс]. – Режим доступу: https://habrahabr.ru/post/111361/.
