Реалізація паралельного алгоритму пошуку Depth-First Search

Abstract

Розроблено оптимізований паралельний алгоритм пошуку в глибину Depth-First Search для графів. Проведено детальний аналіз існуючих методів пошуку в глибину, обґрунтовано вибір засобів для реалізації паралельного виконання та моделювання часових затримок між вузлами графу. Визначено переваги та недоліки класичних підходів та запропоновано методи їхньої оптимізації. Запропоновано використання бібліотеки ThreadPoolExecutor у Python для реалізації багатопотокового обчислення. Особлива увага приділена ефективності використання потоків, балансуванню навантаження та мінімізації синхронізаційних витрат. Створено програмну реалізацію паралельного Depth-First Search, що дозволяє значно скоротити час виконання алгоритму, особливо на великих графах. Проведене тестування підтвердило зменшення часу виконання на 1.5-2 рази в порівнянні з послідовною версією, що підтверджує ефективність багатопотокового підходу. Отримані результати можуть бути використані в задачах реального часу, аналізі соціальних мереж, оптимізації маршрутів, а також у розподілених системах обчислень.

An optimized parallel Depth-First Search algorithm for graphs has been developed. A detailed analysis of existing DFS methods was conducted, and the choice of tools for parallel execution and modeling of time delays between graph nodes was justified. The advantages and disadvantages of classical approaches were identified, and methods for their optimization were proposed. The use of the ThreadPoolExecutor library in Python was suggested for implementing multithreaded computation. Special attention was given to thread efficiency, load balancing, and minimizing synchronization overhead. A software implementation of the parallel Depth-First Search algorithm was created, significantly reducing execution time, especially for large graphs. Testing confirmed a reduction in execution time by 1.5-2 times compared to the sequential version, demonstrating the effectiveness of the multithreading approach. The obtained results can be applied to real-time tasks, social network analysis, route optimization, and distributed computing systems.