Method of optimizing the search for a path in a graph by rejecting unnecessary nodes
DOI:
https://doi.org/10.18372/2310-5461.37.12364Keywords:
search for a path, optimization, transitive closure, cluster analysis, the best path in the graphAbstract
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.References
Юдін О. К. Аналіз загроз державним інформаційним ресурсам / О. К. Юдін, С. С. Бучик // Проблеми інформатизації та управління. – 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/.
