Методика оптимізації пошуку шляху в графі за рахунок відкидання зайвих вузлів

С.С. Бучик, І. В. Пулеко, І. В. Половніков

Анотація


У статі запропоновано методику оптимізації пошуку оптимального шляху в графі за рахунок відкидання зайвих вузлів на основі кластерного аналізу з використанням транзитивного замикання матриці відношення. Проаналізовано існуючі методи оптимізації пошуку шляху, в результаті чого запропоновано методику, що реалізує ідею зменшення кількості вузлів в поточному обрахунку, як результат відбувається зменшення кількості задіяних ресурсів. Розглянуто застосування методики на практиці, та зроблено висновки щодо подальших досліджень в цьому напрямку. Для перевірки працездатності та оцінки ефективності методики розроблено програмне забезпечення на мові програмування високо рівня С++. Отримані результати свідчать про досить високу ефективність оптимізації для статичних вузлів, які не змінюють своїх властивостей певний період часу.


Ключові слова


пошук шляху; оптимізація; транзитивне замикання; кластерний аналіз; оптимальний шлях в графі

Посилання


Юдін О. К. Аналіз загроз державним інформаційним ресурсам / О. К. Юдін, С. С. Бучик // Проблеми інформатизації та управління. – 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/.


Повний текст: PDF

Посилання

  • Поки немає зовнішніх посилань.


E-ISSN 2310-5461, ISSN 2075-0781

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

Ulrich's Periodicals DirectoryIndex CopernicusDOAJSSMРИНЦWorldCatCASBASEDRIVERНаціональна бібліотека ім. ВернадськогоНауково-технічна бібліотека НАУ