|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
A Criterion of Optimality of Some Parallelization Scheme for Backtrack Search Problem in Binary Treesстатья
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 4 июня 2021 г.
- Авторы: Kolpakov Roman, Posypkin Mikhail
- Сборник: Communications in Computer and Information Science
- Том: 1145
- Год издания: 2020
- Издательство: Springer International Publishing AG
- Местоположение издательства: Cham, Switzerland
- Первая страница: 455
- Последняя страница: 464
- DOI: 10.1007/978-3-030-38603-0_33
- Аннотация: The backtracking is a basic combinatorial search algorithm. As many other deterministic methods it suffers from the high complexity. Fortunately the high performance computing can efficiently cope with this issue. It was observed that the structure of the search tree can dramatically affect the efficiency of a parallel search. We study the complexity of a frontal autonomous scheme for the backtrack search parallelization. In this approach several independent cores perform a number of first steps of the backtrack search. After that each core takes one sub-problem and solves it completely. Then the results are merged to select the best solution. To study the impact of the tree structure on the performance of the frontal autonomous scheme we formalize the notion of a perfectly scalable problem and prove a criterion for a search tree to fit to this class.
- Добавил в систему: Колпаков Роман Максимович