Back Tracking 백트래킹 알고리즘

백트래킹 알고리즘

---

여러 다양한 방법을 순서대로 탑색하면서

조건을 만족시키는 솔루션을 찾을 때 까지 되돌아가서 찾는 방법이다

마치 미로를 탐색하는 것을 생각하면 되고

탐색하다가 Promising 하지 않은 길이면 (미로같은 경우 dead end) back track해서 마지막 갈림길로 돌아가 다른 길로 탐색하는 알고리즘이다

탐색 Tree를 전체 탐색하지 않는 버젼의 DFS라고 할 수도 있다

 

이 알고리즘을 활용한 문제들이 여러개 있는데

728x90

 

N-Queens 문제

---

N-Queens 문제는 N x N 체스보드에 N개의 퀸을 서로 위협하지 않도록 배치하는 방법을 찾는 문제이다. 각 퀸은 자신의 행, 열, 대각선 상에 있는 다른 퀸을 위협하지 않는 배치를 찾는 문제이다

 

백트래킹을 사용하여 N-Queens 문제를 해결할 때, 상태 공간 트리를 구성한다다. State Space Tree

트리의 각 레벨은 퀸의 행(row)을 나타내며, 노드는 퀸의 열(column) 위치를 나타낸다.

유망한 (Promising) 노드는 퀸이 서로 위협하지 않는 위치에 있는 노드이다.

반응형

Pruning은 다음과 같은 경우에 이루어진다:

• 같은 열에 퀸이 이미 배치된 경우
• 같은 대각선 상에 퀸이 배치된 경우
• |col(i)-col(k)|=|i-k| ->같으면 대각선에 있는 

가지치기(pruning)를 통해 불필요한 탐색을 줄임으로써 효율성을 높일 수 있다

확인해보면

만약 Pruning없이 그냥 brute force 로 탐색을 했다면

개의 노드를 확인해야하는 반면

 

Promising한 노드들만 탐색하는 경우에 Upper Bound를 찾아보면

더 줄어든 것을 확인 할 수 있다

하지만 이 것도 이상적인 탐색 횟수는 아니다 (대각선 비고려) 등등

 

그래프 색칠 문제 (Graph Coloring Problem)

---

그래프 색칠 문제는 주어진 그래프의 각 정점을 색칠할 때, 인접한 정점이 같은 색상을 가지지 않도록 최소한의 색상을 사용하는 방법을 찾는 문제이다

그럼 m-색칠 문제(m-Coloring Problem)는

최대 m개의 색상을 사용하여 그래프를 색칠하는 모든 방법을 찾는 문제이다.

 

사실 Map Coloring problem으로 더 유명한데

위와같은 graph로 그리려면 모든 Map지도는 Planar Graph로 그릴 수있다

 

Planar Graph:

모든 edge들이 서로 엇갈리지 않는 Graph를 뜻한다

 

백트래킹을 사용하여 그래프 색칠 문제를 해결할 때, State Space Tree 를 구성하고

트리의 각 레벨은 정점을 나타내며, 노드는 해당 정점에 할당된 색상을 나타낸다.

 

유망한 노드는 인접한 정점이 같은 색상을 가지지 않는 노드이며

가지치기는 인접한 정점이 같은 색상을 가지는 경우에 이루어진다.

 

Worst Case:

해밀턴 회로 문제 (Hamiltonian Circuits Problem)

---

해밀턴 회로 문제는 그래프에서 모든 정점을 정확히 한 번씩 방문하고 시작 정점으로 돌아오는 경로를 찾는 문제다.

백트래킹을 사용하여 해밀턴 회로 문제를 해결할 때, State Space Tree 를 구성하며.

트리의 각 레벨은 경로상의 정점을 나타내며, 노드는 해당 정점을 방문하는 순서를 나타낸다.

Promising한 노드는 다음 조건을 만족하는 노드들이다:

• i번째 정점은 (i-1)번째 정점과 인접해야 한다.
• (n-1)번째 정점은 시작[마지막] 정점(0번째 정점)과 인접해야한다.
• i번째 정점은 이전에 방문한 정점이 아니어야 한다.

pruning은 위의 조건을 만족하지 않는 경우에 이루어진다

 

Worst Case:

0-1 배낭 문제 (0-1 Knapsack Problem)

---

0-1 배낭 문제는 배낭의 용량을 초과하지 않으면서 가치의 합을 최대화하는 물품의 조합을 찾는 문제이다.

각 물품은 포함되거나 포함되지 않는 두 가지 경우만 있기에 Binary 

백트래킹을 사용하여 0-1 배낭 문제를 해결할 때, State Space Tree 를 구성합니다.

트리의 각 레벨은 물품을 나타내며, 노드는 해당 물품을 포함할지 여부를 나타냅니다.

 

maxprofit: 지금까지 최고 profit

bound: 이 가방 안에 잠재적으로 담을 수 있는 profit

만약 이 값이 max profit 보다 작으면 굳이 이 노드를 탐색 할 필요가 없다

 

Promising한 노드는 다음 조건을 만족하는 노드입니다:

• 배낭의 현재 용량과 남은 물품의 무게를 고려했을 때, 최대 가치(bound)가 현재까지의 최대 가치(maxprofit)보다 크거나 같아야 합니다.
• 배낭의 용량을 초과하지 않아야 합니다.

가지치기는 위의 조건을 만족하지 않는 경우에 이루어집니다.

 

ex)

Suppose that n = 4, W=16, and we have the following

i pi wi pi/wi

1 $40 2 $20

2 $30 5 $6

3 $50 10 $5

4 $10 5 $2

so at the first node the bound would be

and the maxprofit is 0, so it’s still promising

at the second node

and the maxprofit updates to 40

 

 

백트래킹은 문제의 특성에 맞는 상태 공간 트리를 구성하고, 유망한 노드를 판별하는 기준을 세우는 것이 중요하다.

효과적인 가지치기를 통해 불필요한 탐색을 줄임으로써 알고리즘의 효율성을 높일 수 있다.

 

백트래킹은 다양한 최적화 문제와 의사 결정 문제를 해결하는데 유용하게 활용된다

 

<Merge Sort, 합병 정렬>

https://tonnykang.tistory.com/184

Merge Sort 합병 정렬