728x90
- Back Tracking(되돌아가며 풀어보기)
백트래킹 알고리즘 : 해를 찾는 과정에서 해를 더 이상 얻지 못하면 바로 직전 상태로 되돌아가서 다른 것을 시도하며 해를 찾는다.
- 백트래킹 알고리즘은 최적화 문제와 결정 문제를 해결
- 결정 문제 : 문제에 대한 해의 존재 여부(즉, 해가 '있다' 또는 '없다')를 답하는 문제
- 백트래킹은 해 탐색 순서가 깊이 우선(Depth First)으로 수행
- 분기 한정(Branch-and-Bound) 알고리즘 - 한정 값(bound)을 이용하여 한정 값이 가장 좋은 것 부터 최선 우선(Best First)탐색하는 방식으로 탐색 범위를 상당히 줄여서 해를 찾는다.
- M-coloring 백트래킹 알고리즘
인접한 영역을 서로 다른 색으로 칠하는 지도 색칠
지도를 Graph를 활용하여 보면 n개의 영역 = n개의 정점 / 두 영역이 서로 인접하면 그래프에선 두 영역에 대응되는 두 정점들을 간선으로 잇는다.
- 정점 0을 하나의 색으로 칠함
- 모든 점들이 색칠될 때까지 다음 점이 이미 색칠된 점과 인접하면, 인접한 점의 색과 다른 색을 선택
단, 주어진 k(색의 수)에 대해 색칠 실패하면 k를 1증가 후, 처음부터 다시 알고리즘 수행
수행시간 : O(nkⁿ)
- 여왕 말 문제(n-Queens problem)
Q가 같은 열, 같은 행, 같은 대각선상에 서로 놓이지 않도록 n x n 장기판에 n개의 Q를 배치하는 문제 (단, n>3)
- Q를 (0, 0)부터 놓기 시작하여 다음 Q를 서로 위협하지 않도록 배치한다.
- 만일 배치할 수 없으면, 직전 Q의 위치를 다음 칸으로 이동하여 다시 시도한다. 다음 칸이 없는 경우에는 위층의 Q를 다음 칸으로 이동하여 시도한다.
def solve_n_queens(n):
def is_safe(board, row, col):
# 같은 열 확인
for i in range(row):
if board[i] == col:
return False
# 좌상향 대각선 확인
for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if board[i] == j:
return False
# 우상향 대각선 확인
for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
if board[i] == j:
return False
return True
def solve(row, board, solutions):
if row == n:
solutions.append(board[:]) # 현재 해를 저장
return
for col in range(n):
if is_safe(board, row, col):
board[row] = col
solve(row + 1, board, solutions)
board[row] = -1 # 백트래킹
solutions = []
board = [-1] * n # 각 행에 퀸의 열 위치를 저장
solve(0, board, solutions)
# 결과 출력
def print_board(solutions):
for sol in solutions:
for i in sol:
row = ["."] * n
row[i] = "Q"
print(" ".join(row))
print("\n")
print_board(solutions)
return len(solutions)
# 예제 실행
n = 8 # n-Queens 문제에서 n의 값
solution_count = solve_n_queens(n)
print(f"총 솔루션 개수: {solution_count}")수행시간 : O(nⁿ⁺¹)
- 합이 K 되는 숫자
동적 계획 알고리즘에서 이 알고리즘은 O(nK) 시간에 최적해를 찾았는데 K=2ⁿ 이라면, DP알고리즘도 n이 커질수록 해를 찾기 어렵다. 백트래킹 알고리즘을 이용하여 좀더 빠르게 해를 찾을 수 있다.
- 주어진 숫자들을 증가 순으로 정렬
- 순서대로 숫자를 선택하는 경우(o)와 포기하는 경우(x)로 나누어 상태 공간 트리의 노드를 만든다. 만일 노드를 만들 수 없거나 만들 필요가 없으면 부모 노드로 되돌아가서 다른 노드를 선택한다.
- 위에서 만든(선택한) 노드에서 해를 찾으면 알고리즘 종료, 해가 아니면 2를 수행한다.
가지치기(punning)
입력을 정렬하는 이유: 자식 노드를 만들 때 다음 숫자를 추가한 합이 K를 초과하면 그 이후의 숫자는 다음 숫자보다 크므로 만들어진 노드로부터 아래로 더 이상 탐색해도 해가 없으므로
탐색 중단 : 가지치기(punning)
수행 시간 : O(2ⁿ)
728x90