균일 비용 탐색 Uniform Cost Search(UCS)

Uniform Cost Search

---

Strategy: Cost가 가장 낮은 노드를 우선 탐색한다.

Implementation: 우선순위큐로 작성한다. (우선순위: 누적 cost)

Uniform Cost Search Properties

---

- 탐색시간: 

- 프린지 필요 용량: 

- Complete 한가? Yes (cost가 양수값을 가질때)

- Optimal 한가? Yes( 다음에 배울 A*를 통해 증명됨)

Uniform Cost Search Issues

---

- Remember: UCS는 cost 등고선의 증가를 설명함

- The good: UCS는 complete하고 optimal 하다.

- The bad:

목표에 대한 정보가 없다.

모든 방향에서 옵션을 탐색한다.