'체험 인공지능'을 읽다 .
아래는 책 중에서 발췌한 탐색 알고리즘 관련 내용들.
--------------------------------------------------------
- DFS(Depth-First Search)와 BFS(Breath-First Searce)의 차이는
사용하는 자료구조가 'Stack(스택: LIFO-Last In First Out)'이냐 'Queue(큐: FIFO-First In First Out)'냐 하는 점.

16/8/17 수

- A* 알고리즘 의사 코드:

OpenList: 아직 조사하지 않은 노드, 즉 앞으로 조사할 노드들을 담은 리스트.
ClosedList: 이미 조사한 노드들을 담은 리스트.

1) 시작노드를 OpenList에 넣는다.(처음 시작시 탐색한 노드가 없으므로 ClosedList는 비어있고 OpenList는 처음 위치(시작노드)만 갖고 있다)

2) 반복
a) OpenList에서 최저값(f값)을 가진 노드 n을 제거하고 n을 ClosedList에 추가. (노드 n은 이미 방문한 셈이므로 ClosedList에 넣는다.
f(n) = g(n) + h(n)이다.
g(n): 시작노드에서 노드 n까지의 실제 cost 정보,
h(n): 노드 n에서 목표노드까지의 최소 cost의 휴리스틱-추정치heuristic.
이 단계에서 heuristics를 사용하게 된다)

b) n의 인접노드들 중에서
* 만약 그 인접노드가 이미 ClosedList에 있으면 무시
(ClosedList에 있는 노드는 이미 탐색한 것이므로 무시한다)
* 그렇지 않다면 OpenList에 추가
(이미 OpenList에 있다면 g값이 작은 노드로 대체. 탐색되지 않은 곳이라면 OpenList에 넣고 이미 OpenList에 있는 노드일 땐 그 위치를 통하는 새로운 경로가 이전보다 g(n)값이 작으면 그 노드의 정보를 갱신해 준다)
* n을 이 노드의 부모로 저장.
(목표노드에 도착한 뒤 경로를 역추적 하려면 부모노드를 저장해야 한다)

C) 다음 조건을 만족하면 정지.
* 목표노드에 도착하거나
* 목표노드는 아니지만 OpenList가 비어있으면

3) 목표노드에서 역으로 부모를 따라서 시작노드로 탐색(이 경로가 찾고자 했던 경로)