'tree search'에 해당되는 글 1건

### 최적의 거리 찾기

도시를 다들리는 최적의 방법을 찾는법은

수많은 경를 다구해 최단 거리를 산출하는 방법

### 순서도 

1. Initial state

   목적

2. Possible actions

   가능한 방한들

3. Goal test

   목적에 도착 했는가

4. Path cost

   Step cost (x, a , y) ≥ 0: 방법은 0보다 크거나 같다

   비용 정리

### 추상화 방법

원래 문제를 추상화를 통하여 간단하게 혹은 쉽게 이해하게 만든다

### tree search(트리 서치)

이동의 경우의수를 트리구조로 만든것

액션이 가능한 경우에 수를 나열하여 다음갈 곳도 나열을 한다

### 전략

1. Completeness: 해를 찾을 수 있다 라는 목적

2. Time complexity : 시간이 얼마나 걸릴지

3. Space complexity: 총 매모리 필요량

4. Optimality : 항상 최적의 솔루션이 있나?

### Uninformed search

1. Breadth-first search : 너비 우선 

2. Uniform-cost search

3. Depth-first search : 깊이 우선 

4. Depth-limited search

5. Iteratibe deepening search

@@ 너비 우선 탐색 (Breadth-First search)

FiFO(first in first out) 

fringe(아직 펼쳐지지않은 로드)

     A  

  B      C

D  E  F  G

시작 

A    --> a갈 수 있는곳 BC 

BC ---> b 갈 수있는곳 DE

CDE ---> c 갈 수 있는곳 FG

DEFG ---> d 갈 수 있는곳 ......

이런식으로 메모리를 최대한 절약하여 찾는 방법

@@ 깊이 우선 탐색(Depth-First search)
LIFO = Last in frist out

     A 

  B      C

D  E  F  G

시작 

A    --> a갈 수 있는곳 BC 

BC ---> b 갈 수있는곳 DE

DEC ---> d 갈 수 있는곳 HI

HIEC ---> H 갈 수 있는곳 없을시 없엠

IEC ---> I 갈 수 있는곳 ....

끝 까지 가보는 것 이다

그렇게 메모리를 줄여 서치를 한다