대표적인 그래프 탐색(BFS - UCS, DFS - IDS)과 각 탐색에 대한 평가

평가 기준

1. Completness (완전성) : 출발에서 목표까지 항상 가는가

2. Optimal(최적) : 최적이냐 항상 최소 비용을 보장하는가?

3. Time Complexity : 시간 복잡도, 노드의 개수가 몇개나 생성되는가?

4. Space Complexity : 탐색 시 사용하는 메모리 (몇개의 노드나 메모리에 들고 있는가?)

탐색 방법

BFS : 너비 우선 탐색, 선입선출인 큐를 써서 구현한다.  =>> IDS 너비 우선이지만 제한을 두고 찾는 것

- BFS의 평가 척도 ,
  -  완전성 - 노드의 수가 유한하기 때문에 완전하다. 하나의 너비에 무한개가 있는 것은 너무 극단적이므로 예외
   - 최적 - 최적이다. 무조건 하나의 너비에 대해서 다 찾기 때문에 최적을 찾는다. DFS는 깊이가 우선이므로 최적은 아니다.
  - 시간 복잡도 - O(b^d )  *b가 매 상태, d가 깊이. 

UCS : BFS의 확장 버전,  다익스트라

- Uniform cost search 즉 단일 비용 서치이다. BFS나 DFS는 노드가 어디로 가는지를 고려하지만 유니폼 코스트 탐색은 해당 노드까지 얼마나 비용이 드는지를 찾는다. 큐에서 코스트를 서칭해서 집어 넣고 사용하게 된다. 다른 말로는 Digkstra's 다익스트라의 최단 경로 알고리즘 이라고도 한다.

- BFS의 과정에서 만약 비용이 덜 드는게 있다면 업데이트 하는 로직이 중간에 추가 (더 짧은 길이 나온다면 그것으로 새로 업데이트) 항상 우선큐에서 비용을 보고 분기처리를 해서 최소 비용인 명령을 수행시킨다.

-BFS와의 또 하나의 차이점은 골 테스트 시점이다.  BFS는 마지막이 GOAL이면 그 상태를 저장하지 않고 끝내면 되지만 UCS는 GOAL을 체크하는 것이 기계적으로 하면 안되고 항상 시작시에 비용을 고려해야 하기 때문에 끝날 경우에는 GOAL까지 다 저장하고 시작시에 검사를 하는 식으로 로직을 짠다. 

- 완전성 : O (스탭 비용이 작은 양수라면, 코스트가 음수면 찾긴 하지만 최적성은 없다.)

- 최적 : 최적이다.

- 시간 공간 복잡도는 아래 링크 참고 (기본적으로 같으나 비용에 따라  달라짐)

https://magician-of-c.tistory.com/35

Search Algorithm [3]. 균일 비용 탐색 (Uniform Cost Search : UCS)

DFS : 깊이 우선 탐색 (Depth-first-search) 

- LIFO 큐를 사용, 가장 깊은 노드를 우선적으로 탐색한다.

- 완전성 : 완전하지 않다. 유한한 공간과 깊이가 필요하다.

- 시간복잡도 : 최대 깊이를 m이라고 할 경우 O(b^m) 이다. 깊이가 크면 더 BFS보다 더 나쁘지만 그렇지 않다면 더 좋다.

- 공간 복잡도 : 탐색 시에는 해당 깊이에 대한 내용만 들고 있으면 된다.

DLS : DLS 깊이 우선이지만 제한을 두고 찾는 것.

-  그냥 DFS에서 레벨을 지정해두고 그 안에서 찾는다.

- 깊이의 리밋을 거는 느낌, 중간에 cutoff를 만들어서 탐색 전에 그냥 몇단계 까지만 진행하도록 한다.

- 완전성 : 유한하므로 당연히 O

-시간 복잡도 : O(b^d) *여기서 d는 레벨 , bfs 보다는 조금 더 많은 노드가 생성

- 공간 복잡도 : O(bd)

- 최적화 : 스텝 코스트가 1이라면 최적의 경로를 찾게 된다.

* Bidirectional Search : 시작점과 도착점 양쪽에서 서치하기 시작, 양쪽 다 BFS를 사용할 경우에는 완전성과 최적성이 보장되며 문제는 많은 공간 복잡도 이다. O(b^(d/2))