[AI]Heuristiac 탐색

1. 휴리스틱 탐색

• 인공지능 탐색 알고리즘의 핵심 개념 중 하나
• 단순히 무작정 탐색하지 않고, 어느 방향으로 가면 목표에 더 가까울지 판단하는 기준을 사용하여 탐색 효율을 높이는 방법
• 모든 경로를 다 뒤지는 대신 경험적 판단 (Heuristic Function)을 통해 유망한 경로부터 먼저 탐색하는 것

2. Hill Climbing 알고리즘

• Hill Clibing : 현재 상태보다 더 좋은 (높은 평가값의) 상태로만 이동하는 탐색
• 핵심 아이디어
  • 현재 위치에서 이웃 노드(neighbor)를 모두 탐색
  • 가장 평가 함수 값이 좋은 노드로 이동
  • 더 이상 개선할 수 없으면 종료 (정상에 도달한 것으로 간주)
• 알고리즘 절차 설명
  • (1). 노드의 확장 (Expand the Node) : 현재 위치를 기준으로 각 방향의 높이 판단
  • (2). 목표 상태인가 검사 : 만일 모든 위치가 현 위치보다 낮다면 그 곳을 정상이라고 판단
  • (3). 후계 노드의 선택 : 현 위치가 정상이 아니라면 확인된 위치 중 가장 높은 곳으로 이동
• 단점 : 현재보다 나은 곳만 찾아서 이동하니깐 더 좋은 해를 놓칠 수도 있고, 중간 언덕에 멈춰버릴 수도 있다.

3. A* 알고리즘 (A-Star Search)

• A* 알고리즘은 가중치가 있는 그래프에서 최소 비용 경로를 찾는 탐색 기법
• 휴리스틱 함수 h(n)과 실제 비용
• $f(n)=g(n)+h(n)$
• f(n) : 전체 평가값, 작을수록 유망한 경로
• g(n) : 시작 노드에서 현재 노드까지의 실제 비용
• h(n) : 전체 평가값, 작을수록 유망한 경로로 판단
• 8puzzle 에서의 A*
  • h(n) : 제자리에 있지 않은 타일의 개수
  • g(n) : 이동 횟수
  • f(n) : 두 값을 합한 평가함수

4. TSP (Travelling Salesman Problem)

• 여러 도시와 도시 간 거리가 주어졌을 때, 한 도시에서 출발하여 모든 도시를 한 번씩 방문하고 출발지로 돌아오는 최단 경로를 찾는 문제
• 그래프 특성 : 가중치가 있는 그래프를 사용, 방향성이 없는 그래프임
• 최단 경로를 찾는 알고리즘 : Dijkstra 알고리즘