pizzaplanet

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

State Space Graphs 그래프는 state들을 추상화 한 것이다.그래프에서 각 state는 한 번만 발생한다. (Search Trees와의 차이점)보통은 전체 그래프를 메모리에 구축하기 힘들다.(너무 크기 때문) 하지만 유용하게 써먹을 수 있다. Search Trees 루트노드는 Start state이다.대부분의 문제에 대해 전체 트리를 구축하기 힘들다 State Space Graphs vs. Search TreesSearch Tree의 각 노드는 State Space Graph의 전체 Path다.필요에 따라 둘 다 구성하고 가능한 작게 구성하는 것이 좋다. 좌측 그래프를 트리로 구현한다면? (S노드가 Start state, G노드가 Goal state)그래프에서 사이클이 존재하기때문에 단순 ..

본 강의는 UC Berkeley의 AI 강의를 참고하여 진행됩니다. Pacman을 예시로 사용하여 Search Problems의 3가지 구성요소를 살펴보자. (pac coin CPR좀..) A State spaceState space는 각 상황을 나타내는 state의 집합이다.state는 x,y에 위치한 food의 on, ff의 상태이다. 위 이미지에서 간략하게 state space를 계산한다면 3 X 3 크기에 food가 on, off로 나뉘므로 으로 볼 수 있다.물론 더 들어가서 팩맨의 위치, 팩맨의 방향까지 고려할 수 있지만 용어 및 개념파악을 위한 것이므로 더 자세히 들어가지는 말자. A successor function(with actions, costs) 왼쪽 현재 state에서 "N",1.0..

본 강의는 UC Berkeley의 AI 강의를 참고하여 진행됩니다. Agent는 크게 2가지(Reflex, Flanning) 로 나눌 수 있다. Reflex agents- 앞의 수는 고려하지 않고 단지 현재의 상황만을 보고 행동을 취한다.- 현재 상태에 대한 기억 혹은 모델을 가질 수 있다- 그렇다면 reflex agent가 합리적일 수 있을까? Planning agents- 이렇게 하면 어떤지 끊임없이 물어본다. 이 말은 현재 상황(state)에서 취한 액션이 다음 상황(state')을 어떻게 만들고, 다음 상황(state')에서 취한 액션이 또 어떤 다다음 상황(state'')을 만드는지 처음부터 끝까지 계획한다.- 끝까지 계획하기 위해 goal state가 존재해야 한다.- 완벽한 해(Optimal..

본 강의는 UC Berkeley의 AI 강의를 참고하여 진행됩니다. AI를 이용한 자동화 종류들(Applied AI involves many kinds of automation)- 스케쥴링(scheduling), ex> airline routing- 길찾기(route planning), ex> google maps- 의료진단(medical diagnosis)- Web search engines- 스팸분류기(spam classifiers)- 이상 탐지(fraud detection), ex> FDS(Fraud Detection System, 금융거래에서 이상거래 탐지)- 추천(recommendations), ex> youtube, amazon- 그 외

본 강의는 UC Berkeley의 AI 강의를 참고하여 진행됩니다. Rational behavior- 한정된 세계(closed worlds)에서는 쉽다. 하지만 현실세계(open worlds)에서는 어렵다 Perception- 패턴 매치(match patterns)는 쉬우나 무슨 뜻인지 이해는 어렵다(understand meaning).