Taessing

줄여서 약자 CSP 이야 이번장 부터는 문제를 이용해서 이론을 도출하는 식으로 한번 공부를 해볼려고 한다.

먼저 기본적인 개념을 잡고 가자
우선 Constraint satisfaction problems(CSP) 문제를 푸는데 있어서 어떤 제약을 만족해야 되는 그런 문제를 말한다.

state는 Variable Xi 로 나타내고, domain Di 에서 오는 value 값을 지닌다.
goal테스트를 만족하기 위해서 set of constarint를 만족 하여야 한다.

이것을 간단히 Map-coloring 예제로 나타내면 다음 그리과 같다.

다음과 같이 Varialble은 지도의 지역들 지역들이 가지는 색깔값들은 domain Di에서 오게 되고 Constraint는 위와 adjacent 하는 지역은 다른 컬러를 지녀야 한다는 것이다.


1. 강의록 12 ~ 13 페이지에 소개된 backtracking search를 이용하여 4-queens problem을 풀면 어떻게 될지 강의록 17 페이지에 보인 것과 같은 형태로 그려보라.

먼저 backtracking search가 어떻게 돌아가는건지 한번 알아보도록 하자.

다음과 같이 Varialble은 지도의 지역들 지역들이 가지는 색깔값들은 domain Di에서 오게 되고 Constraint는 위와 adjacent 하는 지역은 다른 컬러를 지녀야 한다는 것이다. 이것을 토대로 이제 문제도 한번 풀어보자.

이런식으로 문제를 쉽게 풀 수 있다.

2. Backtracking search를 이용하여 graph coloring problem을 풀기 위해 most constrained variable과 most constraining variable 및 least constraining value heuristic을 모두 사용하면서 forward checking까지 적용하고자 핚다. 아래 graph의 node들에 {Blue, Green, Red}를 칠핛 경우 생성되는 search tree를 그려보라. 단, variable이나 value의 우선 순위가 같을 경우에는 그 이름의 alphabet 순을 따라 선택핚다.
이문제를 풀기위해서 백트래킹도 알아야 하겠지만 most contrained variable 과 most contraining variable, least constraining value heuristic, forward cheking 까지 알아야 한다.

most constrained variable
fewest legal value를 선택을 한다.

most constraining variable
영향을 제일 많이 주는 variable 부터 선택을 한다.

least constraning value
영향을 가장 적게 주는 value 부터 선택한다.
-> 남아 있는 variable중 fewest value 선택

forward cheking
어떤 variable 이든 더이상 legal value가 존재 하지 않으면 종료를 하는것이다. variable에 value를 assign 하면서 다른 남은 variable들에게 어떤 value가 assign될 수 있는지 항상 체크 하는것이다.


요렇게 푸는 것이다.

3. 위 2번 graph의 B에는 Red 그리고 F 에는 Green이 지정되어 있는 상태에서 forward checking과 arc consistency algorithm을 적용하고자 핚다. 교과서 Figure 5.7의 AC3 algorithm을 이용핛 경우 종료 시까지 총 몇 개의 arc가 처리되고 몇 개의 arc가 다시 queue로 insert되며 또핚 최종 결과는 어떻게 되는가? 단, queue에는 arc들이 다음과 같은 순서로 들어 있다고 가정핚다: AB, BA, AD, DA, AE, EA, BC, CB, BE, EB, CE, EC, CF, FC, DE, ED, EF, FE.

Arc consistency 가 뭔지를 알아야 한다.

본 포스팅은 부산대학교 정보컴퓨터 공학부 4학년 학생이 인공지능 수업을 들은 내용을 토대로 작성한 것입니다. 본 포스팅의 내용의 신빙성을 책임지지는 않습니다.
--------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------
Informed Search Strategies

우리는 이전 내용에서 Searching에 의해서 문제를 해결하는 쉽게 이야기 해서 어떤 문제의 해답을 서치하는 몇가지 방법들을 살펴 보았다. 간단히 Review를 해본다면

