pizzaplanet

게임을 예로 들어서 보자면 지금까지 포스팅은 플레이어가 1명이었을 때였다.이제는 플레이어가 2명이고 서로 적대적인 관계일때의 Search에 대하여 알아보자. Adversarial Search 적대적인 관계가 존재할 때 적대적 관계의 행동을 미리 고려하여 결정을 내리는 Search이다. 팩맨을 예로 들면 팩맨이 food만 먹는게 아니라 Ghost의 행동도 고려해야하는 것. Ghost가 똑똑하게 나를 향해 올수도, 멍청하게 혼자 이리저리 움직이기만 할 수도 있으나 어쨋든 Ghost의 Action을 고려하여 팩맨의 Action을 취해야 한다. 간단하게 Zero-Sum Game이라 생각하면 된다. Minmax Values 간단하게, 나는 Max 값을 취하고 상대는 내 입장에서의 Min 값을 취한다. 상대가 내 ..

Local Search Local search: 더 나아질 수 없을 때까지 search 하는 것이며 fringe를 쓰지 않는다.New successor: 로컬을 다른 지점으로 변경한다.속도도 빠르고 메모리도 적게 잡아먹으나 해를 찾았다고 해서 optimal하지는 않을 수 있다. Hill ClimbingSimple, general idea:- 아무 곳에서나 시작한다.- 반복: 가까운 곳에서 현재 위치보다 나은 곳이 있다면 그 곳으로 이동하고 나은 곳이 없다면 종료한다. 로컬을 어디서 시작하느냐에 따라 도달하는 Goal 지점이 달라진다. 그림상의 current state에서 시작한다면 local maximum에 도달하여 global maximum은 찾지 못하고 끝나게 된다.

Constraint Satisfaction Problems - search problems의 special subset- State는 도메인 D의 값을 가진 변수 에 의하여 정의된다.- Goal test는 변수의 하위 집합에 허영되는 값의 조합을 지정하는 제약 조건 집합. 아 인공지능 배우면서 느끼는건 말이 더 어렵다. 해보는게 더 쉬운 접근법이다. CSP Examples Variables: WA, NT, Q, NSW, V, SA, T Domains: D = { Red, Green, Blue } Constraints: 인접한 지역은 서로 다른 색이여야 한다.Implicit: Explicit: Solutions: 모든 Constraints를 충족시키는 것이며 솔루션은 유니크 하지 않을 수 있다.(솔루션이 ..

A* Search전혀 새로울 것이 없는 탐색 방법이다.2018/05/04 - [Artificial intelligence] - Uninformed Search and Informed Search2018/05/04 - [Artificial intelligence] - 탐욕 탐색 Greedy Search실제 거리 + 예측거리식을 이용하는데 이 두가지를 섞은 것이 A* Search이다. Combining UCS and Greedy - Uniform-cost orders by path cost, or backward cost g(n)- Greedy orders by goal proximity, or forward cost h(n) A* Search orders by the sum: f(n)=g(n)+h(n)만약..

Greedy Search 휴리스틱h(x) 가 가장 작은 노드부터 확장해 나가는 것이다. 이 휴리스틱 값은 우리가 입력 혹은 설정해주어야 하는 값이다. Arad -> Bucharest 상황을 가정해보자.우측 Red Box는 각 노드에서 Bucharest까지의 휴리스틱을 나열해놓은 것이다.Arad에서 Bucharest까지의 휴리스틱은 366, Bucharest에서 Bucharest까지의 휴리스틱은 0.다시 짚고 넘어가야 할 것은 휴리스틱은 real cost 즉, 실제 거리가 아닌 예상 거리이다.Arad와 닿아있는 노드는 Zerind, Sibiu, Timlsoara 3가지. Rad Box를 참고하면h(Zerind)=374h(Sibiu)=253h(Timlsoara)=329이 3가지중 가장 작은 값을 가진 Sib..

Heuristics 간단하게는 A노드에서 B노드까지 가는 예상 거리를 휴리스틱이라 할 수 있다.이 휴리스틱은 실제값보다 작거나 같아야(h

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