pizzaplanet

지금까지는 Uninformed Search(DFS, BFS, UCS) 즉, 정보를 사용하지 않았을때의 탐색방법에 대해 배워보았다.앞으로는 어떠한 정보(Heuristics)를 사용하여 탐색하는 Informed Search에 배워볼까 한다. Uninformed Search- DFS- BFS- UCS Informed Search- Heuristics- Greedy Search- A* Search- Graph Search

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:목표에 대한 정보가 없다.모든 방향에서 옵션을 탐색한다.

Breadth-First Search Strategy: 얕은 노드를 먼저 확장한다.Implementation: 프린지는 Queue(FIFO)로 구현한다. Breadth-First Search Properties- 탐색시간: - 프린지 용량은 얼마만큼 필요한가? - complete 한가? yes- optimal 한가? 모든 코스트가 1일때는 optimal 하다. 예로 더 좋은 코스트가 더 깊은 곳에 있다면 optimal 하지 않다.

Depth-First SearchStrategy: 더 밑으로 갈 수 없을때까지 혹장한다.Implementation: Fringe는 Stack(LIFO-Last in Last Out)로 구현한다.처음 시작하면 S를 확장시켜 d, e, p 순으로 프린지에 넣는다. 다시 d를 확장시켜 b, c, e를 프린지에 넣고 b를 확장시켜 a를 프린지에 넣는다. a를 확장시키려 하였으나 더 이상 확장시킬 수 없다.이때 길이 막혔으므로 부모노드로 돌아가는 백트래킹(Backtracking) 과정을 밟는다. 그럼 b로 올라가며 b에서도 확장시킬 자식 노드가 없어 다시 백트래킹 과정을 밟는다. d까지 올라와서 보니 c, e가 있으므로 c를 확장시켜 다시 탐색을 시도한다. S->d->b->a->Backtracking->c->a ..

Search Example: Romania 위와 같은 그래프가 있다. Start state는 Ared, Goal state는 Bucharest이다.이 그래프를 참조하여 트리를 이용해 Ared to Bucharest 길찾기를 해보자. 이제부터 나올 포스팅은 프로그래머의 시선에서 위 그림처럼 트리노드를 확장해 나가는 것을 어떻게 구현할 것인지 생각을 해보며 진행 될 것이다. General Tree Search Important ideasFringe: 방문하지 않은 노드를 쌓을 공간Expansion: 꺼낸걸 확장시켜 프린지에 집어 넣음Exploration strategy: 프린지에서 어느 것을 꺼낼 건지 Example: Tree Search

조건부 확률밀도함수는 아래와 같이 정의 된다.

결합확률밀도함수는 n개의 임의변수에 대해 주어진 값 조합에 근접할 확률을 제공한다.

결합 확률질량함수는 n개의 랜덤변수에 가능한 모든 값 조합에 대한 확률을 지정한다. 더 쉽게 말하면 확률변수(Random variables)가 여러개일 때 이들을 함께 고려하는 것. 결합확률질량함수를 지정하면 많은 수의 값이 필요하다.- 은 각각 임의 k개의 이산 값 중 하나를 취할 수 있는 임의 n개의 변수를 가정한다.- 독립성 또는 조건부독립성을 가정하면 단순화 할 수 있다. P(Cavity, Toothache)가 2x2 매트릭스일때 Joint Probability(결합확률)은 아래와 같다. Joint Probability Toothache Not Toothache Cavity 0.04 0.06 Not Cavity 0.01 0.89 [ Sum of probabilities = 1.0 ]