먼저 중요한 용어 Fringe라는 용어가 있었다. Fringe는 Expand하기를 원하는Node들의 집합이다. 일반적으로 구현이 될때 queue로 구현이 된다. 그리고 Depth는 solution을 찾기위해 search를 할 때 만들어지는 Searching tree의 깊이, path cost는 한node에서 다른 node로 가는 비용이라 할 수 있다.

Breadth-first Search : 이건 같은 Depth의 fringe상에 있는 node들을 차례대로 expand 한다. Breadth가 먼저 즉 fringe들을 다 expand 하고 다음 Depth로 넘어간다.
Uniform Cost Search : depth의 수치보다 코스트의 수치로 프린지에 있는 노드를 선택해 expand한다.
Depth-first Search : 이건 Depth first, 즉 한쪽의 모든 Depth를 search 한다. 그다음 옆으로 이동한다.
Depth-limited Search : Depth-first에 limit를 준다.
Iterative Deeping Search : Depth-limited의 limit를 증가 시킨다.
Bidirectional Search : Start(initial) 과 Goal에서 동시에 뻐어 나온다. 그래서 제일 먼저 만나는것을 솔루션으로 한다.
이런것들을 알아 보았다. 위의 Searching 방법들의 성능을 비교한 것은 다음과 같다.

위의 전술들은 모두, Time과 space가 어떤 변수에 대해 exponential 하다. 이문제를 해결 하기 위해 이제 부터 우리는 Informed Search를 한번 배워 보자. 인공지능적인 요소는 여기서 부터 나오는 것이다.

먼저 이 Informed search strategies에는
Apply evaluation function to determine the order of the nodes in the queue.
평가 함수가 존재한다. 이평가함수는 큐속에 있는 노드들의 순위를 결정한다.
Evaluation function f(n):
바로 평가 함수 f(n) 파라미터는 어떤 한 노드 n 이다.
f(n) =distance through node n to the goal
노드 n부터 goal 까지의 distance, 즉 거리이지만 평가 값이라고 할 것이다.
Comes from problem-specific knowledge
problem-specific knowledge에서 이값을 도출할 수 있다.
Priority queue maintains the order of the fringe nodes.
프린지노드의 순서를 우선순위 큐로 결정할 수 있다.

Components of evaluation function:
그리고 평가함수의 구성요소를 살펴보자.
h(n):heuristic function
휴리스특 펑션 h(n)이 있다.
h(n) =estimated cost of the cheapest path from node n to the goal
이 h(n)은 노드 n에서 goal 까지 가장 짧은거리를 추측해보는건데 우리가 주로 보는 내용이 길찾기 이런게 많기 떄문에 f(n)은 노드 n에서 골까지의 직선거리로 추측하기도 하고 그런것이다.
g(n):path cost from the start node to n
이건 우리가 앞에서도 봤었던 시작 노드부터 노드 n 까지의 path cost이다.

만약 여기서 f(n) = h(n) 이라면 이건 단지 평가를 휴리스틱 함수로만 한것이다. 그리고 f(n) = g(n) 이라면 이것은 uniform cost search 이다 평가 기준이 path cost 이기 떄문이다.

이제 이 f(n)을 이용한 search 방법들에 대해서 알아보도록 하자.

Greedy best-fit search
일단 먼저 위의 그림은 루마니아의 지도인데. 오른쪽의 직선거리가 각 노드에서 Bucharest까지의 직선거리가 있다. 우리는 이것을 h(n), 휴리스틱 펑션값으로 이용을 할 것이다. Greedy best-fit search란 f(n)을 바로 휴리스틱 펑션만으로 판단하는 것이다.
즉 f(n) = h(n) 이렇게 되는 것이다. 이것을 바탕으로 Arad에서 Bucharest까지의 최단거리를 가지는 Path를 찾아 보자. 상당히 간단하다.

노드를 expansion하는 기준이 h가 가장 작은 노드이다. 즉 h값이 가장 작은 순서대로 queue에 들어 가있다고 생각하면 된다.
depth와 breadth에 전혀 관계가 없다.

