Method of optimizing the search for a path in a graph by rejecting unnecessary nodes
Наукові журнали НАУ
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Method of optimizing the search for a path in a graph by rejecting unnecessary nodes
Методика оптимизации поиска пути в графе за счет отбрасывания лишних узлов Методика оптимізації пошуку шляху в графі за рахунок відкидання зайвих вузлів |
|
| Creator |
Бучик, С.С.
Пулеко, І. В. Половніков, І. В. |
|
| Subject |
—
search for a path; optimization; transitive closure; cluster analysis; the best path in the graph — — поиск пути; оптимизация; транзитивное замыкание; кластерный анализ; оптимальный путь в графе — — пошук шляху; оптимізація; транзитивне замикання; кластерний аналіз; оптимальний шлях в графі 004.942(67) |
|
| Description |
The article proposes method optimizing the search of the optimal path in the graph by rejecting extra nodes based on cluster analysis using the transitive closure of the matrix of the relation. The existing methods of optimizing the search of the path have been analyzed, which resulted in the proposed method, which implements the idea of reducing the number of nodes in the current calculation, as a result of which there is a decrease in the number of resources. The application of the method in practice is considered, and conclusions are made regarding further research in this direction. To test performance and evaluate the effectiveness of the method the software was developed on the programming language of high-level C++. The results of the research indicate rather high efficiency of optimization for static nodes that do not change their properties for a certain period of time.
В статье предложена методика оптимизации поиска оптимального пути в графе за счет отбрасывания лишних узлов на основе кластерного анализа с использованием транзитивного замыкания матрицы отношения. Проанализированы существующие методы оптимизации поиска пути, в результате чего предложена методика, реализующая идею сокращения количества узлов в текущих расчетах, как результат происходит сокращение количества задействованных ресурсов. Рассмотрено применение методики на практике, и сделаны выводы о последующих исследованиях в этом направлении. Для проверки работоспособности и оценки эффективности методики разработано программное обеспечение на языке программирования высокого уровня С++. Полученные результаты свидетельствуют о достаточно высокой эффективности оптимизации для статических узлов, которые не меняют своих свойств длительный период времени. У статі запропоновано методику оптимізації пошуку оптимального шляху в графі за рахунок відкидання зайвих вузлів на основі кластерного аналізу з використанням транзитивного замикання матриці відношення. Проаналізовано існуючі методи оптимізації пошуку шляху, в результаті чого запропоновано методику, що реалізує ідею зменшення кількості вузлів в поточному обрахунку, як результат відбувається зменшення кількості задіяних ресурсів. Розглянуто застосування методики на практиці, та зроблено висновки щодо подальших досліджень в цьому напрямку. Для перевірки працездатності та оцінки ефективності методики розроблено програмне забезпечення на мові програмування високо рівня С++. Отримані результати свідчать про досить високу ефективність оптимізації для статичних вузлів, які не змінюють своїх властивостей певний період часу. |
|
| Publisher |
National Aviation University
|
|
| Contributor |
—
— — |
|
| Date |
2018-03-22
|
|
| Type |
—
— — |
|
| Format |
application/pdf
|
|
| Identifier |
http://jrnl.nau.edu.ua/index.php/SBT/article/view/12364
10.18372/2310-5461.37.12364 |
|
| Source |
Наукоємні технології; Том 37, № 1 (2018); 11-17
Science-based technologies; Том 37, № 1 (2018); 11-17 Наукоемкие технологии; Том 37, № 1 (2018); 11-17 |
|
| Language |
uk
|
|