(AI) 문제해결 위한 탐색

💼📝🔑⏰ 📙📓📘📒🎓

💼 그래프 탐색

그래프에서 경로의 탐색

• 초기상태에서 시작하여 목표상태에 도달할 수 있는 일련의 연산자를 찾는 것
• 시행착오를 거치면서 목표상태에 도달하는 탐색 과정
• 탐색에 유용한 지식을 사용함으로써 방대한 상태공간에서 탐색 범위를 좁히려고 함

📝 탐색과정

• 노드의 확장: 주어진 노드(상태)에 적용할 수 있는 모든 연산자를 가하여 모든 후계노드(후계상태)를 생성
• 목표노드가 있는지 검사함
• 후계노드에 부모노드를 가리키는 포인터를 첨부(탐색 경로를 알 수 있게 함)
• 정해진 기준에 따라 다음 노드를 선택하여 탐색 과정 반복
• OPEN: 앞으로 확장할 노드를 저장하는 리스트
• CLOSED: 이미 확장한 노드를 저장하는 리스트

💼 탐색의 종류

📝 맹목적 탐색

• 목표노드의 위치와 무관한 순서로 노드 확장
• 매우 소모적인 탐색을 할 가능성이 높음
• 임의 경로 탐색: 깊이우선 탐색, 너비우선 탐색
• 최적경로 탐색: 균일비용 탐색

📝 경험적 탐색

• 문제영역에서 사용할 수 있는 목표노드의 위치와 관련된 경험적 정보를 사용
• 경험적 정보 :항상 옳은 것은 아니지만, 개연성이 있어 많은 경우 잘 맞는 정보
• 임의 경로 탐색: 언덕오르기 탐색, 최적우선 탐색, 모의 담금질
• 최적경로 탐색: A* 알고리즘

💼 무정보 탐색

📝 깊이우선 방법

탐색 진행방향(깊이 방향)으로 계속 전진하여 목표를 탐색하는 방법

• 가장 최근에 생성된 노드를 가장 먼저 확장함
• OPEN은 스택 구조

문제점

• 목표에 도달할 수 없는 경로를 계속 탐색하게 될 수 있음
• 깊이제한(depthbound)을 정하여 무한정 진행하지 않도록 제한함

📝 너비우선 방법

트리의 레벨 순서에 따라 노드를 확장함

• 생성된 순서에 따라 노드를 확장함(먼저 생성된 노드)
• OPEN은 큐 구조
• 만일 해가 존재한다면 출발노드에서 목표노드까지 도달하는 최단길이 경로를 찾는 것을 보장함

📝 균일비용 방법

🔑 노드 사이의 경로비용

한 상태에서 다른 상태로 이동하기 위한 필요한 ‘비용’

• 예) 8퍼즐 문제 :조각의 이동을 최소화하면서 원하는 배열을 얻고자 함
  • 빈 칸을 한 칸 이동하는데 1이라는 비용을 고려해야 함
  • 비용이 항상 동일함
• 예) 지도상의 최단 경로 검색 문제
  • 한 지점에서 다른 지점으로 이동할 때의 거리를 비용으로 고려해야 함
  • 비용이 항상 다르다.
• 출발노드 S노드로부터 노드 n까지의 경로비용
  • OPEN의 노드들 중 출발노드로부터의 경로비용이 최소인 노드들을 선택하여 확장
  • 최소비용 경로를 탐색할 수 있음