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

Автор(и)

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

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/.

##submission.downloads##

Як цитувати

Бучик, С., Пулеко, І. В., & Половніков, І. В. (2018). Методика оптимізації пошуку шляху в графі за рахунок відкидання зайвих вузлів. Наукоємні технології, 37(1), 11–17. https://doi.org/10.18372/2310-5461.37.12364

Номер

Том 37 № 1 (2018)

Розділ

Інформаційно-комунікаційні системи та мережі

Ліцензія

Науковий журнал дотримується принципів відкритого доступу (Open Access) та забезпечує вільний, негайний і постійний доступ до всіх опублікованих матеріалів без фінансових, технічних або юридичних обмежень для читачів.

Усі статті публікуються у відкритому доступі відповідно до ліцензії Creative Commons Attribution 4.0 International (CC BY 4.0).

Авторські права

Автори, які публікують свої роботи в журналі:

  • зберігають за собою авторські права на свої публікації;

  • надають журналу право на перше опублікування статті;

  • погоджуються на поширення матеріалів за ліцензією CC BY 4.0;

  • мають право повторно використовувати, архівувати та поширювати свої роботи (у тому числі в інституційних та тематичних репозитаріях) за умови посилання на первинну публікацію в журналі.