Problem Solving이란?

Problem Solving은 상태공간(state space) 내에서 초기상태(initial state)를 목표상태(goal state)로 진행하는 과정(path)을 찾는 탐색(search)이다.

example - TSP(Traveling Salesperson Problem), The 8-Puzzle, The 8-queens problem

우리에게 주어진 초기상태에서 어떠한 연산(동작)들을 적용하여 우리가 원하는 목표상태로 만들 것이다.
TSP에서 생각해보자.
이 때, 모든 경우의 수를 계산하는 방법의 time complexity는 $n!$이다. 이는 우리가 현실세계에서 적용하기 어려운 방법이다. (현실 세계의 n은 매우 크기 때문에 time complexity가 매우 커진다)
그렇다면 가장 좋은 답(goal)은 아니지만 '어느정도 좋은 답(goal)을 찾는(heuristic)' 알고리즘을 적용하면 $n^2$으로 줄일 수 있다.

우리는 이러한 문제들에서 '더 빨리', '더 좋은' 답을 찾는 방법들을 배운다.

그렇기 위해서는 문제를 우리가 알아보기 쉬운 형식으로 표기할 필요가 있다.
우리는 다음과 같은 것들을 정의한다.

• 초기상태 (Initial state)
• 연산자 (Operator)
• 목표상태 (Goal state)
• 가중치 함수 (Path cost function)

→ Search Algorithm의 Input

Searching for Soultion

Search Tree

탐색(search)하는 과정을 우리가 알기 쉽게 표기하기 위해 Search Tree를 이용한다.
Search Tree는 아래와 같은 member를 가진 Node로 이루어진 Tree이다.

• $n.State$ (현재 탐색 상태)
• $n.Parent$ (그 이전까지의 Path)
• $n.Action$
• $n.Path-Cost$

초기상태(Initial state)가 root node가 되고 branch는 action을 의미한다.

현재state에 action을 실행하면 state가 expanding 되고, 새로운 state를 가진 node가 generate 된다.

Methods of Expanding

앞서 우리는 문제에서 '더 빨리', '더 좋은' 답을 찾는 방법들을 배운다고 했다.
이를 위해 앞으로 state를 expanding하는 방법에 대해 고민해본다.