Take the biggest bite possible the name “greedy search”
Greedy best-fit search는 가장 가능성이 큰것을 취한다. 이름이 그리디 서치이다.

Evaluation:
Neither optimal nor complete(cf: depth-first search)
이것은 옵티말 하지도 컴플리트하지도 않다.
Time and space complexity
Retains all nodes in memory
메모리안에 모든노드가 있다.
O(b^m), m:maximum depth of the search space
b의m승 오더가 적용이 되는데 m은 가장 깊은 depth 즉, 서치한트리에서 가장 깊은 depth값이다.
Good heuristic function can reduce the space and time complexity.
좋은 휴리스틱 펑션이 space와 time complexity를 줄일 수 있다.

이제 이것보다 약간 발전된 형태인 A* Search에 대해 알아보자.

A*Search
Minimizes the total estimated solution cost
추측된 총 솔루션 코스트를 최소화 시킨다.
Combination of greedy best-first search and uniform-cost search
A* 서치는 쉽게 이야기 해서 greedy best-fit 서치와 uniform-cost 서치의 콤비네이션 즉 합친거다
f(n) = g(n) + h(n)
그래서 평가함수 f(n)은 g(n)과 h(n)을 더한 결과가 된다.
g(n):path cost from the start node to n
h(n):estimated cost of the cheapest path from nto the goal
f(n):estimated cost of the cheapest solution through n
위의 설명은 저 위에서 수차례했으니 패스 바로 위의 지도에서 solution을 찾는 서치트리를 만들어보면

역시 위의 방법은 비슷하나 평가 함수에 g(n)이 들어오게 딘다.

Theorem:
이것에 Theorem에 대해서 보자.
A*using Tree-Search is optimal if h(n)never overestimates the cost to reach the goal. (Such an h(n)is called an admissible heuristic.)
A* 서치는 한가지 조건만 충족이 된다면 옵티말 하다. 바로 h(n)을 측정할때 h(n)이 실제보다 큰값으로만 측정 되지 않으면 된다.(이런 h(n)이 admissible heuristic이다.)

Proof :
Let C*be the cost of the optimal solution.
C*를 옵티말 솔루션의 코스트라고 하자
Suppose a suboptimal goal node G2 appears on the fringe. Then,
서브옵티말(옵티말하지는 않는다는것이다.) 골노드 G2가 프린지 상에 나타나게 된고 가정하자. 그러면
f(G2) = g(G2) + h(G2) = g(G2) > C*
G2에서 골까지 가는 평가 함수값 = 시작노드에서 G2까지의 path cost + G2에서 골까지의 h값  = g(G2) > C*
But, for a fringe node n that is on an optimal solution path
하지만 프린지 노드 n은 옵티말 솔루션 패스이므로
f(n) = g(n) + h(n) <= C*
이렇게 되고
Since f(n) <g(G2), G2 will not be expanded.
결구 f(n)< g(G2) 가 되고 G2가 expand가 되지 않는다. 역시 증명의 길은 어렵다는것을 꺠닫게 되는구나.

A*is optimal and complete.
A*는 옵티말 하고 컴플리트 하다. 단 h가 overestimate 하지않는다면 말이다.

Time and memory complexity:
Exponential time complexity
역시 exponential time complexity를 지니게 된다.
Perfect h->no search (practically impossible)
퍼펙트한 h -> 서치가 없게 되지 이건 불가능하다.
Exponential memory complexity
exponential한 메모리 complexity를 지니게 된다.

A*is optimally efficient for any given heuristics.
A*는 어떤 주어진 휴리스틱에도 옵티말하게 효율적이다.
Search is done efficiently by pruning the subtrees below the nodes with f(n) > C*.
서치는 서브트리를 가지치기 하면서 완료가 되는데 어떤서브티리이냐 하면 f(n) > C*것의 node 밑의 서브트리를 가지치기 한다.
No other optimal algorithm is guaranteed to expand fewer nodes than A*.
A*다 더적게 노드를 expand하는 옵티말 알고리즘은 없다.(이것이 중요하다.) 하지만 아직은 시간과 공간의 complexity가 부담이 된다. 좋은 휴리스틱 펑션을 찾는것이 필요하다. 그것은 유니폼 코스트 서치를 사용하는것보다 훨씬 더 좋게 된다는 말이 된다.
 
