Ž»ö°ú Á¦¾îÀü·«
ÀΰøÁö´É °³·Ð : Dan W. Patterson Àú¼, ±è¿µ·Ä.±è¿ì¼º.±èÁ¤±Ô.¹Ú¿ë¹ý.Á¤¸ñµ¿ ¿Å±è, Áö¼ºÃâÆÇ»ç, 1995 (¿ø¼ : Introduction to Artificial Intelligence and Expert Systems, 1990)
1. ¼Ò°³
2. ¼·Ð °³³ä (preliminary concepts)
3. Ž»ö ¹®Á¦µéÀÇ ¿¹
4. ¹«Á¤º¸ ¶Ç´Â ºí¶óÀεå Ž»ö (Uninformed or Blind Search)
³ªºñ¿ì¼± Ž»ö (Breadth-First Search)
±íÀ̿켱 Ž»ö (Depth-first search)
±íÀ̿켱 ¹Ýº¹ ½ÉÈ Å½»ö (Depth-first Iterative Deepening search)
¾ç¹æÇâ Ž»ö (Bidirectional Search)
5. Á¤º¸°¡ Àִ Ž»ö (Informed Search)
°æÇèÀû Á¤º¸ (Heuristic Information)
¾ð´ö ¿À¸£±â Ž»ö (Hill Climbing Methods)
ÃÖÀû¿ì¼± Ž»ö (Best-first Search)
ºÐ±â¿Í ÇÑÁ¤Å½»ö (Branch-and-Ground Search)
ÃÖÀû Ž»ö°ú A* (Optimal Search and A*)
¹Ýº¹ ½ÉÈ A* (Iterative Deepening A*)
6. AND-OR ±×·¡ÇÁ Ž»ö (Searching AND-OR Graphs)
7. ¿ä¾à
BFS ¹æ¹ýÀº ´ÙÀ½ ·¹º§ÀÇ ³ëµå¸¦ Á¶»çÇϱ⠾ռ Æ®¸®ÀÇ °°Àº ·¹º§ÀÌ ÀÖ´Â ·¹º§ÀÇ ³ëµå¸¦ ¸ÕÀú Á¶»çÇÏ´Â ¹æ¹ýÀÌ´Ù. À̰ÍÀº ÀÚ½ÄÀÇ ÀڽĵéÀÌ °í·ÁµÇ±â Àü¿¡ Çö ³ëµåÀÇ ¹Ù·Î ¹Ø¿¡ ÀÖ´Â ÀÚ½Ä ³ëµå°¡ Á¶»çµÈ´Ù´Â °ÍÀ» ÀǹÌÇÑ´Ù.
BFS ¸¦ ´ÙÀ½±×¸²¿¡ ³ªÅ¸³½´Ù. ±×°ÍÀº Ç×»ó ¸¸ÀÏ ÃÖ¼Ò±æÀÌÀÇ ±æÀ̰¡ Á¸ÀçÇÏ¸é ±×°ÍÀ» ã´Â ÀåÁ¡ÀÌ ÀÖ´Ù. ±×·¯³ª ¸¸ÀÏ Æ®¸®°¡ ²Ë Â÷ÀÖ´Ù¸é ÇØ´äÀÌ ¹ß°ßµÇ±â Àü±îÁö ¸¹Àº ³ëµå¸¦ Á¶»çÇØ¾ß ÇÒ Çʿ䰡 ÀÖ´Ù. BFS ¾Ë°í¸®ÁòÀº ¸Å¿ì ´Ü¼øÇÏ´Ù. ±×°ÍÀº Á¶»çµÇÁö ¾ÊÀº ³ëµåµéÀ» Á¦¿ÜÇÑ ¸ðµç »ý¼ºµÈ ³ëµå¸¦ ÀúÀåÇϱâ À§ÇØ ³ëµå±¸Á¶¸¦ »ç¿ëÇÑ´Ù. ³ëµåÀÇ Á¦°Å³ª Á¶»ç¸¦ ÇϱâÀ§ÇØ ³ëµåµéÀÌ À§Ä¡ÇØ ÀÖ´Â ¼ø¼´Â Ž»öÀÇ ÇüŸ¦ °áÁ¤ÇÑ´Ù. BFS ¾Ë°í¸®ÁòÀº ´ÙÀ½°ú °°´Ù.
Breadth First Search
BFSÀÇ
½Ã°£ º¹Àâµµ´Â ÀÌ´Ù. À̰ÍÀº ¸ñÇ¥ ±íÀÌ
±îÁöÀÇ ¸ðµç ³ëµå°¡ »ý¼ºµÊÀ» ÁÖ¸ñÇÏ¸é ¾Ë ¼ö ÀÖ´Ù. ±×·¯¹Ç·Î »ý¼ºµÇ´Â ³ëµå ¼ö´Â
, Áï
ÀÓÀ» ¾Ë ¼ö ÀÖ´Ù. °ø°£ º¹Àâµµ´Â ¿ª½Ã
ÀÌ´Ù. ¿Ö³ÄÇϸé ÁÖ¾îÁø ±íÀÌÀÇ ¸ðµç ³ëµåµéÀº ´ÙÀ½ ±íÀÌÀÇ ¸ðµç ³ëµåµéÀ» »ý¼ºÇϱâ
À§ÇØ ÀúÀåµÇ¾ß¸¸ ÇÑ´Ù. Áï ±íÀÌ
ÀÎ
³ëµåµéÀÌ ±íÀÌ
ÀÇ ³ëµå¸¦ »ý¼ºÇϱâ À§ÇØ ÀúÀåµÇ¾ß¸¸ ÇÑ´Ù. °á±¹ °ø°£ º¹Àâµµ´Â
°¡ µÈ´Ù. ÀÌ·¯ÇÑ Áö¼ö ÇÔ¼öÀûÀÎ ½Ã°£ °ø°£ Ư¼ºÀÌ BFS À» Àß Àû¿ëÇÏÁö ¸øÇÏ°Ô ÇÏ´Â ÀÌÀ¯ÁßÀÇ ÇϳªÀÌ´Ù.
DFSÀº °¡´ÉÇÑ
»¡¸® Ž»ö Æ®¸®¼ÓÀ¸·Î µé¾î°¡¼ ¼öÇàµÈ´Ù. À̰ÍÀº ÃÖ±Ù¿¡ È®ÀåµÈ ³ëµåÀÇ ÀÚ³ëµå(chidren
node)¸¦ »ý¼ºÇÔÀ¸·Î½á °¡´ÉÇÏ´Ù. ´ÙÀ½¿¡ ÀÚ³ëµå(children node)ÀÇ ÀÚ³ëµå¸¦ »ý¼ºÇÏ¿©
¸ñÇ¥°¡ ¹ß°ßµÇ±â±îÁö ȤÀº ÀÓ°è ±íÀÌ(cutoff depth) d¿¡ À̸¦ ¶§±îÁö ¹Ýº¹µÈ´Ù. ÀÙ³ëµå(leaf
node)¿¡ À̸¦ ¶§ ±îÁö ¶Ç´Â ÀÓ°èÁ¡(cutoff point)¿¡¼ ¸ñÇ¥°¡ ¹ß°ßµÇÁö ¾ÊÀ¸¸é ÇÁ·Î±×·¥Àº
ÃÖ±Ù¿¡ È®ÀåµÈ ³ëµå·Î ¿ªÇà(back tracking)ÇÏ¿© ±× ³ëµåÀÇ ´Ù¸¥ ÀÚ³ëµå ¸¦ »ý¼ºÇÑ´Ù. ÀÌ °úÁ¤Àº ¸ñÇ¥°¡ ¹ß°ßµÇ±â±îÁö ȤÀº ½ÇÆÐÇÏ°Ô µÉ ¶§±îÁö °è¼ÓµÈ´Ù.
DFS¾Ë°í¸®ÁòÀº Queue
¿¡ À§Ä¡ÇÏ´Â ³ëµåÀÇ ¼ø¼¸¦ Á¦¿ÜÇϰí´Â
breadth-first search °ú µ¿ÀÏÇÏ´Ù. DFSÀº »õ·Î »ý¼ºµÈ ÀÚ½ÄÀ» Queue ÀÇ ¾Õ¿¡ À§Ä¡½ÃÄÑ ±×°ÍµéÀÌ ¸ÕÀú ¼±Åõǵµ·Ï
ÇÑ´Ù.
Ž»ö°úÁ¤Àº ´ÙÀ½°ú °°´Ù.
DFS˼
Ž»ö Æ®¸®°¡ ¸Å¿ì ¸¹Àº ¸ñÇ¥¸¦ °®°í ÀÖ´Â °æ¿ì¿¡ breadth-first search
º¸´Ù ´õ ¼±È£µÈ´Ù. ±×·¸Áö ¾ÊÀ¸¸é ±íÀÌ ¿ì¼± Ž»öÀº ÇØ´äÀ» ¹ß°ßÇÏÁö ¸øÇÒ ¼öµµ ÀÖ´Ù.
±íÀÌ ÀÓ°è°ª(depth cutoff) ¿ª½Ã ¸î°¡Áö ¹®Á¦¸¦ ¾ß±â½ÃŲ´Ù. ¸¸¾à ÀÓ°è°ªÀÌ ³Ê¹«
¾èÀ¸¸é ¸ñÇ¥¸¦ ãÁö ¸øÇÒ ¼ö ÀÖ°í, ÀÓ°è°ªÀÌ ³Ê¹« ±íÀ¸¸é Ãß°¡ÀûÀÎ °è»êÀÌ ÇÊ¿äÇϰÔ
µÈ´Ù.
DFS ÀÇ ½Ã°£ º¹Àâµµ(time
complexity)´Â breadth-first search ÀÇ º¹Àâµµ Áï ¿Í °°´Ù. Ãʱ⠽ÃÀÛ ³ëµå·ÎºÎÅÍ ÇöÀç ³ëµå·ÎÀÇ path ¸¸ ÀúÀåµÇ±â ¶§¹®¿¡ °ø°£Àº
´ú Â÷ÁöÇÏ°Ô µÈ´Ù. ±×·¯¹Ç·Î ¸¸ÀÏ ±íÀÌ ÀÓ°è°ª(depth cutoff)ÀÌ
À̸é, °ø°£ º¹Àâµµ´Â
ÀÌ´Ù.