.gif&blockId=11b00c82-b138-8050-a58b-dcbceda2ef8f)
백트래킹
•
퇴각 검색
•
한정 조건을 가진 문제를 풀려는 전략
•
한정 조건
◦
백트래킹 알고리즘에서 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없다고 판단되면 그 노드의 부모 노드로 되돌아가는 것
•
보통 BFS나 DFS와 함께 구현
◦
BFS보다는 DFS의 구현이 더 편함
•
최적화 문제, 결정 문제에서 많이 사용
◦
미로 찾기 / n-Queen / Map coloring / 부분 집합의 합 등
한정 조건
•
3 X 3 행렬 선택 게임
◦
선택한 숫자들의 행과 열은 모두 중복하면 안된다.
◦
가장 적은 점수를 얻는 것이 승리하는 것이라 할때 선택해야하는 숫자 3개를 골라보자.
◦
한정 조건이 없을 때
◦
한정 조건이 있을 때
코드 형태
def 백트래킹(n):
if 정답이면 :
출력 or 저장
else :
for 모든 자식 노드에 대해 :
if 유망한지확인(m) :
자식노드로 이동
백트래킹(n+1)
부모노드로 이동
def 유망한지확인(m):
if 조건에 안맞으면 :
return False
return True
Python
복사
백트래킹과 DFS의 차이
•
백트레킹
◦
어떤 노드에서 출발하는 경로가 그 해결책으로 이어질 것 같지 않으면 더 이상 경로를 탐색하지 않음으로써 시도 횟수 감소
◦
불필요한 경로의 조기 차단
◦
N! 가지의 경우의 수를 가진 문제에 대해 백트레킹에 가하면 일반적으로 경우의 수가 줄어들지만 최악의 경우는 처리 불가능
◦
모든 후보를 검사하지 않음
•
DFS
◦
모든 경로를 추적
◦
N! 가지의 경우의 수를 가진 문제에 대해 깊이 우선 탐색을 이용하면 처리 불가능
◦
모든 후보를 검사
