기본 검색 방식: 반복적으로 깊게 내려가는 검색방식

Basic Search Method: Iterative Deepening Search

 

반복 검색 설명

함수 & 그림

LISP 코드 예제

검색 비교

자료

 

반복적으로 깊게 내려가는 방식에 대한 설명

Iterative Deepening Search라고 불리우는 이 방식은 반복적으로 계속 한단계씩 내려가면서 답을 찾는 방식입니다. 이 방식은 기본적인 Breadth-first Search 와 Depth-first Search의 좋은점을 결합한 것이지요. 이 방식은 답을 찾는면에 의해서 완벽하고 최상의 답을 찾을수 있습니다. 여기서 완벽하다는 뜻은 여기에 검색 하는곳을 완벽하게 다 검사해보는것이고. 그 중에서 여러게의 답이 있을때, 최상의 답을 구할수 있다는 것 입니다. 반복적으로 내려 간다는 의미는 검색 장소에 있어서, 검색 했던 곳을 또 한다는 뜻이 있습니다. 검색 했던 곳을 또 하면서 내려가면 시간이 소비가 많이 될텐데, 검색하는 장소는 깊이 내려 가면서 많은 곳을 검색해야 하는 시간때문에 실제 시간은 Breadth-First와 같이 나옵니다.

일반적으로, 이 검색 방법은 검색 장소가 넓고 깊이가 알려져 있지 않을때 사용될수 있는 검색 방법으로 쓰여집니다.

 

Function 과 그림의 예제

function Iterative-Deepening-Search(problem) returns a solution sequence
   inputs: problem, a problem
   for depth ←0 to ∽ do
      if depth-limited-search(problem, depth) succeeds then return its result
   end
   return failure

Iterative Deepening Search excerpted from AIMA

위에 있는 함수는 Depth-Limited-Search를 사용하는 것입니다. 다만 여기서 깊이의 한계를 무한으로 바꾸는 것입니다. 무한 = ∽

그림의 예제는 한단계씩 내려 가면서 쓰여진것입니다. 여기서는 2개씩 나누어 지는 방식을 사용했습니다. (사용에 따라서 이것보다 더 많이 나누어 질수도 있습니다.)
깊이가 0일때는 제일 위에것을 검색합니다.
깊이가 1일때는 제일 위에것과 밑에 2개를 검색합니다.
깊이가 2일때는 제일 위에것과 밑에 2개를 다시 검색하고 그 밑어것을 검색합니다.
깊이가 3일때는 깊이가 2일때검색한것을 다시 검색하고 그 다음 것을 검색합니다.
이렇게 앞에 검색한것을 다시 반복으로 검색하는것이 Iterative Deepening Search 입니다. 아래의 코드를 사용해보십시요.

 

이 코드는 제가 여기에 대한 예제를 lisp으로 만든것입니다. Common-lisp 으로 위에서 부터 하나씩 Evaluate해 나가시면서 사용할수 있습니다. Iterative deepening search와 Common-lisp이 주는 것과 비교할수 있도록 만들었습니다.
(C) Copyright to Kee Dae Nam, All Rights Reserved.

(DEFUN ITERATIVE-DEEPENING (FIND-THIS FROM-HERE)
"Finds the value of FIND-THIS from FROM-HERE, for the sake of this program
FIND-THIS is a symbol (x, k, b) and FROM-HERE is a list where symbols are in"
(IF (AND (SYMBOLP FIND-THIS) (LISTP FROM-HERE)) ; CHECK TO SEE IF THE VALUES ARE VALID
(LOOP FOR Y = 0 THEN (+ Y 1)
DO (PROGN
(SETF RESULT (DEPTH-LIMITED-SEARCH FIND-THIS FROM-HERE Y))
(IF (OR (EQUAL 'END RESULT) RESULT)
(RETURN 'DONE))))
(PROGN
(FORMAT T "Values are not entered correctly, SYMBOL and LIST is required for argument")
NIL))) ; END OF IF-ELSE -> RETURN STRING WITH NIL

(DEFUN DEPTH-LIMITED-SEARCH (FIND-THIS FROM-HERE DEPTH)
"Depth limites search method returns 'END when the end of the list is reached
or returns T when a solution is found and also prints where the solution is found."
(SETF ITEMS 0)
(LOOP FOR K FROM DEPTH DOWNTO 0
DO (SETF ITEMS (+ ITEMS (EXPT 2 (- DEPTH K)))))
(LOOP FOR X FROM 0 TO ITEMS
DO (IF (>= X (LENGTH FROM-HERE))
(PROGN
(FORMAT T "~&Solution cannot be found")
(RETURN 'END))
(IF (EQUAL FIND-THIS (NTH X FROM-HERE))
(PROGN
(FORMAT T "~&Solution is found at ~D." X)
(RETURN T))))))


;SETTING
(setf test-list (make-list 1000 :initial-element 'a))
(setf (nth 0 test-list) 'b)
(setf (nth 999 test-list) 'k)
(setf (nth (random (length test-list)) test-list) 'x)

; TESTING
(time (position 'b test-list))
(time (position 'x test-list))
(time (position 'k test-list))
; 'z is not in the list, the program should return nil
(time (position 'z test-list))

; testing iterative-deepening function

; BEST CASE
(time (iterative-deepening 'b test-list))
; AVERAGE
(time (iterative-deepening 'x test-list))
; WORST CASE
(time (iterative-deepening 'k test-list))
; WORST CAST TOO
(time (iterative-deepening 'z test-list))

 

다른 검색 방법들과 비교

Criterion

Breadth-First

Uniform-Cost

Depth First

Depth-Limited

Iterative Deepening

Bidirectional (if applicable)

Time(시간)
Space(공간)
Optimal?(최상적인 답)
Complete?(완벽하게 다 검색)

bd
bd

YES

YES

bd
bd

YES

YES

bm
bm

NO

NO

bl
bl

NO

YES, if l ≥ d

bd
bd

YES

YES

bd/2
bd/2

YES

YES

여기서의 b는 나누어지는 가지 수. (branching factor)
d 는 깊이 입니다. (depth)
m 는 최대 깊이입니다. (maximum depth)
l 은 깊이의 한계입니다. (depth limit)

이 자료는 Artificial Intelligence, A Modern Approach에서 공부한 내용중의 하나를 한글로 쓴것입니다. 참고로 figure 3.16 그림은 책 79쪽에서 복사한 내용입니다. 그리고 코드 예제는 제가 이부분을 다른 분들에게 설명하기 위해 만든 예제입니다.

여기에 대한 질문이 있으시면 kee@unforgettable.com 으로 메일주시면 답변드리겠습니다.