3. Solving Problems By Searching
ㅇProblem-solving agent
- one kind of goal-based agent
- Problem-solving agents use atomic representations(블랙박스 접근)
ㅇ A Problem can be defined formally by five components
1. Inital State : The initial state that the agent starts in. 에이전트가 시작되는 초기상태
2. Actions :
3. Transition model : A description of what each action does.
4. Goal test : The goal test, which determines whether a given state is a goal state.
5. Path cost : A path cost function that assigns a numeric cost to each path.
ㅇ Uniformed Search (Blind Search)
- 전체 상태를 경험적으로 분석할 수 없기에 Goal State로 향하는 어떠한 방향성을 가지고
있지 않고 모든 방향으로 뻗어나간다
1. Breadth-first Search : Frontier에서 가장 얕은 탐험되지 않은 노드들 먼저 확장하는 방법.
여기서 Frontier는 FIFO Queue로서 구현이 되어야만 한다.
2. Uniform-cost Search : 현재 Frontier에서 확장되지 않은 노드 중에서 가장 비용이 적은 노드부터 선택해서 확장하는 것을 의미
3. Depth-first Search : 깊이 우선 탐색 방법. Frontier에서 확장되지 않은 노드중에서 가장 깊은 것을 우선적으로 확장한다. Frontier는 Stack의 형태로 구성
4. Depth-limited Search : 일반적으로 DFS와 완전하게 일치. 다만 깊이에 제한을 둔다는 점에서 차익 았다. 깊이 제한을 L(Limit)이라고 한다면 깊이가 L인 노드에는 자식 노드가 붙지 않는다.
전체 상태 공간의 지름을 알고 있을 경우 효과적
5. Iterative deepening depth-first Search : DLS에서 limit를 점차적으로 늘려가는 방식.
전체 상태 공간의 지름을 모를 경우 효과적
6. Biderectional Search : 시작 Node와 목표 Node에서 동시에 탐색을 시작하는 것.
이를 사용하는 이유는 Breadth-first에 비해서 시간과 공간을 많이 줄일 수 있기 때문이다.
ㅇ Informed Search(Heuristic Search)
- State-space의 가지에서 가장 전도유망한 방향으로 Search를 진행
- Blind Search의 단점을 극복하기 위해서 나타났음
1. Greedy best-first search : F(n) = H(n)
2. A* search : F(n) = H(n) + G(n)
3. Memory-bounded heuristic search
- one kind of goal-based agent
- Problem-solving agents use atomic representations(블랙박스 접근)
ㅇ A Problem can be defined formally by five components
1. Inital State : The initial state that the agent starts in. 에이전트가 시작되는 초기상태
2. Actions :
3. Transition model : A description of what each action does.
4. Goal test : The goal test, which determines whether a given state is a goal state.
5. Path cost : A path cost function that assigns a numeric cost to each path.
ㅇ Uniformed Search (Blind Search)
- 전체 상태를 경험적으로 분석할 수 없기에 Goal State로 향하는 어떠한 방향성을 가지고
있지 않고 모든 방향으로 뻗어나간다
1. Breadth-first Search : Frontier에서 가장 얕은 탐험되지 않은 노드들 먼저 확장하는 방법.
여기서 Frontier는 FIFO Queue로서 구현이 되어야만 한다.
2. Uniform-cost Search : 현재 Frontier에서 확장되지 않은 노드 중에서 가장 비용이 적은 노드부터 선택해서 확장하는 것을 의미
3. Depth-first Search : 깊이 우선 탐색 방법. Frontier에서 확장되지 않은 노드중에서 가장 깊은 것을 우선적으로 확장한다. Frontier는 Stack의 형태로 구성
4. Depth-limited Search : 일반적으로 DFS와 완전하게 일치. 다만 깊이에 제한을 둔다는 점에서 차익 았다. 깊이 제한을 L(Limit)이라고 한다면 깊이가 L인 노드에는 자식 노드가 붙지 않는다.
전체 상태 공간의 지름을 알고 있을 경우 효과적
5. Iterative deepening depth-first Search : DLS에서 limit를 점차적으로 늘려가는 방식.
전체 상태 공간의 지름을 모를 경우 효과적
6. Biderectional Search : 시작 Node와 목표 Node에서 동시에 탐색을 시작하는 것.
이를 사용하는 이유는 Breadth-first에 비해서 시간과 공간을 많이 줄일 수 있기 때문이다.
ㅇ Informed Search(Heuristic Search)
- State-space의 가지에서 가장 전도유망한 방향으로 Search를 진행
- Blind Search의 단점을 극복하기 위해서 나타났음
1. Greedy best-first search : F(n) = H(n)
2. A* search : F(n) = H(n) + G(n)
3. Memory-bounded heuristic search
댓글