Problem solving
Search: find a sequence of actions ->goal can be achieved
문제를 표현하는 방법
-State Space: 상태 공간 표현
내가 다루려는 문제를 하나의 그래프로 표현
vertices(정점, 문제의 서로 다른 상태), edges(간선, 특정한 액션들)
* 상태 공간은 아래 4가지로 이루어짐.
ex) Planning in a blocks world, 8-Puzzle, Inference, Route finding
->Inference에 대한 예시
즉, State Space상에서 아래와 같은 연결관계가 있다는 걸 search를 통해 알게 된다면
search를 통해 찾은 solution이라고 볼 수 있다.
*Solution path=(S, s1, s2, G) = (c, e, f)
[State Space Search]
Search algorithm
1) Start: S에서 시작
2) Test: 현재 내가 목표상태에 와있는지 test(확인)한다.
3) Expand: 아직 목표상태가 아니라면, 다음 action으로 갈 때 어떤 state들이 가능한지 확인한다.
4) Choose: 대기열에 대기시키고 나서 State 하나를 다시 선택한 후 (2)번 과정으로 돌아간다.
1. DFS(Depth-First Search)
open: 앞으로 가볼 state들의 대기열
closed: 이미 가서 확인한 state들의 모음
-> Solution Path: A->B->E->F->G
2. BFS(Breath-First Search)
위의 Example 너비우선탐색 방법으로도 해보기
-> Solution Path: A->C->G
*Search space 정의
-b) Branching factor: state에서 다음 state로 갈 수 있는 경우의 수
-s) Search depth: 몇스텝이나 가야 자명한 goal에 도달할 수 있는가(?)
DFS vs BFS 중 더 효율적으로 찾을 수 있는 것이 무엇인지 파악
goal에 도달했다고 무조건 효율적 solution에 도달했다고 보장할 수 없음.
3. IDS(Iterative Deepening Search)
깊이우선탐색을 진행하되, 깊이 1 이상은 가지 않겠다. 그다음 depth를 2로 늘리고 다시 DFS 진행.
->Goal을 못찾고 끝나면depth를 1씩 늘리면서 위의 과정 계속 반복
*장점: Optimal한 경로를 찾을 수 있다.
*Time = O(b^d)
*Space = O(b*d)