±âº» °Ë»ö ¹æ½Ä: ¹Ýº¹ÀûÀ¸·Î ±í°Ô ³»·Á°¡´Â °Ë»ö¹æ½Ä

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
b
d


YES

YES

bd
b
d


YES

YES

bm
bm


NO

NO

bl
bl


NO

YES, if
l ¡Ã d

bd
bd


YES

YES

bd/2
b
d/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 À¸·Î ¸ÞÀÏÁÖ½Ã¸é ´äº¯µå¸®°Ú½À´Ï´Ù.