L17 - A* Algorithm

 

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한
 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다

 

 

 

 

TSP 문제 : 완전그래프에서 가장 짧은 해밀토니안 사이클 찾기

 

 

비대칭 TSP 문제 : 두 점 사이의 거리가 방향에 따라 다를 수 있는 TSP 문제

=> 방향그래프인데 가는 방향, 오는 방향의 weight가 다를 수 있는 TSP 문제

 

State-Space Tree

 

TSP 문제의 상태 공간 트리

 

상태 공간 트리 : 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리

 

Backtracking

 

백트랙킹 : 상태 공간 트리를 탐색하여 해를 찾는 알고리즘

 

• 해가 아닌 경우 되돌아간다는 의미에서 지어진 이름
  
  
• 깊이 우선 탐색 (DFS) 알고리즘을 응용
  
  
• 상태 공간 트리를 명시적으로 만들지는 않음

 

미로찾기 문제의 상태 공간 트리

 

Backtracking vs Brute-force

 

인접한 부분을 간선으로 연결하면 graph를 이룸

 

색칠 문제 : k개의 색상을 사용하여 인접한 정점은 같은 색상이 칠해지지 않도록 그래프를 칠할 수 있는가?

 

 

색칠 문제를 Brute-force 방식으로 푼다면?

 

색칠하는 모든 경우를 조사해야하므로 경우의 수가 k^n이 됨

 

 

Backtracking 방식으로 푼다면?

탐색 더 진행 X

 

상태 공간 트리를 탐색하는 중에, 답이 될 수 없는 경우는 빠르게 걸러내기 가능

 

Branch-and-Bound

 

한정 분기 : 최적의 해가 될 수 없는 경우 가지치기(Pruning) 하는 방법

 

=> 각 상태의 lower bound가 지금 찾은 해보다 더 좋아지지 않으면 가지치기

 

• 상태 공간 트리를 탐색할 때, 각 상태마다 하한을 계산 (추정치)
  
  
  • 각 상태의 서브트리는 하한보다 더 좋은 해를 가지지 않음
    
    
  • 하한 = g(x) + h(x)
    
    
    • g(x) : 지금까지의 경로 길이
      
      
    • h(x) : 남은 경로 길이의 추정치
  • 남은 경로 길이의 추정치 조건
    
    
    • 실제 경로보다 작거나 같아야함
      
      
    • 단조증가 해야함 h(x) <= w(x, y) + h(y)
      
      
    • 조건을 만족하지 않는 경우, 최적해를 구할 수 없음

 

Branch and Bound vs Backtracking

Backtracking 가지치기 : 제약조건을 만족하지 않는 경우

=> 색칠 문제에서 인접한 색이 같은 색으로 칠해지는 경우

한정 분기의 가지치기 : 최적해가 될 수 없는 경우

=> 지금까지 찾은 해보다 더 좋은 해를 찾을 수 없는 경우
(더 많은 경우 가지치기가 발생함!)

 

 

Branch and Bound for TSP

 

 

 

TSP 문제에서 하한 설정 : 사용한 간선의 가중치 + 각 정점의 가장 짧은 out-edge 길이의 합

 

 

 

=> cycle은 각 정점에서 나가는 간선이 있음을 바탕으로 시작할 때 각 정점에서 나가는 최소 간선들을 더한 33보다는 무조건 커야함

 

A* Algorithm

 

A* 알고리즘 : Branch and bound + Best-First-Search 
(다익스트라처럼 최선을 선택)

 

 

 

후보들 중 하한이 가장 낮은 것 부터 탐색함

 

=> 리프 노드를 하나라도 방문하는 순간 알고리즘 종료
(가장 처음 방문한 리프 노드가 최적해이므로)

 

시작점 - 도착점 최단 경로 계산

 

 

각 정점마다 도착 정점까지 추정 거리 존재

 

(하한 = 지나온 경로 거리 + 추정거리)

 

=> 하한이 가장 짧은 정점을 우선적으로 방문