[알고리즘🔑] Iterative deepening Search와 Iterative lengthening Search

---

들어가기 앞서

• BFS/DFS 에 대해 숙지하셔야 합니다.
• Blind Search 의 기본 원리를 알고 계셔야 합니다.

---

---

Iterative Deepening Search란 

iterative : 반복적인

즉, 한국 말로 '번역하자면 반복적인 깊이 탐색' 정도가 되겠네요.

DFS 와, BFS 의 단점들을 보완하기 위해 고안된 search 방법입니다!

그러면 어떤 점들을 보완시켰는지 알기 전에, 먼저 DFS와 BFS의 특징들을 간단하게 알아볼까요?

 

---

 

DFS의 특징

 

DFS (출처 : aistudy.com)

 

장점 :

BFS 에 비해 메모리 소요가 적다. (BFS는 frontier 큐에 하위 노드들 전부 넣어야함)

목표해가 깊은 단계에 있을 경우, BFS 보다 훨씬 빠르다.

 

단점 :

DFS 는 탐색트리에서 깊이가 아주 큰, 하지만 해가 해당 깊이에 없는 경우를 만나게 되면, 깊이 빠져들어갈 수 있다. 이렇게 들어가다가 메모리에 문제가 생길 수도 있고, 해를 찾게되더라해도 깊은 깊이의 해를 구하게 되므로 Optimal 한 해가 아니다. 

 

---

BFS의 특징

 

BFS (출처 : aistudy.com)

 

장점 :

모든 노드들을 깊이순으로 차례대로 다 확인해보기 때문에 Optimal 합니다.

 

단점 : 

DFS 에 비해 평균 메모리 소요가 매우 큽니다.

 

 

---

Depth-Limited Search

DFS 의 단점을 보완하기 위해 나온 것이 Depth-Limited Search입니다.

DFS 와 기본 작동방식은 같지만, 깊이를 끝까지 들어가지 않고 한계 깊이를 정해 그 깊이 이상은 탐색하지않고 Cutoff해 옆 노드로 넘어가는 방식입니다. 

하지만 한계깊이 이상의 노드들은 탐색하지 못해 Optimal하지 못하다는 단점이 있습니다.

 

---

Iterative Deepening Search 작동방식

iterative deepening Search 는 Depth-Limited Search 의 작동 방식을 기본으로 합니다.

하지만 Depth-Limited 의 한계 깊이를 1, 2, 3, 4 .... 이렇게 차례대로 늘려가며 iterative 하게 반복실행합니다.

 

 

Iterative deepening Search 의 의의 

 

• 깊이를 1개씩 늘려가며 탐색하게되므로 Optimal한 해를 구할 수 있습니다.

• 기본 작동방식이 DFS이므로 memory 측면에서 DFS 의 이점을 그대로 가져옵니다.

 

---

Iterative lengthening Search

iterative lengthening search 는 iterative deepening search 와 작동방식이 매우 비슷합니다.

일반적으로 search 알고리즘을 적용할 문제들은, 단순한 엣지가 아니라 weight (path-cost) 가 설정되어 있습니다!

그런 문제에 대해서 iterative deepening search 처럼 단순히 깊이만 가지고 prunning 하는것은 비효율 적입니다.

그러므로 iterative iengthening search 는 iterative deepening search 과 같은 작동방식이지만, 한계 깊이에 대해 iterative 하게 돌지 않고, 한계 path-cost를 설정한 뒤, 한계 path-cost를 높여가며 iterative 하게 돕니다. 

 

예시)

 

iterative deepening search : 

한계 깊이 1.

-> 해못찾음 

-> 한계깊이 2.

-> 해못찾음

-> 한계깊이 3.

-> 해찾음. 

종료. (깊이 3의 최적해 반환)

 

iterative lengthening search :   * 첫 한계 path-cost 5로 설정. / 5씩 늘려주기로 설정. 

한계 path-cost 5.

-> 해못찾음 

-> 한계 path-cost 10.

-> 해못찾음

-> 한계 path-cost 15.

-> 해찾음. 

종료. (cost 10~ 15 사이의 최적해 반환)