이 포스팅은 부산대학교 정보컴퓨터 공학부의 인공지능 수업을 들은 학생이 수업을 듣고 문서를 참고해 만든 포스팅으로 절대 이 내용이 정답이라고 보장 할 수는 없다.
================================================================================================================
Searching 을 이용해서 문제를 해결 한다는 것이다. 인공지능이란 과목에서 이것이 뜻하는 바가 무엇인가??
일단, 컴퓨터 과목에서 많이 나오는 State들 즉 시작 state(initial state)와 state들 사이의 이동을 전이(이동) 통해서 목표한(Goal)State를 찾아가는 듯한 느낌이다.
Problem solving agent
요것은 어떤 문제를 해결하는 데 있어서 그과정을 formalize(형식화) , operationalize(조작가능화) 하는것인데.
Define 할것이 있다.
search 알고리즘의 input 들은
◎ initial state -> state space
◎ operator (succesor functions) -> 요놈 역시 state space
◎ goal test
◎ path cost functions : 요건 path에서 개별적인 action에 대한 cost의 총합이라고 볼 수 있다.
위와 같고
Solution 이란 단어가 있는데 이건 initial state 에서 goal state 까지의 path를 말하는 것이고 optimal solution은 코스트가 가장 적게드는 solution이다.
쉽게 말해
서울에서 부산까지 가는 길이 엄청나게 많은데 그중에서 거리가 가장 짤은 길이 바로 optimal solution이 되는 것이다. 여기서 cost는 거리가 될수도 있고 돈이 될 수 있겠지. 그것은 상황마다 달라진다.
슬라이드에는 8-puzzle, 8-queens problem 이 나와 있고 어떤 문제들인지 설명과 각각의 agent에 대해설명이 자세히 나와 있다. 하지만 별로 어려운 것은 아니고 agent를 더 좋게 형식화 하면 훨씬 적은 stae space만 사용한다는 이런 예가 나와 있다. 그러므로 8-puzzle, 8-queens problem에 대해 간략히 설명 하면
8-puzzle은
요런 initial(start) state를 가지고 어떤 숫자가 있는 사각형을 빈칸으로 요리조리 (up, down, right, left)로 옮기면서(요게 successor function) goal state로 가면 된다.
8-queenz는
체스에서 퀸은 대각선으로만 공격할 수 있다는데 서로 공격하지 않게 배치해보자 이런 문제 이다. 앞으로도 많이 나와서 간략히 언급을 하였다.
----------------------------------------------------------------------------------------------------------------
Searching for Solution
state space를 통한 서치... 이게 뭔가??
일단 내용을 보게 되면
● 서치 트리라는 게 만들어 진다. 이것은 initial state 와 successor function에 의해 발생 된다는데..
● 서치 트리라는게 요거는 자료구조에서 배웟던것 처럼 노드가 있는데 이것은 보통 initial state 이다 당연한 거겠지.
● 현재 state에 operator를 적용하므로서 새로운
set of state가 발생한다. (한마디로 확장이 된다는 것이다.)
● 어떤것을 먼저 확장 시킬 것인가는 => Search Strategy 요것에 의해
요런것들이 있는데 쉽게 그림으로 나타내면 아까 8 puzzle problem에서 서치 트리를 한번 나타내 보자.
그림으로 나타내니 훨씬 쉽다. initial state 에서 successor function에 의해 expand가 잘되어 가는것이 보여진다.
그렇다면 이제 본격적으로 알아보자. 다음그림을 보자.
위 그림은 길을 찾아가는 문제를 그림으로 나타낸 것이다. 여기서 처음 시작점(initial state)를 Arad라고 하자. 그 후
어떤 곳을 찾아가기 위해서 searching tree를 만든다고 하면 다음 그림과 같이 나타낼 수 있을 것이다.
이 그림은 처음 봐서는 무슨 뜻인지 잘 이해가 안갈 텐데 일단 Arad가 root node(initial state), 나머지 state들이 계속 나타난 다는것을 알 수 있는데 위의 지도 그래프에서 보면 Arad의 인접한 것이 Sibiu , Timisoara, Zerind 이렇게 있다는것을 알 수 있다. 이것을 (b)에 잘나와 있듯이 Arad에서 expand를 한것이라고 하는데 set of state가 나온거라고 할 수 있다. 거기서 어떤것을 선택해서 계속 반복해서 원하는 목적지에 달하면 solution을 찾는 것이라 할 수 있는데~
여기서 Arad밖에 없을 때는 당연히 Arad에서 expand를 하는것이겠지만 (b)에서 3가지 state에서는 어쩔것인가? 어디서 expand 하는 가를 선택하는 것이 바로
searching strategy 이다.
그리고 (c)에서 보면 Arad가 또 나오는데 요러면 Arad를 선택해버리면 무한 루프에 빠져 버릴 수 도 있지 않겠는가? 한마디로 이것은 자신의 Ancestor(선조)를 expand 하지 않는다라고 생각하면 편할 것이다.
위의 장황한 말을 용어로 정리 해보자
Componets of a search node -> 트리의 구성 요소 정도?
◆ State(node)
◆ Parent node
◆ Action(Operator)
◆ Depth(깊이 이것은 위그림에서는 길에 따른 노드의 갯수 정도가 될것이다.)
◆ Path cost
Fringe -> 요거 매우 중요하다.
한마디로 앞으로 expand 될 노드이다. 요건 일반적으로 queue로 구현이 된다.
위의 말이 무엇인지 모르겠다면 그림으로 한방에!
한번에 이해가 가지 않는가?
그러면 이제 앞으로의 알고리즘은 문제에 의해서 한번 풀어 볼 수 있도록 하자.
No Reason(090330).zip