당연한 법칙 3가지를 소개 하면
Recall that f(n) = g(n) + h(n)
h= 0, uniform cost search g(n) -> path cost만을 이용해서 판단
g = 1, h= 0 breadth-first search -> 이것은 모든 노드를 차례대로 expand 해야한다. 판단기준이 모두 같기 때문에
g= 0 greedy best-first search -> 이것은 h(n)으로만 판단 하는 greedy best-fit 알고리즘과 같다.

이제 본격적으로 heuristic function에 대해서 알아보도록 하자.
8-puzzle problem을 예를 들어서 알아 보자.


h1= the number of tiles that are in the wrong position
h1 첫번쨰 휴리스틱은 잘못된 위치에 있는 타일의 개수이다.
h2= the sum of the distances of the tiles from their goal positions (Manhattan distance)
두번째 휴리스틱은 그들의 골포지션으로 부터 타일들의 거리의 총합이다. (맨하탄 디스턴스라고 한다.)
* Both are admissible: never overestimates
둘다 절대 overestimate 되지 않았다. h1같은 경우는 그러려니 싶지만 h2는 왜그런지 약간 헷갈릴 수도 있다. 이것은 타일들이 그위치에서 바로된 위치에서 거리보다도 그곳으로 실제로 가기위해서는 다른타일도 움직여야 하는 비용까지 더해지기 때문이다.

The total number of nodes expanded:
expand되는 노드의 총 개수는?
A*with effective branching factor b*(Figure 4.8)
브랜칭 팩터 b*r가 있다.
N= 1 + b* + (b*)^2+ (b*)^3+ … + (b*)^d, d :depth
요런식으로 expand 되는 노딍 총수를 구할수있다.

Dominating heuristic:
We say that h2 dominates h1 if for any node n,
h2가 h1을 어떤 노드 n에서든 dominate한다고 할 수 있는데
h2(n) >=  h1(n).
h2(n) >= h1(n)이기 떄문이 다.
It is always better to use a heuristic function with higher values, as long as it does not overestimates.
그러니까 정리를 하면 h값은 overestimate 되지않는 선에서 높은 값을 선택하는 것이 좋다.
그림에서 보게 되어도 h2가 depth가 커질수록 effective branching factor값이 더 많이 작아진다는 것을 알 수 있다.
그러므로 1 + b* + (b*)^2 + ..... + (b*)^d 인 expanded 노드의 총수 역시 작아진다는것을 알 수가 있다.

이제 좀더 확장된 주제로 넘어자 보자.
Inventing Admissible Heuristic Functions

Consider a relaxed problem:
relaxed problem에 대해서 생각해보자.
A relaxed problem is a problem with fewer restrictions on the action.
relaxed problem은 action에 있어서 제약이 더 없는 문제를 뜻한다.
The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem.
relaxed problem에 대한 옵티말 솔루션의 코스트는 오리지널 문제에 대한 admissible 휴리스틱이다.
The optimal solution in the original problem is at least as expensive as the optimal solution in the relaxed problem. 
original problem에 있는 옵티말 솔루션은 적어도 relaxed problem에 있는 옵티말 솔루션과 비슷하게 expensive 할것이다.


8-puzzle의 예를 한번들어보자.
A tile can move from square Ato B if Ais horizontally or vertically adjacent to B and B is blank.
타일은 B가 비어있고 A와 수직또는 수평으로 근접할때 A에서 B로 이동이 가능하다.
 
