연구

인공지능 - 탐색

다음의 그래프를 가지고 각각의 경우에 대하여 목적지까지의 최단거리(가능하다면)를 구하시오.

시작점 : A, 도착점 : E


1. DFS (Depth First Search)


DFS이므로 노드간의 가중치는 생각하지 않는다. 알파벳 순서로 탐색한다고 정하면 제일 먼저 A의 자식노드인 B를 탐색하고, 다음에 B의 자식노드인 C를 탐색하고, C의 자식노드인 D를 탐색하고, D의 자식노드인 E를 탐색함으로써 TSP를 마친다.
A → B → C → D → E


2. BFS (Breadth First Search)


BFS이므로 노드간의 가중치는 생각하지 않는다. 알파벳 순서로 탐색한다고 정하면 A에서 B를 탐색하고, 다시 A의 자식노드인 C를 탐색하고, 차례대로 D, E 순으로 탐색한다.
A → B → C → D → E


3. Hill Climbing

<그림1> f = h*


<그림1>에서 A 노드에서 시작한 후 AB, AC, AD, AE 노드중 평가함수 값이 가장 작은 AC로 간다. 다음에 AC의 자식노드 ACB, ACD, ACE 노드중 평가함수 값이 가장 작은 노드가 2개가 있으므로 알파벳 순으로 ACD 노드로 간다. ACD 노드의 자식노드중 평가함수 값이 작은 노드가 2개 있으므로 역시 알파벳 순으로 ACDB 노드로 간다. ACDB 노드의 자식노드인 ACDBE로 이동하면서 TSP를 마친다.
A → AC → ACD → ACDB → ACDBE


4. BFS (Best First Search)

<그림1>에서

① OPEN = {A/35}; CLOSED = {}
  - 노드 A가 시작노드
② OPEN = {AC/20, AD/21, AB/27}; CLOSED = {A/35}
  - 평가함수 값이 가장 낮은 노드가 OPEN의 가장 왼쪽에 오고 다음 방문 노드가 된다.
③ OPEN = {ACD/16, ACB/20, AD/21, AB/27}; CLOSED = {AC/20, A/35}
④ OPEN = {ACDB/10, ACB/20, AD/21, AB/27}; CLOSED = {ACD/16, AC/20, A/35}
⑤ OPEN = {ACDBE/0, ACB/20, AD/21, AB/27}; CLOSED = {ACDB/10, ACD/16, AC/20, A/35}
⑥ OPEN = {ACB/20, AD/21, AB/27}; CLOSED = {ACDBE/0, ACDB/10, ACD/16, AC/20, A/35}
A → AC → ACD → ACDB → ACDBE


5. A*


<그림 2> f = g + h*


<그림2>에서

① OPEN = {A/35}; CLOSED = {}
  - 노드 A가 시작노드
② OPEN = {AC/26, AD/30, AB/35, AE/36}
 CLOSED = {A/35}
  - 평가함수 값이 가장 낮은 노드가 OPEN의 가장 왼쪽에 오고 다음 방문 노드가 된다.
③ OPEN = {ACD/27, ACE/30, AD/30, ACB/33, AB/35, AE/36}
 CLOSED = {AC/26, A/35}
④ OPEN = {ACDE/27, ACDB/31, ACE/30, AD/30, ACB/33, AB/35, AE/36}
 CLOSED = {ACD/27, AC/26, A/35}
⑤ OPEN = {ACDEB/27, ACDB/31, ACE/30, AD/30, ACB/33, AB/35, AE/36}
 CLOSED = {ACDE/27, ACD/27, AC/26, A/35}
⑥ OPEN = {ACDB/31, ACE/30, AD/30, ACB/33, AB/35, AE/36}
 CLOSED = {ACDEB/27, ACDB/31, ACD/27, AC/26, A/35}

A → AC → ACD → ACDB → ACDEB
 




이올린에 북마크하기(0) 이올린에 추천하기(0)
top


http://www.joon.pe.kr/blog/trackback/148


<< Prev   1   ... 193   194   195   196   197   198   199   200   201   ... 336   Next >>