===================1122
3.
Backtracking알고리즘
: 해답이 될 가능성이 있는지를 확인하고,
유망하지 않다면 더 이상 깊게 들어가지 않고 부모 노드로 돌아오는 방식을 취한다.
=> 해답이 될 가능성이 없으면 배제하고, 부모노드로 되돌아가면서 풀이시간을 단축한다.
효과-> 엄청 효율적이다.
The backtrack algorithm has the ability to yield the
same answer with for fewer than m trials.
5.
백트래킹 기법
? 백트래킹 (Backtracking) 기법은 해를 찾는 도중에 ‘막히면’
(즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다
? 백트래킹 기법은 최적화 (optimization) 문제와 결정 (decision)
문제를 해결할 수 있다.
? 결정 문제: 문제의 조건을 만족하는 해가 존재하는지의
여부를 ‘yes’ 또는 ‘no’가 답하는 문제
6.
Backtrack 알고리즘의 기본형태
Assume : 1. Solution is expressed as X(1..n)
2. X(k)∈ S={a1,a2,… am}, where S is a finite set
3. Initially, X(k)= a0 for all k, where a0 ∈ S
Procedure BACKTRACK(n)
k := 1 ;
for i=1 to n do
X(i) := a0 ;
while 1 ≤ k ≤ n do
GETNEXT(k);
if X(k) = a0
then k := k-1 ; (이 부분이 backtrack)
else if k = n ;
then OUTPUT(X) ;
else k := k+1;
Procedure GETNEXT(k)
Let a i be the current value of X(k)
while i < m do
X(k) := a i+1 ;
i := i + 1;
if BOUND(k) = true
then return ;
if i = m then X(k) := a 0 ;
7.
[https://idea-sketch.tistory.com/29]
제일 대표 n-Queens 문제
조건: 같은 행/열/대각선상에 위치하면 안됨. (체스 게임상)
bounding function이 잘 되면 빨리 넘어감
8.
4-Queens 문제를 무작정 알고리즘으로 풀기
-> 각 queen을 각각 다른 행에 할당 후,
어떤 열에 위치하면 해답을 얻을 수 있는지 차례대로 모두 점검.
-> 각 queen은 4개의 열 중에 위치할 수 있기 때문에 무작정 알고리즘으로 풀면, 점검해 보아야 하는 경우의 수는
4 * 4 * 4 * 4 = 256가지.
10.
복습) Depth-First Search (DFS) 깊이우선탐색
: root가 되는 노드를 먼저 방문한 뒤, 그 노드의 모든 descendant(후손)들을 차례로 (보통 왼쪽에서 오른쪽으로) 방문한다.
DFS 기본 형태:
void DFS(node v) {
node u;
visit[v] := 1;
for (each node u which is adjacent to v)
DFS(u)
}
13.
DFS로 형성되는 state(각 노드) space tree에서,
root노드에서 leaf노드까지의 경로는 해답후보가 되는데, dfs해서 그 해답후보 중에서 해답을 찾는 과정임.
하지만,
(DFS의 한계점) 해답이 될 가능성이 전혀 없는 노드&그 노드의 후손노드들도 모두 검색해야하므로 비효율적임.
14.
4-Queens 문제를 Back Track 기술을 사용하여 풀기
용어
'유망'하다=해답이 나올 가능성이 있는 노드를 일컫는 말
'유망'하지 않다=전혀 해답이 나올 가능성이 없는 노드를 일컫는 말
[BackTrack=어떤 노드의 유망성을 점검 후, 유망하지 않다고 판단이 되면 그 유망성 없다고 판단된 노드의 부모노드로 '돌아가' 다음 후손노드에 대한 검색을 계속하게 되는 절차]
15.
backtracking의 절차
1. state space tree의 깊이우선검색을 실시
2. 각 노드가 promising한지 점검
3. non-promising하면, 그 노드의 부모노드로 돌아가서 검색을 계속
16-17. 해봄
트리의 노드를 가장 적게 생성하는 것이 우리 목표. 그래서 1.2에서 멈춤.
생성되는 노드가 적을수록 시간이 별로 안걸리는 것임.
=====================1127
18.
(x=행, y=열)
(x,y) 점에 대한 대각선에 위치한 것들의 특징은?
식으로 나타내면?
(row-column)값이 같으면 같은 대각선상에 있다.
ex) 1,2 / 2,3/ 3,4는 차이가 다 1로 대각선상에 있음.
마찬가지로 (row+column)값이 같으면 같은 대각선상에 있다. (반대 대각선 모양)
19. (pg. 18에 대한 설명을 식으로 표현함.)
만약) 두 queen의 위치가 각각 A(a, b), A(c, d)라 하면.
If, a-b = c-d or a+b = c+d, they are on the same diagonal.
즉, | b - d | = | a ? c |
만약
| i - j | = | X(i) ? X(j) | 라면, (=같은 대각선상이라면)
k번째 queen이 X(k)에 있을 수 없음
21.
Promising 노드의 개수를 정확하게 구하기 위한 유일한 방법은 실제로 알고리즘을 수행하여 구축된 state space tree의 노드의 개수를 세어보는 수 밖에 없다.
그러나, 이 방법은 진정한 분석 방법이 될 수 없다. 왜냐하면 분석은 알고리즘을 실제로 수행하지 않고 이루어져야 하기 때문이다.
22.
Monte Carlo 기법을 사용하여 수행시간을 추정할 수 있다.
23.
그래프 칼라링 문제
: m개의 색을 가지고 인접한 지역이 같은 색이 되지 않도록 지도에 색칠하는 문제
24.
해봄
25.
Monte Carlo 기법을 사용하여 수행시간을 추정할 수 있다.
26-31. 해 봄.
현재 나온 값 중에 제일 작은 것으로 계속 업데이트 하면 됨.
만약 해가 16인데 다음 꺼 하다가 중간에 17 나오면 굳이 17 안해봐도 됨. 왜냐면 어차피 해봤자 16이 제일 작은 값이니까.
->이렇게 하면 훨씬 가지가 점점 줄어들 것임
32.
최종해= [A,B,E,C,D,A]이고, 거리=16이다.
Comments