인공지능 특론- Search-Part 1

Alpha-Beta

Search에 대해서 알아보자 .인공지능에서 쓰는 기법이다. 

문제를 해결하기 위해 Search하는 것이다.

Puzzle 알 맞추기  A -> B로 제일 최단 경로를 알아보기  , Chess를 해보기,  John이 Mary의 조상이라고 증명해보기  이런 것들이 다 Search하는 기법이다.

과정들이 있다. 먼저 해야할 것은  문제가 정확히 무엇인지 아는 것이다.

초기의 상태가 무엇이고 궁극적인 상태는 무엇인지 알아야하는 것이다.  그리고 문제를 분석하고 풀어야 할 task를 나타내야 한다 여기서 쓰이는게 자료 구조이다.

그리고 search methods를 적용하는 것이다

Problems의 종류는 State Space Representation , AND /OR graph, Problem-reduction representation, Game Tress가 있다.

Search Method로는 Blind State Space Search, Heuristic Search, Game Tree Search가 있다.

Search Systems의 구성요소는 자료구조, 연산자, Control Strategy가 있다.

Problem의 종류인 State Space Representation을 봐보자 

형태는 Graph(V,E)이다. 

V는 Vertex

E는 Edge이다.

Representation할때 또 쓰이는 용어가 있는데 state와 operator가 있다.

State는 snapshot 을 찍는 것이다. 초기 상태의 snapshot을 찍어서 보여주는것이다

operator는 어떤 상태에서 다른 상태에서 변하는 행위이다.

예로 들자면 8-Puzzle을 풀기위해선는 문제 문제가 무엇인지 판단하고 State를 나타내준다. Operator가 4가지로 구성된 directions라고 알수있다. State Space는 Search 했을때 경우의 수를 보여준다 .9!/2가지이다. 이렇게 표현해야한다.

State space search는 state space안을 검색하는 과정이다. 

목표는 제일 짧은 경로를 찾는 것인데 문제는 search space가 엄청 커서 문제가 있다

이를 해결하는게 heuristic이다. 

Heuristic은 쉽게 말해서 최선의 해답을 찾기 위해 모든 경우의 수를 따져보는 것이다

Heuristic외도 Search Methods(Algorithm)은 많다. 

Basic Search로 Blind Search는 DFS, BFS가 있고 Heuristic을 쓰는 search는 Hill -Climbing, Best First,Beam Search

Optimal Search는 Branch and Bound A, A*가 있다. A*가 제일 좋다고 한다.

Adversary Search는 Minimax, Alpha-Beta pruning 등등이 있다. 나중에 수업을 들으면서 하나씩 알아갈 예정입니다.