Relaxed problems:
relaxed problem으로 생각하면
(a)A tile can move from square A to B if A is adjacent to B(h2)
A에 있는 타일은 A가 B에 adjacent할때 A에서 B로 이동이 가능하다 (h2)
(b)A tile can move from square A to B if B is blank.
A에 있는 타일은 B가 blank일떄 A에서 B로 이동이 가능하다.
(c)A tile can move from square A to B. (h1)
A에 있는 타일은 A에서 B로 이동이 가능하다. (h1)

Construction of a relaxed problem:
relaxed problem을 구축해보자.
Can be done automatically if a problem definition is written in a formal language
문제의 정의가 일반적인 언어로 쓸수 있다면 자동적으로 완료가 된다.

Trade off between accuracy and computation time:
정확도와 computation time을 trade off 한다.
It takes more time to derive more accurate heuristic.
좀더 정확한 휴리스틱은 더많은 시간을 소요할 것이다.

Using multiple admissible heuristics:
여러개의 admissible heuristic을 이용해보자
If a set of admissible heuristics h1,…, hm is available, and none of them dominates any of the others, we can use the
admissible 휴리스틱 h1,....의 집합이 있고 hm은 이용가능하며 그들중에 어떤것도 다른것을 dominate 하지 않는다. 
heuristic most accurate on the node in question:
휴리스틱은 어떤 노드에서 가장 정확한 휴리스틱을 선택하면 된다.
h(n) = max{h1(n),…, hm(n)}
그러므로 h(n)은 h1(n),......,hm(n)에서 가장 큰값을 선택하는것이다. 어짜피 집합은 admissible 한 휴리스틱이기 떄문에.

Consider a subproblem:
subproblem에 대해서 생각해보자.
Admissible heuristics can also be derived from the solution cost of a subproblem.
Admissible 휴리스틱들은 또한 subproblem의 솔루션 코스트로 부터 이끌어 낼 수 도 있다.
Can be substantially more accurate than Manhattan distance in some cases
어떤경우에는 맨하탄 디스턴스 모다 훨씬 정확할 수도 있다.


Pattern databases:
패턴 데이터베이스
Store exact solution costs for every possible subproblem instance (every possible configuration of four tiles and
모든 가능한 subproblem instance(4개의 타일과 blank의 모든 가능한 설정)에 대한 모든 가능석에 대한 정확한 소루션 코스트들을 저장한다.
blanks).
The database is constructed by searching backwards from the goal state and recording the cost of each new pattern
데이터베이스는 골스테이트로 부터의 searching backwards와 각각 새로운 pattern encountered의 코스트의 레코딩에의해 구축이 된다.
encountered.
We could construct databases for 5-6-7-8, 2-4-6-8, and so on.
우리는 5-6-7-8, 2-4-6-8 등등으로 데이터 베이스를 만들수가 있다.
These heuristics can be combined by taking the maximum value.
이들 휴리스틱은 최대의 값을 combine 할 수 있다.
The number of nodes generated can be reduced by a factor of 1,000 when solving random 15-puzzles compared with
노드의 갯수는  15-puzzle 문제에서는 1000개의 팩터정도를 제거 할 수 있다. 이것은 맨하탄 디스턴스를 쓸때 비해서 이다. 패턴 데이터 베이스를 쓸때이다.
using Manhattan distance.


Disjoint pattern databases:
패턴 데이터 베이스 분리

Example:
예를 들어서
Construct 1-2-3-4 database and the 5-6-7-8 database.
1-2-3-4 데이터 베이스와 5-6-7-8 데이터베이스를 구축한다.
Record not the total cost of solving the subproblem 1-2-3-4 (5-6-7-8) but just the number of moves involving 1-2-3-4
(5-6-7-8).
subproblem을 solving한 코스트의 총합을 기록하는것이 아니지만 subproblem의 move의 수를 기록한다.
Use the sum of the two costs → still admissible
두개의 코스트의 합을 더해도 아직 admissible 하다.
The number of nodes generated can be reduced by a factor of 10,000when solving random 15-puzzles.
15-puzzle에서 10000개 팩터를 제거, 등 스피드 업이 있다.
A speedup of 1,000,000for 24-puzzles.
==========================================================================================================================
Learning Heuristics from Experience
경험에서 오는 러닝 휴리스틱
Optimal solutions to an 8-puzzle provide examples from which h(n)can be learned.
8-puzzle에 옵티말 솔루션은 h(n)이 배울수 있는데서 오는 예제를 제공한다.

