[공학]백트래킹의 개념과 해밀턴 회로 문제 알고리즘 분석과 코딩까지

소개

백트래킹의 개념 및 해밀턴 회로 문제의 개념부터 알고리즘 분석과 코딩까지 직접 했습니다.
책에 잘못된 점까지 지적했다고 교수님께 칭찬을 들은 레포트입니다.^^

목차

6.1 개념소개
- 백트래킹이란
- 탐색공간트리

6.2 해밀턴 회로 문제
- 해밀턴 경로란
- 해밀턴 경로예제
- 알고리즘 분석
- 소스 및 분석

본문내용

.6.1 개념소개

"백트래킹(backtracking)" 이란?

- 미로 찾기 문제 (출구를 찾을 때까지 반복)
1. 분기점이 나올 때까지 길을 따라 간다.
2. 분기점을 만나면 그 중 어느 한 길을 선택하여 진행한다.
3. 길을 따라 가다가 막혀 있으면 분기점까지 되돌아 온다.
4. 되돌아 온 길로는 다시 가지 않도록 표시한다.
5. 다른 길을 시도해 본다.

-> 어떤 일을 한 이후에 그 일을 되 물리는 것




* 탐색공간트리
어떠한 문제에 대해 모든 경우가 다 나와 있는 트리를 탐색 공간 트리라고 한다.

ex) 서울에서 출발하여
대전, 대구, 부산을 모두 구경하고
다시 서울로 돌아오는 경로를 구한다면,

백트랙킹의 또 다른 예
- 백트래킹이란,
상태 공간 트리에서 해답 노드를 찾는 탐색을 할 때,
상태 공간 트리의 각 노드가 유망한 노드인지 아닌지를
판단하면서 깊이 우선 탐색(DFS)
-> 전위순회(root->왼쪽->오른쪽)를 하는 탐색방법이다.



void 깊이 우선 탐색 (node r)
{
node u;
visit r;

for (each child u of r)
깊이 우선 탐색 (u);
}

그렇지만, DFS방식으로 상태공간트리의 모든 노드를 다 방문한다면 효율적인 탐색이라고 말할 수 없다. 탐색을 효율적으로 수행하기 위해서는 트리에 탐색이 불필요한 부분을 찾아내어 탐색 대상에서 제외시키는 것이 필요하다.
즉, 탐색 공간 트리의 탐색 중에 방문하는 각 노드에서 어떤 특정한 검사를 하여 그 노드의 상태가 해가 될 가능성이 있는가를 결정한다. 해가 될 가능성이 없다고 판단되면 이 노드의 후손은 탐색대상에서 제외시킨다.



void check_node(node v)
{
node u
if (유망한가(v))
if (there is a solution at v)
출력하시오;
else
for (each child u of v)
check_node(u);
}
: 노드가 유망한지 아닌지 검사하고 유망할 때 그 노드가 해답이면 출력하고,
아니면 자식 노드가 있는 동안 체크노드함수를 불러 탐색한다.

참고자료

· 없음