Pre-Class

첫번째 퀸을 임의의 위치에 놓은 다음 두번째 퀸 부터 어디에 놓을지를 결정하여야 한다.

퀸은 상/하/좌/우/대각선으로 움직일 수 있다

이때 퀸을 놓을 수 있는 위치는 64가지 이다.
그렇다 보니 O(64!) 라는 말도 안되는 경우의 수가 생긴다.

그렇기 때문에 이러한 배열 판을 알아내는 문제가 바로 8-queens problem이라고 부른다.

States : 0 to 8 queens on the board
Initial state : No queens on the board
Actions : Add a queen to any empty square
Transition model : Returns the board with a queen added to the specified square
Goal Test : 8 queens are on the board, none attacked

3.3 Searching for Solution

3.3.2 Measuring problem-solving performance

성능 평가

Completencess : AI 문제는 반드시 답이 나온다고 가정하는 것이 아닐 수도 있음. 그렇기 때문에 AI 알고리즘이 솔루선을 도출하는 것을 보장하는지 않하는지를 알려주는 것
Optimality : 경우에 따라서는 lowest 한 해결책이 아닐 수도 있기 때문에 상황에 맞는 가장 최적의 해답을 찾아내야 한다.
Time Complexity** : (시간복잡도) 실행 시간을 고려
Space Complexity : 메인 메모리 공간을 얼마나 사용하는지를 고려

3.4 Uniformed Search Strategies

개요 : 목표까지 가는 사전 정보가 없기 때문에 시작부터 결과까지 가는 모든 방법을 찾아내는 전략

3.4.1 Breadth-first search

너비 우선 탐색

처음에는 Dequeue 방식으로 넣고 빼는 식으로 사용
경우에 따라서는 무한루프가 돌아서 Completeness를 만족하지 못할 수도 있기 때문에 명확한 성능 측정 기준을 마련해 두어야 한다.

3.4.2 Uniform-cost search

균등한 비용이 드는 탐색기법 = 평균적으로 비슷한 비용이 든다(Uniform-cost)

균일한 비용이 드는 그래프에서 최단 경로를 찾아주는 다익스트라 알고리즘, 현재 노드에 연결된 자식 노드들의 가중치를 보고 가장 낮은 가중치를 가지는 노드를 우선 방문하여 최단 경로를 찾아내는 알고리즘

p85(시험)

해석) 만약 모든 경로의 비용이 같다면 Uniform-cost search는 BFS 방식으로 움직이게 됩니다. 하지만 BFS와는 다르게 한 step에서 갈 수 있는 모든 경로를 탐색하기 때문에 BFS에 비하여 더욱 엄격한 탐색이 이루어 집니다.

3.4.3 Depth-first search

BFS와 다르게 한쪽 방향으로만 쭉 진행하여서 해답을 찾은 다음 다른 방향으로 나아가는 알고리즘

3.4.4 Depth-limited search

DFS의 Completeness가 완벽하지 않을 수 있기 때문에 이를 해결하기 위하여 DFS가 들어가는 깊이를 제한시켜놓은 알고리즘으로 l깊이에 있는 노드들의 자식 들은 취급하지 않는다.

diameter : 문제 내에서 maximum limit를 설정해 놓은 값

3.4.5 Iteratie deepening depth-first search

조금 조금씩 반복적으로 깊어지는 dfs 해결책으로 최고의 깊이 제한을 찾는 방법이다. 이를 위해 점진적으로 깊이 제한을 늘리어 나가면서 목표를 찾을 때까지 진행한다.

3.4.6 Bidirectional search

Start와 Goal이 명확히 정의가 되는 경우 각 위치에서 출발해서 만나는 지점이 생길때까지 이동

3.4.7 Comparing uniformed search strategies

3.5 Informed (Heuristic) Search Strategies

자기 스스로 발견하는 학습하는 알고리즘

휴리스틱 함수
h(n) = estimated cost of the cheapest path from the state at node n to a goal state

3.5.1 Greedy best-first search

아라드 기준으로 bucharest가 목표라고 했을때 각 도시에서 bucharest까지 바로 갈 수 있다고 한다면 그때에 거리 : SLD Heuridstic

f(n) = h(n)
휴리스틱 알고리즘에서 오로지 목표에 맞는 값만을 우선 선택하는 알고리즘

3.5.2 A* search : Minimizing the total estimated solution cost

f(n) = g(n) + h(n)

g(n) : 특정노드까지 다다르는 코스트
h(n) : 목표에 다다르는 가장