State is described by a set of features
state는 튿징들에 의해서 설명될 수 있는데.
x1(n): # of misplaced tiles
x1(n)은 잘못배치된 타일들이다
x2(n): # of pairs of adjacent tiles also adjacent in the goal state
x2는 adjacent된 타일쌍들의 갯수이고 또한 골스테이트에 근접한것도 된다.
Then, derive a linear combination (find best fitting ci’s)
그러면 선형 조합에서
h(n) = c1x1(n) + c2x2(n)
위와 같은 식을 얻게 되는것이다.
------------------------------------------------------------------------------------------------정말애매하군.

Local search algorithm

In many problems, the path to the goal is irrelevant.
많은 문제들에서 골까지의 path는 irrelevant 하다.
Example: 8-queens problem
예를들어 8-queens problem이 있다.
Order of adding queens is irrelevant
queen을 추가하는 순서는 관계가 없다.

Neighborhood search:
이웃 서치
Local search algorithms operate using a single current state and move only to its neighbors.
local search 알고리은 single current state을 사용하고 오직 자신의 이웃에 이동할 때만 동작하게 되된다.
여기서 state란 바로 어떤 문제를 해결하기 위해서 진행이 될때 그상태 어떻게 진행 되었는지 상태 뭐이런것들이다.
Start with a complete configuration and make modifications to improve its quality
완벽한 설정과함께 시작하고 퀄러티를 향상시키기 위해서 변경을 한다.

Useful for solving optimization problems:
Find the best state according to the objective function.
목표하는 함수를 위한 가장 좋은 state를 찾는다.


Local search algorithm의 예를 보자 이것의 neighborhood configuration의 후보자들을 보면 서로 인접해있는 것들끼리 바꾸는것을 알수있다. 한번에 하나씩! 이제 이런느낌의 알고리즘을 보게 될것이다 그것이 바로 Hill-climbing search이다.

State space landscape
Location: state
기로 : 스테이트 스페이스
Elevation: heuristic cost function or objective function
세로 : 휴리스틱 혹은 오브젝티브 펑션,
어떤 스테이트에서의 휴리스틱펑션값이나 오브젝티브 펑션값이 높으면 높을 수록 좋다.



이런게 노올 수가 있다. 어떤 스테트에서 가장 높은 값을가지는 objective function값을 가지는것을 찾는 것이 궁국적인 목표이다. 하지만 그것은 힘들고 local maximum이라도 잘찾으면 나름 성공적인 서치가 될 것이다.

Hill-climbing Search
Also called as greedy local search:
그리디 로컬 서치라고도 불리는데 그러는걸 보면 로컬 서치 알고리즘이기는 한가 보다.
Continually moves in the direction of increasing value
계속적으로 값이 오르는쪽으로 이동을 하게 된다. 그래서 언덕을 오르는 서치라는 이름이 붙은것이다. 수도코드를 보면

function Hill-Climbing(problem) returnsa state that is a local maximum //로컬 맥시멈인 스테이트를 리턴하게 된다.
inputs: problem, a problem//인풋으로는 문제가 들어가고
local variables: current, a node//local variable로서 현재노드와

이 포스팅은 부산대학교 정보컴퓨터 공학부의 인공지능 수업을 들은 학생이 수업을 듣고 문서를 참고해 만든 포스팅으로 절대 이 내용이 정답이라고 보장 할 수는 없다.
================================================================================================================
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로 구현이 된다.

 위의 말이 무엇인지 모르겠다면 그림으로 한방에!

한번에 이해가 가지 않는가?
그러면 이제 앞으로의 알고리즘은 문제에 의해서 한번 풀어 볼 수 있도록 하자.