(AI) 문제해결 위한 탐색(2)

💼📝🔑⏰ 📙📓📘📒🎓

💼 경험적 탐색

• 목표상태를 보다 신속하게 탐색하기 위해 경험적 지식을 사용하는 탐색 방법
• 경험적 지식을 평가함수에 반영
  • 어떤 상태가 주어졌을 때 그 상태를 거쳐 가는 것이 목표상태로 가는데 얼마나 바람직한가를 나타내는 함수
  • 해를 향해 가는데 필요한 비용,해로 향하는 경로상에 존재할 가능성 등

📝 언덕오르기 방법

• 현재상태를 확장하여 생성된 후계노드들 중에서 다음 확장할노드를 선택함
• 깊이우선 탐색과 유사한 순서로 탐색, 깊이우선과 다른 점은 평가함수를 사용하여 계산한다는 점이다.
• 후계노드의 평가함수를 계산하여 가장 비용이 적은 노드를 다음 확장할 노드로 선택

문제점

• 언덕오르기 탐색과 같은 계수 최적화 방법에서는 후계상태들이 모두 낮은 평가함수를 갖음으로 인해 최대치에 도달한 것으로 오인하게 되는 지역최대치 문제
• 평가함수 값의 변화가 없어 더 이상 탐색을 진행하지 못하는 고원문제
• 연산자의 제한된 해상도로 인해 평가함수 값이 개선되는 후계상태를 찾지 못해 최대치에 도달한 것으로 오인하게 되는 능선문제 등이 발생할 수 있다.

평가함수

• 후계노드로부터 목표노드에 도달하는 비용을 예측한 값
• 후계노드까지 도달하는데 사용된 비용은 고려하지 않음

📝 최고우선 탐색 (Best-first search) (=최적우선탐색)

모든 말단 노드를 대상으로 평가함수 값을 비교하는 방법(선택 안된 노드도 추후 선택 가능)

• 가장 유망한 노드만을 확장하므로 탐색비용을 상당히 줄일 수 있다.

📝 A* 알고리즘

• A* 알고리즘에서는 출발노드로부터 노드n까지 도달하는 경로비용과
• 노드n으로부터 아직 탐색이 진행되지 않은 목표노드까지의 경로비용 예측치의 합을 평가함수로 사용한다.
• 평가함수: g(n)+h´(n)

💼 문제축소에 의한 해결방식

📝 문제축소

📝 AND/OR 그래프 및 탐색

📝 게임트리 및 최대최소 탐색

최대최소 탐색

• 나와 상대방이 최적의 선택을 한다는 가정하에
• 나에게 최악인 선택을 하는 상대방을 대상으로
• 나의 결정의 가치가 최대가 되는 결정을 내리는 방식으로 게임을 진행한다.
• 최대화와 최소화를 번갈아 반복하여 가장 우수한 후계노드를 선택한다.

몬테카를로 트리 탐색

• 게임과 같은 의사결정 문제에 활용되는 경험적 탐색 알고리즘
• 탐색공간의 무작위 표본화를 바탕으로 탐색트리를 구성함
• 선택, 확장, 시뮬레이션, 역전파 단계를 반복
• 선택 단계에서는 탐사(exploration)와 활용(exploitation)의 균형을 이룰 수 있는 전략을 선택하며, UCT 알고리즘은 잘 알려진 선택전략 중 하나이다.
• 시뮬레이션 단계에서는 순수한 무작위 방법이나 적절한 시뮬레이션 전략에 따른 유사 무작위 방법으로 수를 선택하는 전략을 사용할 수 있다.
• 최종적인 최적 행동 선택을 위해서는 최대 자식, 강인한 자식, 최대-강인 자식, 안전한 자식 등 적절한 전략을 선택할 수 있다.