Multi-colored Graph에 대한 백트래킹의 효율적인 구현

Abstract

현재 컴퓨터 이론 분야에서 NP-hard에 속하는 그래프 문제에 대한 관심이 커지고 있고, 이러한 NP-hard 그래프 문제를 해결하는 대부분의 state-of-the-art 알고리즘은 백트래킹을 사용한다. 알고리즘 전체가 소모하는 시간 중에서 백트래킹 과정에 소모되는 시간의 비중이 상당히 높아지기도 하므로 효율적으로 백트래킹을 구현하는 것은 NP-hard 그래프 알고리즘의 성능에 있어서 매우 중요하다. 본 논문은 여러 개의 그래프에 반복되는 백트래킹을 더욱 효율적으로 만들 수 있는 multi-colored graph에 대한 백트래킹 방법을 제안한다. 또한 백트래킹의 대응 순서에 있어서 고정된 대응 순서가 아닌 상황에 따라 변화하는 대응 순서를 정할 수 있는 두 가지 방안인 후보 집합에 의한 대응 순서와 유효색에 의한 대응 순서를 제시하였다. 또한 multi-colored graph에 대한 백트래킹은 각각의 단색 그래프가 많이 겹쳐있을수록 더욱 효율적으로 동작하게 되고, multi-colored graph에 대한 백트래킹의 효율의 지표로 사용할 수 있는 유사도를 제안하였다. 실험을 위해 유사도가 높은 단색 그래프로 multi-colored graph를 구성했으며, multi-colored graph에 대한 백트래킹과 각각의 단색 그래프에 대한 백트래킹을 백트래킹 수행 시간 및 재귀 호출 횟수로 비교하였다. 이때 multi-colored graph에 대한 백트래킹은 각각의 단색 그래프에 대한 백트래킹의 합보다 백트래킹 수행 시간이 최대 10배, 재귀 호출 횟수가 최대 250배 개선되었다.

The majority of the state-or-the-art algorithms for NP-hard graph problems are based on the framework of backtracking. An efficient implementation of the backtracking is important to performance of the algorithms for NP-hard graph problems. In this work, we proposed backtracking in multi-colored graphs, which can make repetitive backtracking in many graphs more efficient. We also suggested two strategies of adaptive matching order called candidate-size matching order and color-size matching order. Backtracking is more efficient when each single-colored graphs in a multi-colored graph are similar, and we presented a notion of similarity that can be used as an indicator of efficiency. For the experiments, we constructed multi-colored graphs with similar single-colored graphs, and we measured the running time of backtracking algorithm and the number of recursion calls. The experiments showed that backtracking in a multi-colored graph is faster than each backtracking in single-colored graphs by up to 10, while the number of recursion calls is decreased by up to 250.