ÈÞ¸®½ºÆ½ Ž»ö
(Heuristic Search)
ÀΰøÁö´É-Áö´ÉÇü ¿¡ÀÌÀüÆ®¸¦ Áß½ÉÀ¸·Î : Nils J.Nilsson Àú¼, ÃÖÁß¹Î. ±èÁØÅÂ. ½É±¤¼·. À庴Ź °ø¿ª, »çÀÌÅØ¹Ìµð¾î, 2000 (¿ø¼ : Artificial Intelligence : A New Synthesis 1998), Page 145~167
Æò°¡ ÇÔ¼öÀÇ »ç¿ë (Using Evaluation Function)
ÀϹÝÀûÀÎ ±×·¡ÇÁ Ž»ö ¾Ë°í¸®Áò (A General Graph-Searching Algorithm)
(1) A* ¾Ë°í¸®Áò (Algorithm A*)
(2) A* ÀÇ Çã¿ë¼º (Admissibility of A*)
(3) Àϰü¼º (¶Ç´Â ´ÜÁ¶¼º) Á¶°Ç (The Consistency or Monotone Condition)
(4) ¹Ýº¹Àû ±íÀÌÁõ°¡ A* (Iterative Deepenig A*)
(5) Àç±ÍÀûÀÎ ÃÖ»ó¿ì¼± Ž»ö (Recursive Best-First Search)
ÈÞ¸®½ºÆ½ ÇÔ¼ö¿Í Ž»öÀÇ È¿À²¼º (Heuristic Functions and Search Efficiency)
Âü°í¹®Çå ¹× Åä·Ð (Additional Readings and Discussion)
ÀÌ Àå¿¡¼ ¼³¸íÇϴ Ž»ö ¹æ¹ýÀº ³Êºñ¿ì¼± Ž»ö°ú ºñ½ÁÇÏÁö¸¸, Ž»öÀÌ ½ÃÀÛ ³ëµå¿¡¼ºÎÅÍ ¹Ù±ùÂÊÀ¸·Î ±ÕÀÏÇÏ°Ô ÁøÇàµÇÁö ¾Ê´Â °ÍÀÌ´Ù. ´ë½Å¿¡, ¹®Á¦ÀÇ Æ¯¼º¿¡ ´ëÇÑ Á¤º¸ÀÎ ÈÞ¸®½ºÆ½ (heuristic) ¿¡ µû¶ó ¸ñÇ¥±îÁöÀÇ °¡Àå ÁÁÀº °æ·Î»ó¿¡ ÀÖ´Ù°í ÆÇ´ÜµÇ´Â ³ëµå¸¦ ¿ì¼± ¹æ¹®Çϵµ·Ï ÁøÇàµÈ´Ù. ÀÌ·¯ÇÑ Å½»ö ¹æ¹ýÀ» ÃÖ»ó¿ì¼± (best-first) ¶Ç´Â ÈÞ¸®½ºÆ½ (heuristic) Ž»öÀ̶ó°í ÇÑ´Ù. ±âº»ÀûÀÎ ¾ÆÀ̵ð¾î´Â ´ÙÀ½°ú °°´Ù.
1. ´ÙÀ½¿¡ ¾î´À ³ëµå¸¦
È®ÀåÇÏ´Â °ÍÀÌ ÃÖ¼±ÀÎÁö¸¦ °áÁ¤Çϴµ¥ µµ¿òÀÌ µÇ´Â ÈÞ¸®½ºÆ½ Æò°¡ ÇÔ¼ö ÀÌ ÀÖ´Ù°í °¡Á¤ÇÏÀÚ (
À§¿¡ "hat" À» ºÙÀÎ ÀÌÀ¯´Â ³ªÁß¿¡ ¾Ë °Ô µÈ´Ù.
´Â
-hat À̶ó°í Àд´Ù.
°ªÀÌ ÀÛÀº °ÍÀÌ ´õ ÁÁÀº ³ëµå¸¦ ³ªÅ¸³»´Â °ÍÀ̶ó°í ÇÏÀÚ. ÀÌ ÇÔ¼ö´Â ƯÁ¤ ¹®Á¦
¿µ¿ª¿¡ ´ëÇÑ Á¤º¸¸¦ ±â¹ÝÀ¸·Î ÇÏ´Â °ÍÀÌ´Ù. ÀÌ ÇÔ¼ö´Â °¢ »óÅ ǥÇö¿¡ ´ëÇØ ½Ç¼ö°ªÀ»
°®´Â´Ù.
2. °ªÀÌ °¡Àå ÀÛÀº ³ëµå¸¦ ´ÙÀ½¿¡ È®ÀåÇÒ ³ëµå·Î ¼±ÅÃÇÑ´Ù. °°Àº °ªÀ» °®´Â ³ëµåµéÀº
¹«ÀÛÀ§·Î ¼±ÅÃÇÑ´Ù (ÀÌ Àå¿¡¼´Â ³ëµå¸¦ È®ÀåÇÏ¸é ±× ³ëµåÀÇ ¸ðµç ÀÚ½Ä ³ëµå°¡
»ý¼ºµÈ´Ù°í ÇÏÀÚ).
3. ´ÙÀ½¿¡ È®ÀåÇÒ ³ëµå°¡ ¸ñÇ¥ ³ëµåÀ̸é Ž»öÀ» Á¾·áÇÑ´Ù.
¸¹Àº °æ¿ì¿¡ ÃÖ»ó¿ì¼± Ž»öÀ» ¼öÇàÇϱâ À§ÇÑ ÁÁÀº Æò°¡ ÇÔ¼ö¸¦ Á¤ÀÇÇÒ ¼ö ÀÖ´Ù. ¿¹¸¦ µé¾î, 8 ÆÛÁñÀÇ °æ¿ì¿¡´Â ¾î¶² »óÅÂÀÇ ÁÁ°í ³ª»ÝÀ» ÃøÁ¤Çϱâ À§ÇÏ¿© Á¦ÀÚ¸®¿¡ ÀÖÁö ¾ÊÀº ŸÀÏÀÇ °³¼ö¸¦ ÀÌ¿ëÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù.
= Á¦ÀÚ¸®¿¡ ÀÖÁö ¾ÊÀº ŸÀÏÀÇ ¼ö (¸ñÇ¥ »óÅÂ¿Í ºñ±³ÇßÀ» ¶§)
±×¸² 1 ÈÞ¸®½ºÆ½ Ž»öÀÇ ÇÑ ¿¹
¾Õ¿¡¼ ¼³¸íÇÑ Å½»ö ¹æ¹ý¿¡ ÀÌ ÈÞ¸®½ºÆ½ ÇÔ¼ö¸¦
Àû¿ëÇÏ¸é ±×¸² 1 °ú °°Àº ±×·¡ÇÁ°¡ ¸¸µé¾îÁø´Ù. °¢ ³ëµåÀÇ ¿·¿¡ ÀÖ´Â ¼ýÀÚ´Â ±× ³ëµåÀÇ
°ªÀ» ³ªÅ¸³½´Ù.
ÀÌ ¿¹´Â Ž»ö °úÁ¤ÀÌ ÀÏÂï ¸¸µé¾îÁø ³ëµå¸¦ ¼±È£Çϵµ·Ï ÇÒ
Çʿ䰡 ÀÖ´Ù´Â °Í (Áö³ªÄ¡°Ô ³«°üÀûÀÎ ÈÞ¸®½ºÆ½¿¡ ÀÇÇØ À߸øµÈ ±æ·Î °è¼Ó ³»·Á°¡´Â
°ÍÀ» ¸·±â À§Çؼ) À» º¸¿©ÁØ´Ù. µû¶ó¼ ¿¡ ±íÀÌ¿ä¼Ò¸¦ Ãß°¡ÇÏ¿©
À¸·Î Á¤ÀÇÇÑ´Ù. ¿©±â¼
Àº ±×·¡ÇÁ»ó¿¡¼
ÀÇ ±íÀÌ (depth) (½ÃÀÛ ³ëµå¿¡¼
±îÁö ÃÖ´Ü °æ·ÎÀÇ ±æÀÌ) ¿¡ ´ëÇÑ ÃßÁ¤°ªÀ̰í,
Àº ³ëµå
¿¡ ´ëÇÑ ÈÞ¸®½ºÆ½ Æò°¡°ªÀÌ´Ù. ¸¸ÀÏ ¾Õ¿¡¼Ã³·³
= Á¦ÀÚ¸®¿¡ ÀÖÁö ¾ÊÀº ŸÀÏÀÇ ¼ö¶ó°í Çϰí,
= Ž»ö ±×·¡ÇÁ¿¡¼ ³ëµå
ÀÇ ±íÀ̶ó°í ÇÏ¸é ±×¸² 2 ¿Í °°Àº ±×·¡ÇÁ°¡ ¸¸µé¾îÁø´Ù. ÀÌ ±×¸²¿¡´Â
°ªÀÌ °¢ ³ëµå ¿·¿¡ ³ªÅ¸³ª ÀÖ´Ù. ÀÌ °æ¿ì¿¡´Â Ž»öÀÌ ´õ °ð¹Ù·Î ¸ñÇ¥¸¦ ÇâÇØ
ÁøÇàÇÏ´Â °ÍÀ» º¼ ¼ö ÀÖ´Ù (µ¿±×¶ó¹Ì°¡ ±×·ÁÁø ³ëµå´Â ¿¹¿ÜÀÌ´Ù).
±×¸² 2 À» ÀÌ¿ëÇÑ ÈÞ¸®½ºÆ½ Ž»ö
ÀÌ ¿¹´Â µÎ °¡Áö Áß¿äÇÑ Àǹ®À» Á¦±âÇÑ´Ù. ù°, ÃÖ»ó¿ì¼± Ž»öÀÇ ¹æÇâÀ» °áÁ¤ÇÏ´Â Æò°¡ ÇÔ¼ö¸¦ ¾î¶»°Ô ¼³Á¤ÇÒ ¼ö Àִ°¡? µÑ°, ÃÖ»ó¿ì¼± Ž»öÀÇ Æ¯¼ºÀº ¹«¾ùÀΰ¡? ÃÖ»ó¿ì¼± Ž»öÀº ¾ðÁ¦³ª ¸ñÇ¥ ³ëµå±îÁöÀÇ ÁÁÀº °æ·Î¸¦ ã¾Æ³»´Â°¡? Æò°¡ ÇÔ¼ö¸¦ ¼±ÅÃÇϱâ À§ÇÑ °¡À̵å¶óÀÎÀº ÀÌ ÀåÀÇ µÞºÎºÐ¿¡¼ À̾߱âÇÒ °ÍÀ̸ç, Æò°¡ ÇÔ¼ö¸¦ ÀÚµ¿À¸·Î ÇнÀÇÏ´Â ¹æ¹ýÀº °èȹ, Çൿ ±×¸®°í ÇнÀ¿¡¼ ¼³¸íÇÒ °ÍÀÌ´Ù. ±×·¯³ª ÀÌ Àå¿¡¼´Â ´ëºÎºÐ ÃÖ»ó¿ì¼± Ž»ö¿¡ ´ëÇÑ Á¤ÀÇ¿Í ¿©·¯ Ãø¸éµéÀ» À̾߱âÇÒ °ÍÀÌ´Ù. ¿ì¼± ÀϹÝÀûÀÎ ±×·¡ÇÁ Ž»ö ¾Ë°í¸®ÁòÀ» Á¤ÀÇÇϵµ·Ï ÇÏÀÚ. ÃÖ»ó¿ì¼± Ž»öÀº ÀÌ·¯ÇÑ ¾Ë°í¸®ÁòÀÇ ÇÑ Æ¯¼öÇÑ °æ¿ì¿¡ ÇØ´çÇÑ´Ù (ÈÞ¸®½ºÆ½ Ž»ö¿¡ °üÇÑ ´õ ÀÚ¼¼ÇÑ ³»¿ëÀº ÀÎ¿ë ³í¹®°ú Pearl [Pearl 1984] ÀÇ Ã¥À» Âü°íÇ϶ó).
ÀÌ Àå¿¡¼ ¼³¸íÇÒ ÈÞ¸®½ºÆ½ Ž»ö ¹æ¹ý¿¡ ´ëÇØ Á» ´õ »ó¼¼ÇÏ°Ô ±â¼úÇÏ·Á¸é ÈÞ¸®½ºÆ½À̳ª ¹«Á¤º¸ Ž»ö ¾î´À ÂÊ¿¡³ª Àû¿ëµÇ´Â ÀϹÝÀûÀÎ ±×·¡ÇÁ Ž»ö ¾Ë°í¸®ÁòÀ» À̾߱âÇÒ Çʿ䰡 ÀÖ´Ù. ÀÌ ¾Ë°í¸®ÁòÀ» GRAPHSEARCH ¶ó°í ÇÏÀÚ. ÀÌ ¾Ë°í¸®ÁòÀÇ (ù¹øÂ°) Á¤ÀÇ´Â ´ÙÀ½°ú °°´Ù.
GRAPHSEARCH
1. ½ÃÀÛ ³ëµå ¸¸À¸·Î ±¸¼ºµÈ Ž»öÆ®¸®
À» ¸¸µç´Ù.
À» ¼ø¼ ÀÖ´Â ¸®½ºÆ®ÀÎ OPEN ¿¡ ³Ö´Â´Ù.
2. ºó ¸®½ºÆ® CLOSED ¸¦ ¸¸µç´Ù.
3. OPEN ÀÌ ºñ¾î ÀÖÀ¸¸é ½ÇÆÐ·Î ³¡³´Ù.
4. OPEN ¿¡¼ ù
¹øÂ° ³ëµå¸¦ ¼±ÅÃÇÏ¿© OPEN ¿¡¼ »èÁ¦Çϰí CLOSED ¿¡ ³Ö´Â´Ù.
ÀÌ ³ëµå¸¦ À̶ó°í ÇÑ´Ù.
5. ÀÌ ¸ñÇ¥ ³ëµåÀ̸é
ÀÇ ¾ÆÅ©¸¦ µû¶ó
¿¡¼
À¸·Î °Å²Ù·Î °æ·Î¸¦ ÃßÀûÇÏ¿© ´äÀ» ¾ò°í ³¡³´Ù (¾ÆÅ©´Â ´Ü°è 6 ¿¡¼ ¸¸µç´Ù).
6. ³ëµå À» È®ÀåÇÏ¿© ÀÚ½Ä ³ëµåµéÀÇ ÁýÇÕ
À» ¸¸µç´Ù.
À¸·ÎºÎÅÍ
ÀÇ °¢ ¿ø¼Ò·Î ¾ÆÅ©¸¦ ¸¸µé¾î
ÀÇ ÀÚ½Ä ³ëµåµéÀ»
¿¡ ³Ö´Â´Ù.
7. ÀÇ ÀÚ½Ä ³ëµåµéÀ» OPEN ¿¡ ³Ö°í ÈÞ¸®½ºÆ½°ªÀÇ ¼ø¼ ¶Ç´Â ´Ù¸¥ ¾î¶² ÀÓÀÇÀÇ
¼ø¼¿¡ µû¶ó OPEN À» ÀçÁ¤·ÄÇÑ´Ù.
8. ´Ü°è 3 À¸·Î µ¹¾Æ°£´Ù.
ÀÌ ¾Ë°í¸®ÁòÀº ÃÖ»ó¿ì¼± Ž»ö, ±íÀ̿켱 Ž»ö, ¶Ç´Â ³Êºñ¿ì¼± Ž»öÀ» ¼öÇàÇÏ´Â µ¥ ¸ðµÎ »ç¿ëµÉ ¼ö ÀÖ´Ù. ³Êºñ¿ì¼± Ž»öÀ» ÇÏ·Á¸é »õ ³ëµå¸¦ OPEN ÀÇ ³¡¿¡ ³Ö°í (first in first out ¶Ç´Â FIFO), ÀçÁ¤·ÄÇÏÁö ¾ÊÀ¸¸é µÈ´Ù. ±íÀ̿켱 Ž»öÀ» ÇÏ·Á¸é »õ ³ëµå¸¦ OPEN ÀÇ ¾Õ¿¡ ³ÖÀ¸¸é µÈ´Ù (last in first out ¶Ç´Â FIFO). ÃÖ»ó¿ì¼± (ÈÞ¸®½ºÆ½) Ž»öÀ» ÇÏ·Á¸é OPEN À» °¢ ³ëµåÀÇ ÈÞ¸®½ºÆ½°ª¿¡ µû¶ó ÀçÁ¤·ÄÇÏ¸é µÈ´Ù.
GRAPHSEARCH ¾Ë°í¸®ÁòÀ»
OPEN ¿¡ ÀÖ´Â ³ëµåµéÀ» 8 ÆÛÁñ¿¡¼ º¸ÀÎ °Í°ú °°ÀÌ °ªÀÇ ¿À¸§Â÷¼øÀ¸·Î Á¤·ÄÇÏ´Â (´Ü°è 7) ÃÖ»ó¿ì¼± Ž»öÀ¸·Î ¸¸µé¾î º¸ÀÚ. ÀÌ·¸°Ô
¸¸µç GRAPHSEARCH ¾Ë°í¸®ÁòÀ» ¾Ë°í¸®Áò A* ¶ó°í ÇÏÀÚ. °ð ¼³¸íÇϰÚÁö¸¸,
A* °¡ ³Êºñ¿ì¼± ¶Ç´Â ±ÕÀϺñ¿ë Ž»öÀ» ¼öÇàÇϵµ·Ï
ÇÔ¼ö¸¦ Á¤ÀÇÇÒ ¼ö ÀÖ´Ù. ¾ÕÀ¸·Î »ç¿ëÇÒ
ÇÔ¼öµéÀ» Á¤ÀÇÇϱâ À§ÇÏ¿© ¿ì¼± ¸î °¡Áö Ãß°¡ÀûÀÎ ¿ë¾îµéÀ» µµÀÔÇÏÀÚ.
À» ³ëµå
°ú ¸ñÇ¥ ³ëµå »çÀÌÀÇ ÃÖ´Ü °æ·Î (
¿¡¼ ¸ðµç ¸ñÇ¥ ³ëµå±îÁöÀÇ ¸ðµç °¡´ÉÇÑ °æ·Î Áß¿¡¼) ÀÇ ½ÇÁ¦ °ªÀ̶ó°í ÇÏÀÚ.
À» ½ÃÀÛ ³ëµå
¿¡¼
±îÁöÀÇ ÃÖ´Ü °æ·ÎÀÇ °ªÀ̶ó°í ÇÏÀÚ. ±×·¯¸é
˼
¿¡¼ ¸ñÇ¥ ³ëµå±îÁö ³ëµå
À» ÅëÇÏ¿© °¥ ¼ö ÀÖ´Â ¸ðµç °¡´ÉÇÑ °æ·Î Áß¿¡¼ ÃÖ´Ü °æ·ÎÀÇ °ªÀÌ µÈ´Ù. ±×¸®°í
´Â
¿¡¼ ¸ñÇ¥ ³ëµå±îÁöÀÇ (Á¶°Ç ¾ø´Â) ÃÖ´Ü °æ·ÎÀÇ °ªÀ» ³ªÅ¸³½´Ù. °¢ ³ëµå
¿¡ ´ëÇÏ¿©
(ÈÞ¸®½ºÆ½ ¿ä¼Ò) À»
ÀÇ ÃßÁ¤°ªÀ̶ó°í Çϰí,
(±íÀÌ ¿ä¼Ò) À» A* ¿¡ ÀÇÇÏ¿© Áö±Ý±îÁö ¹ß°ßµÈ ³ëµå
±îÁöÀÇ °æ·Î Áß¿¡¼ ÃÖ´Ü °æ·ÎÀÇ °ªÀ̶ó°í ÇÏÀÚ. ¾Ë°í¸®Áò A* ¿¡¼´Â
¸¦ Æò°¡ ÇÔ¼ö·Î »ç¿ëÇÑ´Ù. ¾Ë°í¸®Áò A* ¿¡¼
ÀÌ 0 ÀÌ¸é ±ÕÀϺñ¿ë Ž»öÀÌ µÈ´Ù.
Áö±Ý±îÁöÀÇ Á¤ÀǵéÀ» ±×¸² 3 ¿¡ ³ªÅ¸³»¾ú´Ù.
±×¸² 3 ÈÞ¸®½ºÆ½ Ž»öÀÇ ¿ë¾î
±×¸² 2 ¿¡¼ º¸ÀÎ 8 ÆÛÁñ¿¡ ´ëÇÑ Å½»ö °úÁ¤Àº A*
ÀÇ ÇÑ ÀÀ¿ë ¿¹ÀÌ´Ù. ±× ¿¹¿¡¼´Â ¸ðµç ¾ÆÅ©ÀÇ °ªÀ» 1 ·Î °¡Á¤ÇÏ¿´À¸¹Ç·Î, Àº ´Ü¼øÈ÷ ³ëµå
ÀÇ ±íÀ̰¡ µÈ´Ù. ±×·±µ¥ ¾Ë°í¸®Áò A* ÀÇ Á¤ÀÇ¿¡¼ ¤°í ³Ñ¾î°¡Áö
¾ÊÀº ¾à°£ º¹ÀâÇÑ ¹®Á¦°¡ ÀÖ´Ù. ¸¸ÀÏ Å½»öÇϰí ÀÖ´Â ¾Ï½ÃÀûÀÎ ±×·¡ÇÁ°¡ Æ®¸®°¡ ¾Æ´Ï¸é
¾î¶»°Ô µÇ´Â°¡? Áï, ½ÃÀÛ »óÅ¿¡¼ ƯÁ¤ÇÑ »óÅ·Π°¡´Â Çൿ ¼ø¼°¡ Çϳª ÀÌ»ó ÀÖ´Â
°æ¿ì¸¦ ¸»ÇÑ´Ù. ¿¹¸¦ µé¾î 8 ÆÛÁñÀÇ °æ¿ì, ¸ðµç ÇൿÀÌ ¿ª¹æÇâÀ¸·Î °¥ ¼ö ÀÖÀ¸¹Ç·Î
¾î¶² ³ëµå
ÀÇ °¢ ÀÚ½Ä ³ëµåµéÀº
À» ÀÚ½ÅÀÇ ÀÚ½Ä ³ëµå·Î °¡Áø´Ù. µû¶ó¼ 8 ÆÛÁñÀÇ ¾Ï½ÃÀûÀÎ ±×·¡ÇÁ´Â ºÐ¸íÈ÷ Æ®¸®°¡
¾Æ´Ï´Ù. 8 ÆÛÁñÀÇ Å½»ö Æ®¸®¸¦ ¸¸µé ¶§´Â ÀÌ·¯ÇÑ ·çÇÁ (loop) ¸¦ ¹«½ÃÇÏ¿´´Ù. 8 ÆÛÁñÀÇ
°æ¿ì¿¡´Â À̰ÍÀÌ °£´ÜÇÏ¿´´Ù. Áï, ¾î¶² ³ëµåÀÇ ºÎ¸ð ³ëµå´Â ±× ³ëµåÀÇ ÀÚ½Ä ³ëµåµé
Áß¿¡ Æ÷ÇÔ½ÃŰÁö ¾Ê¾Ò´Ù. GRAPHSEARCH ÀÇ ´Ü°è 6 À» ½ÇÁ¦·Î ´ÙÀ½°ú °°ÀÌ ¼öÇàÇß´Ù.
6. ³ëµå À» È®ÀåÇÏ¿© ÀÚ½Ä ³ëµåµéÀÇ ÁýÇÕ
À» ¸¸µç´Ù.
À¸·ÎºÎÅÍ
ÀÇ °¢ ¿ø¼Ò·Î ¾ÆÅ©¸¦ ¸¸µé¾î
ÀÇ ÀÚ½Ä ³ëµåµéÀ»
¿¡ ³Ö´Â´Ù.
´õ Å« ·çÇÁ¸¦ °í·ÁÇÏ·Á¸é ´Ü°è 6 À» ´ÙÀ½°ú °°ÀÌ ¹Ù²Û´Ù.
6. ³ëµå À» È®ÀåÇÏ¿© ÀÚ½Ä ³ëµå Áß
¿¡¼
ÀÇ Á¶»óÀÌ ¾Æ´Ñ ³ëµåµéÀÇ ÁýÇÕ
À» ¸¸µç´Ù.
À¸·ÎºÎÅÍ
ÀÇ °¢ ¿ø¼Ò·Î ¾ÆÅ©¸¦ ¸¸µé¾î
ÀÇ ÀÚ½Ä ³ëµåµéÀ»
¿¡ ³Ö´Â´Ù.
¹°·Ð ÀÌ·¯ÇÑ Å« ·çÇÁ¸¦ °Ë»çÇÏ·Á¸é ¾î¶² ³ëµå ÀÇ °¢ ÀÚ½Ä ³ëµå°¡ ³ëµå
ÀÇ Á¶»ó ³ëµå¿Í ÀÏÄ¡ÇÏ´ÂÁö º¸¾Æ¾ß ÇÑ´Ù. ÀÚ·á ±¸Á¶°¡ º¹ÀâÇÒ °æ¿ì, ÀÌ ´Ü°è
¶§¹®¿¡ ¾Ë°í¸®ÁòÀÇ º¹Àâµµ (complexity) °¡ Ä¿Áú ¼ö ÀÖ´Ù.
´Ü°è 6 À» ¼öÁ¤Çϸé
¾Ë°í¸®ÁòÀÌ ¸ñÇ¥±îÁöÀÇ °æ·Î¸¦ Ž»öÇÒ ¶§ ¹Ýº¹ÀûÀÎ ·çÇÁ¿¡ ºüÁö´Â °ÍÀ» ¸·À» ¼ö ÀÖ´Ù.
±×·¯³ª ¾ÆÁ÷µµ ´Ù¸¥ °æ·Î¸¦ ÅëÇÏ¿© °°Àº »óÅ¿¡ µµ´ÞÇÒ °¡´É¼ºÀÌ ³²¾Æ ÀÖ´Ù. ÀÌ ¹®Á¦¸¦
ó¸®ÇÏ´Â ÇÑ °¡Áö ¹æ¹ýÀº ÀÌ °æ¿ì¸¦ ¹«½ÃÇÏ´Â °ÍÀÌ´Ù. Áï, ¾Ë°í¸®ÁòÀÌ ¿¡ ÀÖ´Â ¾î¶² ³ëµå°¡ ÀÌ¹Ì OPEN ¶Ç´Â CLOSED ¿¡ ÀÖ´ÂÁö °Ë»çÇÏÁö
¾Ê´Â °ÍÀÌ´Ù. ÀÌ·¸°Ô µÇ¸é ¾Ë°í¸®ÁòÀº ´Ù¸¥ °æ·Î·Î °°Àº ³ëµå¿¡ µµ´ÞÇßÀ» °¡´É¼º¿¡
´ëÇØ¼´Â »ó°üÇÏÁö ¾Ê´Â´Ù. ÀÌ "°°Àº ³ëµå" ´Â ¾Ë°í¸®ÁòÀÌ ¼·Î ´Ù¸¥ °æ·Î¸¦
ãÀº ¼ö¸¸Å
¿¡ ¹Ýº¹µÉ °ÍÀÌ´Ù. ¸¸ÀÏ
ÀÇ µÎ ³ëµå°¡ °°Àº ÀÚ·á ±¸Á¶¸¦ °®°í ÀÖ´Ù¸é ÀÌ µÎ ³ëµå´Â °¢ÀÚ ¶È°°Àº ¼ºêÆ®¸®¸¦
°®°Ô µÉ °ÍÀÌ´Ù. µû¶ó¼ ¾Ë°í¸®ÁòÀº ÇÊ¿ä¾ø´Â Ž»öÀ» ¹Ýº¹ÇÏ°Ô µÈ´Ù. µÚ¿¡ °¡¼
¿¡ ´ëÇÑ Àû´çÇÑ Á¶°ÇÇÏ¿¡¼´Â A* °¡
¿¡¼ ¾î¶² ³ëµå
À» óÀ½ È®ÀåÇÒ ¶§ À̹Ì
°ªÀÌ ÃÖ¼ÒÀÎ
±îÁöÀÇ °æ·Î¸¦ ¹ß°ßÇÑ °ÍÀÓÀ» º¸ÀÏ °ÍÀÌ´Ù.
±×¸² 4 Ž»ö°úÁ¤¿¡¼ ¸¸µé¾îÁö´Â Ž»ö ±×·¡ÇÁ¿Í Æ®¸®
¾ÕÀ¸·Î ¼³¸íÇÒ ¿¡ ´ëÇÑ Á¶°ÇÀÌ ÀüÁ¦µÇÁö ¾Ê´Â °æ¿ì, Áߺ¹µÈ Ž»öÀ» ¸·À¸·Á¸é ¾Ë°í¸®Áò A*
¿¡ ¾à°£ÀÇ ¼öÁ¤À» ÇØ¾ß ÇÑ´Ù. Ž»öÀÌ ¼·Î ´Ù¸¥ °æ·Î·Î °°Àº ³ëµå¿¡ µµ´ÞÇÒ ¼ö ÀÖÀ¸¹Ç·Î
¾Ë°í¸®Áò A* ´Â ±×·¡ÇÁ¸¦ ¸¸µé¾î³»°Ô µÈ´Ù. ÀÌ ±×·¡ÇÁ¸¦
¶ó°í ÇÏÀÚ.
´Â A* °¡ ½ÃÀÛ ³ëµå¿¡¼ºÎÅÍ ÀÚ½Ä ³ëµå¿Í ±× ÀÚ½Ä ³ëµåµéÀ» Â÷·Ê·Î
È®ÀåÇÏ¸é¼ ¸¸µé¾î³½ ³ëµå¿Í ¾ÆÅ©ÀÇ ±¸Á¶ÀÌ´Ù. A* ´Â ¶ÇÇÑ Å½»öÆ®¸®
À» ÀúÀåÇϰí ÀÖ´Ù.
ÀÇ ¼ºê±×·¡ÇÁÀÎ
Àº Ž»ö ±×·¡ÇÁ¿¡¼ ¸ðµç ³ëµå±îÁöÀÇ Áö±Ý±îÁö ã¾ÆÁø ÃÖ´Ü °æ·Î·Î ±¸¼ºµÈ Æ®¸®ÀÌ´Ù.
±×¸² 4 ¿¡ ¾ÆÅ©°ªÀÌ ¸ðµÎ 1 ÀÎ ±×·¡ÇÁÀÇ ¿¹¸¦ º¸¿´´Ù. Ž»öÀÇ ÃʹÝÀº ±×¸² 4a ¿Í
°°´Ù. Ž»ö ±×·¡ÇÁ¿¡¼ Ž»öÆ®¸® ºÎºÐÀº ÁøÇÑ»ö ¾ÆÅ©·Î Ç¥½ÃµÇ¾î ÀÖ°í, ȸ»ö ¾ÆÅ©´Â
Ž»öÆ®¸®¿¡ Æ÷ÇÔµÇÁö ¾Ê´Â ºÎºÐÀÌ´Ù. ÁøÇÑ»ö ¾ÆÅ©´Â ÇØ´ç ³ëµå±îÁöÀÇ Áö±Ý±îÁö ¹ß°ßµÈ
°æ·Î Áß ÃÖ¼Ò°ªÀ» °®´Â °æ·Î¸¦ ³ªÅ¸³½´Ù. ±×¸² 4a ¿¡¼ ³ëµå 4 ´Â µÎ °³ÀÇ °æ·Î¸¦
µû¶ó µµ´ÞÇÒ ¼ö ÀÖ´Ù. µÎ °æ·Î ¸ðµÎ Ž»ö ±×·¡ÇÁ¿¡ ÀÖÁö¸¸ Ž»öÆ®¸®¿¡´Â Çϳª¸¸ Æ÷ÇԵȴÙ.
ÀÌÀü Ž»ö °úÁ¤¿¡¼ Ž»öÆ®¸®¿¡ ÀÖÁö ¾Ê¾Ò´ø ¾ÆÅ©¸¦ Æ÷ÇÔÇÏ´Â ´õ ªÀº °æ·Î°¡ ³ªÁß¿¡
ã¾ÆÁú ¼ö Àֱ⠶§¹®¿¡ Ž»ö ±×·¡ÇÁ¸¦ ÀúÀåÇϰí ÀÖ¾î¾ß ÇÑ´Ù. ¿¹¸¦ µé¾î, ±×¸² 4b
¿¡¼ ³ëµå 1 À» È®ÀåÇÏ¸é ³ëµå 2 ¿Í ±× Èļյé (³ëµå 4 µîÀ» Æ÷ÇÔÇÑ) ±îÁöÀÇ ´õ ªÀº
°æ·Î°¡ ã¾ÆÁö¹Ç·Î Ž»öÆ®¸®°¡ º¯ÇÏ°Ô µÈ´Ù.
¿Ïº®À» ±âÇϱâ À§Çؼ, Ž»ö ±×·¡ÇÁ¸¦
À¯ÁöÇÏ´Â A* ¾Ë°í¸®ÁòÀ» ¾²µµ·Ï ÇϰڴÙ. ±×·¯³ª ´ë°³ÀÇ °æ¿ì, ¾Ë°í¸®Áò
A* °¡ ¾î¶² ³ëµå¸¦ È®ÀåÇÒ ¶§ ¾ðÁ¦³ª ±× ³ëµå±îÁöÀÇ ÃÖ´Ü °æ·Î¸¦ ãµµ·Ï
¿¡ ´ëÇÑ Á¶°ÇÀ» ÁÙ ¼ö ÀÖÀ¸¹Ç·Î, ÀÌ ÇüÅÂÀÇ ¾Ë°í¸®ÁòÀº °ÅÀÇ ¾²ÀÌÁö ¾Ê´Â´Ù.
¾Ë°í¸®Áò A*
1. ½ÃÀÛ ³ëµå ¸¸À¸·Î ±¸¼ºµÈ Ž»ö ±×·¡ÇÁ
À» ¸¸µç´Ù.
À» ¸®½ºÆ® OPEN ¿¡ ³Ö´Â´Ù.
2. ºó ¸®½ºÆ® CLOSED ¸¦ ¸¸µç´Ù.
3. OPEN ÀÌ ºñ¾î ÀÖÀ¸¸é ½ÇÆÐ·Î ³¡³´Ù.
4. OPEN ¿¡¼ ù
¹øÂ° ³ëµå¸¦ ¼±ÅÃÇÏ¿© OPEN ¿¡¼ »èÁ¦Çϰí CLOSED ¿¡ ³Ö´Â´Ù.
ÀÌ ³ëµå¸¦ À̶ó°í ÇÑ´Ù.
5. ÀÌ ¸ñÇ¥ ³ëµåÀ̸é
ÀÇ Æ÷ÀÎÅ͸¦ µû¶ó
¿¡¼
À¸·Î °æ·Î¸¦ ÃßÀûÇÏ¿© ´äÀ» ¾ò°í ³¡³´Ù (ÀÌ Æ÷ÀÎÅ͸¦ Ž»öÆ®¸®¸¦ Á¤ÀÇÇÏ´Â °ÍÀ¸·Î
´Ü°è 7 ¿¡¼ ¸¸µç´Ù).
6. ³ëµå À» È®ÀåÇÏ¿© ÀÚ½Ä ³ëµå Áß
¿¡¼
ÀÇ Á¶»óÀÌ ¾Æ´Ñ ³ëµåµéÀÇ ÁýÇÕ
À» ¸¸µç´Ù.
ÀÇ °¢ ¿ø¼Ò·Î
ÀÇ ÀÚ½Ä ³ëµåµé·Î
¿¡ ³Ö´Â´Ù.
7. ÀÌ¹Ì ¿¡ ÀÖÁö ¾ÊÀº (Áï, OPEN À̳ª CLOSED ¿¡ ÀÖÁö ¾ÊÀº)
ÀÇ °¢ ¿ø¼Òµé·ÎºÎÅÍ
À¸·Î Æ÷ÀÎÅ͸¦ ¸¸µç´Ù.
ÀÇ ÀÌ ¿ø¼ÒµéÀ» OPEN ¿¡ ³Ö´Â´Ù. ÀÌ¹Ì OPEN À̳ª CLOSED ¿¡
ÀÖ´Â
ÀÇ °¢ ¿ø¼Ò
¿¡ ´ëÇØ¼´Â, Áö±Ý±îÁö ã¾ÆÁø
±îÁöÀÇ ÃÖ´Ü °æ·Î°¡
À» Áö³ª¿À´Â °ÍÀ̶ó¸é Æ÷ÀÎÅ͸¦
À¸·Î º¯°æÇÑ´Ù. ÀÌ¹Ì CLOSED ¿¡ ÀÖ´Â
ÀÇ °¢ ¿ø¼Ò¿¡ ´ëÇØ¼´Â, ¸ðµç ÈÄ¼Õ ³ëµåÀÇ Æ÷ÀÎÅ͸¦ Áö±Ý±îÁö ã¾ÆÁø Ãִܰæ·Î¸¦
°¡¸®Å°µµ·Ï º¯°æÇÑ´Ù.
8. °ªÀÇ ¿À¸§Â÷¼øÀ¸·Î OPEN À» ÀçÁ¤·ÄÇÑ´Ù (
°ªÀÌ °°Àº °æ¿ì¿¡´Â Ž»öÆ®¸®¿¡¼ ±íÀÌ ÀÖ´Â ³ëµå¸¦ ¿ì¼±ÇÑ´Ù).
9. ´Ü°è 3 À¸·Î µ¹¾Æ°£´Ù.
´Ü°è 7 ¿¡¼´Â ¸¸ÀÏ Å½»ö °úÁ¤¿¡¼ ¾î¶² ³ëµå¿¡ ´ëÇØ ÇöÀçÀÇ Æ÷ÀÎÅͰ¡ °¡¸®Å°´Â °æ·Îº¸´Ù ´õ ÀÛÀº °ªÀ» °®´Â °æ·Î°¡ ¹ß°ßµÇ¸é Æ÷ÀÎÅ͸¦ º¯°æÇÑ´Ù. ÀÌ¹Ì CLOSED ¿¡ ÀÖ´Â ³ëµåÀÇ ¸ðµç ÈÄ¼Õ ³ëµåÀÇ Æ÷ÀÎÅ͸¦ º¯°æÇϸé Ž»öÀÌ ÁÙ¾îµé °Ô µÇÁö¸¸, °è»ê·®ÀÌ Áö¼ö ÇÔ¼öÀûÀ¸·Î ´Ã¾î³¯ °¡´É¼ºÀÌ ÀÖ´Ù. µû¶ó¼ ´Ü°è 7 ÀÇ ÀÌ ºÎºÐÀº ´ë°³ ±¸ÇöÇÏÁö ¾Ê´Â´Ù. ÀÌ·¯ÇÑ Æ÷ÀÎÅÍÀÇ ´ëºÎºÐÀº Ž»öÀÌ ÁøÇàµÇ¸é¼ °á±¹ º¯°æµÇ°Ô µÇ¾î ÀÖ´Ù.
¾Ë°í¸®Áò A*
°¡ Ç×»ó ÃÖ´Ü °æ·Î¸¦ ã´Â °ÍÀ» º¸ÀåÇÏ´Â ±×·¡ÇÁ¿Í ¿¡ ´ëÇÑ Á¶°ÇÀÌ ÀÖ´Ù. ±×·¡ÇÁ¿¡ ´ëÇÑ Á¶°ÇÀº ´ÙÀ½°ú °°´Ù.
1. ±×·¡ÇÁÀÇ °¢ ³ëµå´Â À¯ÇѰ³ÀÇ ÀÚ½Ä ³ëµå¸¦ °¡Áø´Ù.
2. ±×·¡ÇÁÀÇ ¸ðµç ¾ÆÅ©´Â
ÀÓÀÇÀÇ ¾ç¼ö º¸´Ù Å« °ªÀ» °®´Â´Ù.
¿¡ ´ëÇÑ Á¶°ÇÀº ´ÙÀ½°ú °°´Ù.
3. Ž»ö ±×·¡ÇÁÀÇ ¸ðµç
³ëµå ¿¡ ´ëÇÏ¿©
ÀÌ´Ù. Áï
´Â Àý´ë ½ÇÁ¦ °ª
¸¦ ³ÑÁö ¾Ê´Â´Ù (ÀÌ·¯ÇÑ
ÇÔ¼ö¸¦ ³«°üÀû ÃßÁ¤ÀÚ (optimistic estimator) ¶ó°íµµ ÇÑ´Ù).
ÀÌ·¯ÇÑ ÇÏÇÑ (lower-bound) Á¶°ÇÀ» ¸¸Á·ÇÏ´Â ÇÔ¼ö¸¦ ã´Â °ÍÀº ±×·¸°Ô Èûµç ÀÏÀÌ ¾Æ´Ï´Ù. ¿¹¸¦ µé¾î, ³ëµå°¡ µµ½ÃµéÀ»
³ªÅ¸³»´Â ±×·¡ÇÁÀÇ °æ·Î ã±â ¹®Á¦¿¡¼´Â, ¾î¶² µµ½Ã
¿¡¼ ¸ñÇ¥ µµ½Ã±îÁöÀÇ Á÷¼± °Å¸®°¡
¿¡¼ ¸ñÇ¥ ³ëµå±îÁöÀÇ ÃÖÀû °æ·ÎÀÇ ±æÀÌ¿¡ ´ëÇÑ ÇÏÇѰªÀÌ µÈ´Ù. 8 ÆÛÁñ ¹®Á¦¿¡¼´Â,
Á¦ÀÚ¸®¿¡ ÀÖÁö ¾ÊÀº ŸÀÏÀÇ ¼ö°¡ ¸ñÇ¥±îÁö ³²Àº ŸÀÏ À̵¿ °³¼ö¿¡ ÇÏÇѰªÀÌ µÈ´Ù.
ÀÌ·¯ÇÑ
¼¼ °³ÀÇ Á¶°ÇÀ» ¸¸Á·ÇÏ¸é ¾Ë°í¸®Áò A* ´Â ¸ñÇ¥±îÁöÀÇ °æ·Î°¡ Àֱ⸸ ÇÏ´Ù¸é
Ç×»ó ÃÖÀû °æ·Î¸¦ ã´Â´Ù´Â °ÍÀ» º¸ÀåÇÑ´Ù. À̰ÍÀ» ÇϳªÀÇ Á¤¸® (theorem) ·Î Ç¥ÇöÇÒ
¼ö ÀÖ´Ù (¾Æ·¡¿¡ ÀÌ Á¤¸®¿¡ ´ëÇÑ »õ·Î¿î Áõ¸íÀ» Á¦½ÃÇÏ¿´´Ù. ¿ø·¡ÀÇ Áõ¸íÀ» º¸·Á¸é
[Hart, Nilsson, & Raphael 1968] À» Âü°íÇ϶ó).
Á¤¸® 1
¾Õ¿¡¼ ¾ð±ÞÇÑ ±×·¡ÇÁ¿Í ¿¡ ´ëÇÑ Á¶°ÇÀÌ ¸¸Á·µÇ°í, ½ÃÀÛ ³ëµå
¿¡¼ ¸ñÇ¥ ³ëµå±îÁö À¯ÇѰªÀ» °®´Â °æ·Î°¡ Á¸ÀçÇϸé, ¾Ë°í¸®Áò A* ´Â
Ç×»ó ¸ñÇ¥±îÁöÀÇ ÃÖ´Ü °æ·Î¸¦ ã°í ³¡³ª°Ô µÈ´Ù.
Áõ ¸í ¡¦ Áõ¸íÀÇ ÁÖ ¿ä¼Ò´Â ´ÙÀ½¿¡ ÀÖ´Â Áß¿äÇÑ º¸Á¶Á¤¸®ÀÌ´Ù. ¾î¶»°Ô ¾Ë°í¸®Áò A* °¡ ÃÖÀû °æ·Î¸¦ ã´Â °ÍÀ» º¸ÀåÇϴ°¡¿¡ ´ëÇÑ Á÷°üÀ» ¾ò±â À§Çؼ´Â ÀÌ º¸Á¶Á¤¸®¸¦ ¿ÏÀüÈ÷ ÀÌÇØÇÏ´Â °ÍÀÌ Áß¿äÇÏ´Ù.
º¸Á¶Á¤¸®
1
A* °¡ ³¡³¯ ¶§±îÁöÀÇ ¸ðµç ´Ü°è¿¡, ¾Æ·¡ÀÇ Æ¯¼ºÀ»
¸¸Á·ÇÏ´Â ³ëµå °¡ Ç×»ó OPEN ¿¡ Á¸ÀçÇÑ´Ù.
1. ´Â ¸ñÇ¥±îÁöÀÇ ÃÖÀû °æ·Î»ó¿¡ ÀÖ´Ù.
2. A* ´Â ±îÁöÀÇ ÃÖÀû °æ·Î¸¦ ã¾Ò´Ù.
3.
º¸Á¶Á¤¸®ÀÇ Áõ¸í ¡¦ ÀÌ º¸Á¶Á¤¸®ÀÇ °á·ÐÀÌ A* ÀÇ ¸ðµç ´Ü°è¿¡¼ ¼º¸³ÇÑ´Ù´Â °ÍÀ» Áõ¸íÇÏ·Á¸é, ´ÙÀ½ÀÇ µÎ °¡Áö¸¦ Áõ¸íÇØ¾ß ÇÑ´Ù. (1) ¾Ë°í¸®ÁòÀÌ ½ÃÀÛÇÒ ¶§ °á·ÐÀÌ ¼º¸³ÇÑ´Ù. (2) ¾î¶² ³ëµå¸¦ È®ÀåÇϱâ Àü¿¡ °á·ÐÀÌ ¼º¸³ÇÑ´Ù¸é ³ëµå¸¦ È®ÀåÇÑ ÈÄ¿¡µµ °á·ÐÀÌ ¼º¸³ÇÑ´Ù. ÀÌ·± Áõ¸í ¹æ¹ýÀ» ¼öÇÐÀû ±Í³³¹ý (mathematical induction) À̶ó°í ÇÑ´Ù. Áõ¸íÀº ´ÙÀ½°ú °°´Ù.
±âº» ´Ü°è : Ž»öÀÌ ½ÃÀÛµÉ ¶§ (³ëµå ¸¸ÀÌ È®ÀåÀ» À§ÇØ ¼±ÅõÆÀ» ¶§) ³ëµå
Àº OPEN ¿¡ ÀÖÀ¸¸ç, ¸ñÇ¥±îÁöÀÇ ÃÖÀû °æ·Î»ó¿¡ ÀÖ°í, A* ´Â
±îÁöÀÇ ÃÖÀû °æ·Î¸¦ ãÀº »óÅÂÀÌ´Ù. ¶ÇÇÑ
À̹ǷÎ
°¡ ¼º¸³µÈ´Ù. µû¶ó¼ ³ëµå
ÀÌ º¸Á¶Á¤¸®ÀÇ
¿¡ ÇØ´çµÈ´Ù.
±Í³³ ´Ü°è : º¸Á¶Á¤¸®ÀÇ °á·ÐÀÌ °³ÀÇ ³ëµå
°¡ È®ÀåµÈ »óÅ¿¡¼ ÂüÀ̶ó°í °¡Á¤Çϰí,
°³ÀÇ ³ëµå°¡ È®ÀåµÇ¾úÀ» ¶§µµ ÂüÀÓÀ» Áõ¸íÇÑ´Ù. ±Í³³ ´Ü°è¸¦ Áõ¸íÇÏ´Â µ¿¾È ±×¸²
5 ¸¦ Âü°íÇÏ¸é µµ¿òÀÌ µÉ °ÍÀÌ´Ù.
±×¸² 5 ¹øÂ° ³ëµå°¡ È®ÀåµÉ ¶§ÀÇ »óȲ
°¡ OPEN ¿¡ ÀÖ´Â ³ëµå·Î½á A* °¡
°³ÀÇ ³ëµå¸¦ È®ÀåÇÑ ÈÄ¿¡ ã¾ÆÁø ÃÖÀû °æ·Î»ó¿¡ ÀÖ´Â ³ëµå¶ó°í °¡Á¤ÇÏÀÚ. ¸¸ÀÏ
¹øÂ° ´Ü°è¿¡¼
°¡ È®ÀåµÇÁö ¾Ê´Â´Ù¸é (±×¸² 5a),
´Â Àü°ú °°Àº Ư¼ºÀ» ±×´ë·Î °¡Áö°í ÀÖÀ¸¹Ç·Î ÀÌ °æ¿ì¿¡´Â ±Í³³ ´Ü°è°¡ Áõ¸íµÈ´Ù.
¸¸ÀÏ
°¡ È®ÀåµÈ´Ù¸é (±×¸² 5b),
ÀÇ ¸ðµç ÀÚ½Ä ³ëµåµéÀÌ OPEN ¿¡ µé¾î°¡°í, À̵é Áß Àû¾îµµ ÇϳªÀÇ ³ëµå
´Â ¸ñÇ¥±îÁöÀÇ ÃÖÀû °æ·Î»ó¿¡ ÀÖÀ» °ÍÀÌ´Ù (ÃÖÀû °æ·Î´Â
¸¦ Áö³ª°£´Ù°í °¡Á¤Çß°í, Àû¾îµµ ÇϳªÀÇ ÀÚ½Ä ³ëµå·Î À̾îÁú °ÍÀ̹ǷÎ). ±×¸®°í
A* ´Â
±îÁöÀÇ ÃÖÀû °æ·Î¸¦ ãÀº °ÍÀÌ´Ù. ¿Ö³ÄÇϸé
±îÁö ´õ ³ªÀº °æ·Î°¡ ÀÖ´Ù¸é ±× °æ·Î´Â ¸ñÇ¥±îÁöµµ ´õ ³ªÀº °æ·Î°¡ µÇ±â ¶§¹®ÀÌ´Ù
(À̰ÍÀº A* °¡ ãÀº
À» Åë°úÇÏ´Â °æ·Îº¸´Ù ´õ ³ªÀº °æ·Î´Â ¾ø´Ù´Â °¡Á¤¿¡ À§¹èµÈ´Ù). µû¶ó¼ ÀÌ °æ¿ì¿¡´Â
¸¦
¹øÂ° ´Ü°è¿¡¼ »õ·Î¿î
¶ó°í Çϸé
¶ó´Â Ư¼ºÀ» Á¦¿ÜÇϰí´Â ±Í³³ ´Ü°è°¡ ¸ðµÎ Áõ¸íµÈ °ÍÀÌ´Ù.
ÀÌÁ¦ ¸¶Áö¸· Ư¼ºÀ»
Ž»öÀÌ Á¾·áµÉ ¶§±îÁöÀÇ ¸ðµç ´Ü°è ¿¡ ´ëÇÏ¿© Áõ¸íÇÏÀÚ. ÃÖÀû °æ·Î»ó¿¡ ÀÖ°í, A* °¡ ±× ³ëµå±îÁöÀÇ ÃÖÀû
°æ·Î¸¦ ãÀº ¸ðµç ³ëµå
¿¡ ´ëÇÏ¿© ´ÙÀ½ÀÌ ¼º¸³ÇÑ´Ù.
(Á¤ÀÇ¿¡ ÀÇÇØ)
(
À̰í
À̹ǷÎ)
(Á¤ÀÇ¿¡
ÀÇÇØ
À̹ǷÎ)
(
°¡ ÃÖÀû °æ·Î»ó¿¡ ÀÖÀ¸¹Ç·Î
)
ÀÌ·Î½á º¸Á¶Á¤¸®°¡ ¿ÏÀüÈ÷ Áõ¸íµÇ¾ú´Ù.
ÀÌÁ¦ °è¼ÓÇØ¼ Á¤¸®¸¦ Áõ¸íÇϱâ À§ÇØ, ¸ÕÀú ¸ñÇ¥±îÁö °æ·Î°¡ ÀÖ´Ù¸é A* ´Â ¹Ýµå½Ã Á¾·áµÈ´Ù´Â °ÍÀ» Áõ¸íÇϰí, ¸ñÇ¥±îÁöÀÇ ÃÖÀû °æ·Î¸¦ ã°í Á¾·áÇÑ´Ù´Â °ÍÀ» Áõ¸íÇÏÀÚ.
A* ´Â ¹Ýµå½Ã Á¾·áµÈ´Ù : Á¾·áµÇÁö
¾Ê´Â´Ù°í °¡Á¤ÇØ º¸ÀÚ. ±×·¸´Ù¸é A* ´Â OPEN ¿¡ ÀÖ´Â
³ëµåµéÀ» °è¼ÓÇØ¼ È®ÀåÇÒ °ÍÀ̰í, °á±¹¿¡´Â ¾î¶² À¯ÇÑÇÑ ±íÀÌ ÇѰ踦 Á¤Çصµ
Ž»öÆ®¸®¿¡¼ ±×º¸´Ù ±íÀÌ ÀÖ´Â ³ëµå¸¦ È®ÀåÇÏ°Ô µÉ °ÍÀÌ´Ù. ¿Ö³ÄÇϸé Ž»öÇÒ
±×·¡ÇÁ°¡ À¯ÇÑÇÑ ºÐ±â °è¼ö¸¦ °¡Áö°í ÀÖ´Ù°í °¡Á¤Ç߱⠶§¹®ÀÌ´Ù. ¸ðµç ¾ÆÅ©ÀÇ
°ªÀÌ º¸´Ù Å©±â ¶§¹®¿¡, OPEN ¿¡ ÀÖ´Â ¸ðµç ³ëµåÀÇ
(µû¶ó¼
µµ) °ªÀÌ °á±¹
¸¦ ³Ñ°Ô µÈ´Ù. ÇÏÁö¸¸ À̰ÍÀº º¸Á¶Á¤¸®¿¡ À§¹èµÈ´Ù.
A* ´Â ÃÖÀû °æ·Î¸¦ ã°í Á¾·áÇÑ´Ù
: A* ´Â ¹Ýµå½Ã ´Ü°è 3 (OPEN ÀÌ ºó °æ¿ì) ¶Ç´Â ´Ü°è
5 (¸ñÇ¥ ³ëµå¸¦ ãÀº °æ¿ì)¿¡¼ Á¾·áÇÑ´Ù. ´Ü°è 3 Àº ¸ñÇ¥ ³ëµå°¡ Á¸ÀçÇÏÁö
¾Ê´Â ±×·¡ÇÁ¿¡¼¸¸ ¹ß»ýÇϴµ¥, Á¤¸®¿¡¼´Â ¸ñÇ¥ ³ëµå°¡ ÀÖ´Â °æ¿ì¿¡¸¸ ¸ñÇ¥±îÁöÀÇ
ÃÖÀû °æ·Î¸¦ ã´Â´Ù°í ÇÏ¿´´Ù. µû¶ó¼ A* °¡ ¸ñÇ¥ ³ëµå¸¦ ã°í
Á¾·áÇÏ´Â °æ¿ì¸¸ »ý°¢ÇÏÀÚ. ÀÎ ÃÖÀû ¸ñÇ¥
ÀÌ ÀÖÀ» ¶§, Ž»öÀÌ
ÀÎ ÃÖÀûÀÌ ¾Æ´Ñ ¸ñÇ¥
¸¦ ã°í Á¾·áÇÑ´Ù°í ÇÏÀÚ (±×¸² 5 ÂüÁ¶).
¿¡¼ Ž»öÀÌ Á¾·áµÇ¾úÀ» ¶§,
°¡ µÈ´Ù. ±×·¯³ª º¸Á¶Á¤¸®¿¡ ÀÇÇÏ¿© A* °¡
¸¦ È®ÀåÇϱâ Á÷Àü¿¡
ÀÎ ÃÖÀû °æ·Î»óÀÇ ³ëµå
°¡ OPEN ¿¡ ÀÖ¾úÀ» °ÍÀÌ´Ù. ±×·±µ¥ A* ´Â Ç×»ó
°ªÀÌ ÃÖ¼ÒÀÎ ³ëµå¸¦ ¼±ÅÃÇϸç,
À̹ǷÎ, Ž»ö°úÁ¤¿¡¼
°¡ ¸ÕÀú ¼±ÅÃµÉ ¼ö´Â ¾ø´Ù.
ÀÌ·¸°Ô ÇÏ¿© Á¤¸®°¡ ¿ÏÀüÈ÷ Áõ¸íµÇ¾ú´Ù. ¸ñÇ¥±îÁöÀÇ
ÃÖÀû °æ·Î¸¦ ã´Â °ÍÀ» º¸ÀåÇÏ´Â ¾Ë°í¸®ÁòÀ» Çã¿ë °¡´É (admissible) ÇÏ´Ù°í ÇÑ´Ù.
µû¶ó¼ Á¤¸®¿¡¼ÀÇ ¼¼ °¡Áö Á¶°ÇÀ» ¸¸Á·Çϸé A* ´Â Çã¿ë °¡´ÉÇÏ´Ù. ³ª¾Æ°¡
¸¦ °ú´ëÆò°¡ (overestimate) ÇÏÁö ¾Ê´Â ¸ðµç
¸¦ Çã¿ë °¡´ÉÇÏ´Ù°í ÇÑ´Ù. Áö±ÝºÎÅÍ´Â A* ¸¦ Àû¿ëÇÑ´Ù°í ÇÒ ¶§ Ç×»ó
Á¤¸®¿¡ ÀÖ´Â ¼¼ °¡Áö Á¶°ÇÀÌ ¸¸Á·µÈ´Ù°í °¡Á¤ÇÑ´Ù.
¸¸ÀÏ µÎ °³ÀÇ ¼·Î ´Ù¸¥ A* ¾Ë°í¸®Áò
A*2 ¿Í A*1 °¡ ¸ñÇ¥ ¿ÜÀÇ ¸ðµç ³ëµå¿¡
´ëÇÏ¿© ÀÎ Á¡¸¸ ´Ù¸£´Ù¸é, A*2 °¡ A*1 º¸´Ù
Á¤º¸°¡ ¸¹´Ù (more informed) °í ÇÑ´Ù. ¿©±â¿¡ ´ëÇÑ ´ÙÀ½ÀÇ Á¤¸®´Â Áõ¸íÇÏÁö ¾Ê°Ú´Ù
([Hart, Nilsson, & Raphael 1968, Hart, Nilsson, & Raphael 1972, Nilsson
1980] À» ÂüÁ¶).
Á¤¸® 2
A*2 °¡ A*1 º¸´Ù
Á¤º¸°¡ ¸¹´Ù¸é (more informed), ¿¡¼ ¸ñÇ¥ ³ëµå±îÁö °æ·Î°¡ ÀÖ´Â ¸ðµç ±×·¡ÇÁ¿¡ ´ëÇØ¼, Ž»öÀÌ Á¾·áµÇ¾úÀ» ¶§
A*2 ¿¡ ÀÇÇØ È®ÀåµÈ ³ëµå´Â A*1 ¿¡
ÀÇÇØ¼µµ È®ÀåµÈ´Ù.
Áï A*1 Àº ÃÖ¼ÒÇÑ A*2 °¡
È®ÀåÇÏ´Â °Íº¸´Ù ¸¹Àº ³ëµå¸¦ È®ÀåÇϸç, µû¶ó¼ Á¤º¸°¡ ¸¹Àº ¾Ë°í¸®ÁòÀÎ A*2 °¡
ÀϹÝÀûÀ¸·Î ´õ È¿À²ÀûÀÌ´Ù. ±×·¯¹Ç·Î ½ÇÁ¦ ¸¦ ³ÑÁö ¾ÊÀ¸¸é¼ (Çã¿ë¼ºÀ» °®±â À§Çؼ),
¿¡ °¡Àå ±ÙÁ¢ÇÑ °ªÀ» °®´Â
ÇÔ¼ö¸¦ ã´Â °ÍÀÌ ÁÁ´Ù (Ž»öÀÇ È¿À²À» ³ôÀ̱â À§ÇÏ¿©). ¹°·Ð, Àüü Ž»ö
È¿À²À» ÃøÁ¤ÇÏ´Â µ¥ À־Â
¸¦ °è»êÇÏ´Â ºñ¿ëµµ °í·ÁÇØ¾ß¸¸ ÇÑ´Ù. °¡Àå Á¤º¸°¡ ¸¹Àº ¾Ë°í¸®ÁòÀº
ÀÎ °æ¿ìÀ̰ÚÁö¸¸, ÀϹÝÀûÀ¸·Î ÀÌ·±
ÇÔ¼ö´Â ¼öÇàÇÏ·Á°í Çϴ Ž»ö ±× ÀÚü¸¦ ¿Ï·áÇÔÀ¸·Î½á¸¸ ¾ò¾îÁú ¼ö ÀÖ´Â
°ÍÀÌ´Ù!
±×¸² 6 Ž»ö ¾Ë°í¸®Áò »çÀÌÀÇ °ü°è
±×¸² 6 Àº Áö±Ý±îÁö ³íÀÇÇß´ø Ž»ö ¾Ë°í¸®Áòµé
»çÀÌÀÇ °ü°è¸¦ Á¤¸®ÇÑ °ÍÀÌ´Ù. ¸ðµç ³ëµå¿¡ ´ëÇÏ¿© ÀÌ¸é ±ÕÀϺñ¿ë Ž»ö (uniform-cost search) ÀÌ µÈ´Ù (Ž»öÀº °°Àº °ªÀÇ µî½É¼±À»
µû¶ó ÁøÇàµÈ´Ù).
ÀÌ¸é °°Àº ±íÀÌÀÇ µî½É¼±À» µû¶ó ÁøÇàµÇ´Â ³Êºñ¿ì¼± Ž»ö (breadth-first search)
ÀÌ µÈ´Ù. ±ÕÀϺñ¿ë Ž»öÀ̳ª ³Êºñ¿ì¼± Ž»ö ¸ðµÎ A* ÀÇ Æ¯¼öÇÑ °æ¿ì
À̹ǷΠ¿ª½Ã Çã¿ë °¡´É (admissible) ÇÏ´Ù.
°¡
ÀÇ ÀÚ½Ä ³ëµåÀÎ ³ëµå ½ÖÀ» »ý°¢ÇØ º¸ÀÚ. Ž»ö ±×·¡ÇÁ ¾ÈÀÇ ¸ðµç ³ëµå ½ÖÀÌ ´ÙÀ½ÀÇ
Á¶°ÇÀ» ¸¸Á·Çϸé Àϰü¼º Á¶°Ç (consistency condition)À» ¸¸Á·ÇÑ´Ù°í ÇÑ´Ù.
¿©±â¼ ´Â
¿¡¼
±îÁö ¾ÆÅ©ÀÇ °ªÀÌ´Ù. ÀÌ ½ÄÀ» ´ÙÀ½°ú °°ÀÌ ¾µ ¼öµµ ÀÖ´Ù.
±×¸² 7 Àϰü¼º Á¶°Ç
ÀÌ Á¶°ÇÀº, Ž»ö ±×·¡ÇÁÀÇ ¾î¶² °æ·Î¸¦ µû¶ó¼µµ,
¸ñÇ¥±îÁöÀÇ (³²Àº) ÃÖÀû°ªÀÇ ÃßÁ¤Ä¡´Â ±× °æ·Î»óÀÇ ¾ÆÅ©°ª ÀÌ»óÀ¸·Î °¨¼ÒÇÏÁö´Â ¾Ê´Â´Ù´Â
°ÍÀÌ´Ù. Áï, ÈÞ¸®½ºÆ½ ÇÔ¼ö´Â ¾ÆÅ©ÀÇ ¾Ë·ÁÁø °ªÀ» °í·ÁÇÒ ¶§ ±¹ºÎÀûÀÎ Àϰü¼ºÀ» °®´Â´Ù´Â
°ÍÀÌ´Ù. Àϰü¼º Á¶°ÇÀº ±×¸² 7¿¡ ÀÖ´Â °Í°ú °°ÀÌ ÀÏÁ¾ÀÇ »ï°¢ ºÎµî½Ä (triangle inequality)
À̶ó°í »ý°¢ÇÒ ¼ö ÀÖ´Ù.
¶ÇÇÑ Àϰü¼º Á¶°ÇÀº Ž»öÆ®¸® ³ëµå¿¡¼ÀÇ °ªÀÌ ½ÃÀÛ ³ëµå¿¡¼ ¸Ö¾îÁü¿¡ µû¶ó ´ÜÁ¶ÀûÀ¸·Î Áõ°¡ÇÑ´Ù (monotonically nondecreasing)
´Â °ÍÀ» ¾Ï½ÃÇÑ´Ù.
¿Í
¸¦ A* ¿¡ ÀÇÇØ »ý¼ºµÈ Ž»öÆ®¸®ÀÇ µÎ ³ëµå·Î½á
°¡
ÀÇ ÀÚ½Ä ³ëµå¶ó°í ÇÏÀÚ. ¸¸ÀÏ Àϰü¼º Á¶°ÇÀÌ ¸¸Á·µÈ´Ù¸é
ÀÌ´Ù. ´ÙÀ½ÀÇ Àϰü¼º Á¶°ÇÀ¸·ÎºÎÅÍ ÀÌ »ç½ÇÀ» Áõ¸íÇÏÀÚ.
¾çº¯¿¡ ¸¦ ´õÇϸé,
±×·±µ¥ ÀÌ´Ù (
¿¡
¸¦ ÅëÇÏ´Â °Íº¸´Ù ÀÛÀº °ªÀ» °®´Â °æ·Î¸¦ µû¶ó µµ´ÞÇÒ ¼öµµ ÀÖÀ¸¹Ç·Î
°¡ ÀÌ °ªº¸´Ù ÀÛÀ» ¼öµµ ÀÖÁö ¾ÊÀ»±î ÇÏ°í »ý°¢ÇÒÁö ¸ð¸¥´Ù. ±×·¯³ª ±×·¸´Ù¸é
´Â Ž»öÆ®¸®¿¡¼
ÀÇ ÀÚ½Ä ³ëµå°¡ ¾Æ´Ò °ÍÀÌ´Ù). µû¶ó¼,
°¡ µÈ´Ù.
ÀÌ·± ÀÌÀ¯ ¶§¹®¿¡ ( ¿¡ ´ëÇÑ) Àϰü¼º Á¶°ÇÀ» (
¿¡ ´ëÇÑ) ´ÜÁ¶¼º Á¶°Ç (monotone condition) À̶ó°íµµ ÇÑ´Ù.
Àϰü¼º Á¶°Ç°ú
°ü·Ã ÀÖ´Â Áß¿äÇÑ Á¤¸®¸¦ ¼Ò°³ÇÑ´Ù ([Hart, Nilsson, & Raphael 1968]).
±×¸² 8 Á¤¸® 3 ÀÇ Áõ¸í¿¡ »ç¿ëµÈ ±×·¡ÇÁ
Á¤¸® 3
¿¡ ´ëÇÑ Àϰü¼º Á¶°ÇÀÌ ¸¸Á·µÈ´Ù¸é, A* °¡ ¾î¶² ³ëµå
À» È®ÀåÇϸé
±îÁöÀÇ ÃÖÀû °æ·Î°¡ ÀÌ¹Ì ¹ß°ßµÈ °ÍÀÌ´Ù.
Áõ ¸í ¡¦ A* °¡ ¾Ï½ÃÀûÀÎ
±×·¡ÇÁ ¿¡¼ ½ÃÀÛ ³ëµå
ºÎÅÍ ¸ñÇ¥ ³ëµå±îÁöÀÇ ÃÖÀû °æ·Î¸¦ Ž»öÇÏ´Â µ¥ ÀÖ¾î¼ ¾î¶² ³ëµå
À» ¸· È®ÀåÇÏ·Á ÇÑ´Ù°í ÇÏÀÚ.
¸¦
¿¡¼
±îÁöÀÇ ÃÖÀû °æ·Î¸¦ ±¸¼ºÇÏ´Â ³ëµå ¿ (sequence) À̶ó°í ÇÏÀÚ.
ÀÌ
Áß¿¡¼ A* °¡ ¸¶Áö¸·À¸·Î È®ÀåÇÑ ³ëµå¶ó°í ÇÏÀÚ (±×¸² 8À» º¸¶ó).
ÀÌ
Áß¿¡¼ ¸¶Áö¸·À¸·Î È®ÀåµÈ ³ëµåÀ̹ǷÎ,
Àº OPEN ¿¡ ÀÖÀ» °ÍÀ̰í, µû¶ó¼ ´ÙÀ½ ¹ø¿¡ È®ÀåµÉ Èĺ¸ Áß ÇϳªÀÏ °ÍÀÌ´Ù.
(
±îÁöÀÇ ÃÖÀû °æ·Î) ¿¡ ÀÖ´Â ¸ðµç ³ëµå
¿Í ±× ÀÚ½Ä ³ëµå
¿¡ ´ëÇØ¼
À̰í,
Àϰü¼º Á¶°ÇÀÌ ¸¸Á·µÇ¸é
ÀÌ´Ù.
°ü°èÀÇ ÀÌÇ༺ (transitivity) ¿¡ ÀÇÇÏ¿©,
ÀÎ
»óÀÇ ¸ðµç
¿Í
¿¡ ´ëÇÏ¿©
°¡ µÈ´Ù. ƯÈ÷, A* °¡ ±îÁöÀÇ ÃÖÀû °æ·Î¸¦ ã¾ÒÀ¸¹Ç·Î
À̶ó Çϸé
ÀÌ´Ù. ±×·¯³ª A* °¡ ³ëµå ÀÌ ¾Æ´Ñ ³ëµå
À» È®ÀåÇÏ·Á°í ÇϹǷΠ´ÙÀ½ÀÌ ¼º¸³ÇÒ °ÍÀÌ´Ù.
±×·¯³ª À̹Ì
ÀÌ µÈ´Ù. ±×·¯³ª ¸¦ °è»êÇÏ´Â ¹æ¹ý¿¡ µû¸£¸é
À̹ǷÎ,
ÀÌ´Ù.
À̰ÍÀ¸·Î À̰ųª, ¶Ç´Â ÀÌ¹Ì ³ëµå
±îÁöÀÇ ´Ù¸¥ ÃÖÀû °æ·Î¸¦ ã¾Ò¾î¾ß¸¸ ÇÔÀ» º¸¿´À¸¸ç, Áõ¸íÀÌ ¿Ï·áµÇ¾ú´Ù.
Àϰü¼º Á¶°ÇÀº ¸¸Á·µÇ±â¸¸ Çϸé A* °¡
(´Ü°è 7 ¿¡¼) ÀüÇô Æ÷ÀÎÅ͸¦ º¯°æÇÒ Çʿ䰡 ¾ø°Ô µÇ¹Ç·Î ¸Å¿ì Áß¿äÇÑ Á¶°ÇÀÌ´Ù.
ÀÌ·¸°Ô µÇ¸é ±×·¡ÇÁÀÇ Å½»öÀº Æ®¸®ÀÇ Å½»ö°ú Â÷À̰¡ ¾ø°Ô µÈ´Ù.
Àϰü¼º Á¶°ÇÀÌ
¸¸Á·µÇ¸é A* ÀÇ Çã¿ë¼º¿¡ ´ëÇÏ¿© ´ÙÀ½°ú °°Àº ¹æ¹ýÀ¸·Î ´Ü¼øÇϰí Á÷°üÀûÀÎ
°á·ÐÀ» ³»¸± ¼ö ÀÖ´Ù.
1. ¿¡ ´ÜÁ¶¼ºÀÌ ÀÖÀ¸¹Ç·Î Ž»öÀº
°ªÀÌ Áõ°¡ÇÏ´Â ¹æÇâÀ¸·Î µî½É¼±À» µû¶ó ÁøÇàÇÑ´Ù.
2. µû¶ó¼ óÀ½À¸·Î ¼±ÅõǴÂ
¸ñÇ¥ ³ëµå°¡ ÃÖ¼ÒÀÇ °ªÀ» °®´Â ¸ñÇ¥ ³ëµå°¡ µÉ °ÍÀÌ´Ù.
3. ¸ðµç ¸ñÇ¥ ³ëµå ¿¡ ´ëÇÏ¿©
ÀÌ´Ù (¸¸ÀÏ
ÇÔ¼ö°¡ Àϰü¼ºÀÌ ÀÖÀ¸¸é, ±× °ªÀº ¶ÇÇÑ ½ÇÁ¦
ÇÔ¼ö°ªÀ» ³ÑÁö ¾Ê´Â´Ù´Â »ç½Ç[Pearl 1984, p.83] À» ÀÌ¿ëÇÏ¿´´Ù).
4. µû¶ó¼ óÀ½À¸·Î ¼±ÅõǴÂ
¸ñÇ¥ ³ëµå°¡ ÃÖ¼ÒÀÇ °ªÀ» °®´Â ¸ñÇ¥ ³ëµå°¡ µÉ °ÍÀÌ´Ù.
5. Á¤¸® 3 ¿¡ µû¶ó, ¾î¶²
¸ñÇ¥ ³ëµå °¡ È®ÀåµÇ¸é
±îÁöÀÇ ÃÖÀû °æ·Î°¡ ÀÌ¹Ì ¹ß°ßµÈ °ÍÀÌ´Ù. Áï
ÀÌ´Ù.
6. µû¶ó¼ óÀ½À¸·Î ¼±ÅõǴ ¸ñÇ¥ ³ëµå°¡ ÃÖÀû °æ·Î·Î µµ´ÞÇÑ ¸ñÇ¥ ³ëµå°¡ µÈ´Ù.
¸¹Àº ÈÞ¸®½ºÆ½ ÇÔ¼öµéÀÌ Àϰü¼º Á¶°ÇÀ» ¸¸Á·ÇÑ´Ù.
¿¹¸¦ µé¾î, 8 ÆÛÁñ¿¡¼ÀÇ "Á¦ÀÚ¸®¿¡ ÀÖÁö ¾ÊÀº ŸÀÏ" ÇÔ¼öµµ ÀÌ Á¶°ÇÀ»
¸¸Á·ÇÑ´Ù. ÈÞ¸®½ºÆ½ ÇÔ¼ö°¡ Àϰü¼º Á¶°ÇÀ» ¸¸Á·ÇÏÁö´Â ¾ÊÁö¸¸ Çã¿ë °¡´É (admissible)
ÇÏ´Ù¸é, (Mérõ[Mérõ 1984] °¡ Á¦¾ÈÇÑ ¾ÆÀ̵ð¾î¸¦ »ç¿ëÇÏ¿©)
±× ÇÔ¼ö¸¦ Àϰü¼º Á¶°ÇÀ» ¸¸Á·ÇÏ´Â °ÍÀ¸·Î (Ž»ö µµÁß¿¡) Á¶Á¤ÇÒ ¼ö ÀÖ´Ù. °¡·É,
A* ÀÇ ¸ðµç ´Ü°è¿¡¼ ¸· È®ÀåµÈ ³ëµå ÀÇ ÀÚ½Ä ³ëµåµéÀÇ
°ªÀ» °Ë»çÇÑ´Ù°í ÇÏÀÚ. À̵é Áß
°ªÀÌ
¿¡¼
À¸·ÎºÎÅÍ ÀڽűîÁöÀÇ ¾ÆÅ©°ªÀ» »« °Íº¸´Ù ÀÛÀº ³ëµå°¡ ÀÖÀ¸¸é,
°ªÀ»
¿¡¼ ¾ÆÅ©°ªÀ» »« °ªÀ¸·Î (Ž»ö µµÁß¿¡) Á¶Á¤ÇÑ´Ù (CLOSED ¿¡ ÀÖ´Â ³ëµåÀÇ
°ªÀÌ ÀÌ¿Í °°ÀÌ º¯°æµÇ¸é ±× ³ëµå¸¦ OPEN À¸·Î ´Ù½Ã ¿Å°Ü¾ß ÇÒ
¼öµµ ÀÖ´Ù. ÀÌ·¯ÇÑ Á¶Á¤À» ÇÏ¿©µµ ¾Ë°í¸®ÁòÀÌ Çã¿ë °¡´ÉÇÏ´Ù´Â °ÍÀ» Áõ¸íÇÏ´Â °ÍÀº
µ¶ÀÚÀÇ ¸òÀ¸·Î ³²°ÜµÎ°Ú´Ù).
¹«Á¤º¸ Ž»ö¿¡¼ ³Êºñ¿ì¼± Ž»öÀÇ ¸Þ¸ð¸® ¿ä±¸·®Àº Ž»ö°ø°£¿¡¼ ¸ñÇ¥ ³ëµåÀÇ ±íÀÌ¿¡ ºñ·ÊÇÏ¿© Áö¼öÀûÀ¸·Î Áõ°¡ÇÑ´Ù°í ÇÏ¿´´Ù. ÁÁÀº ÈÞ¸®½ºÆ½ÀÌ ºÐ±â °è¼ö¸¦ °¨¼Ò½Ã۱â´Â ÇÏÁö¸¸, ÈÞ¸®½ºÆ½ Ž»öµµ °°Àº ´ÜÁ¡À» °¡Áö°í ÀÖ´Ù. ¹«Á¤º¸ Ž»ö¿¡¼ ¼Ò°³ÇÑ ¹Ýº¹Àû ±íÀÌÁõ°¡ Ž»ö (iterative deepening search) À» ÀÌ¿ëÇÏ¸é ¸Þ¸ð¸® ¿ä±¸·®ÀÌ ¸ñÇ¥ ³ëµåÀÇ ±íÀÌ¿¡ ºñ·ÊÇÏ¿© ¼±ÇüÀûÀ¸·Î Áõ°¡ÇÏ¸é¼ ÃÖ´Ü °æ·Î¸¦ ãÀ» ¼ö ÀÖ´Ù. [Korf 1985] °¡ Á¦¾ÈÇÑ ¹Ýº¹Àû ±íÀÌÁõ°¡ A* (iterative-deepening A*, IDA*) ¹æ¹ýÀ» »ç¿ëÇϸé ÈÞ¸®½ºÆ½ Ž»ö¿¡¼µµ ºñ½ÁÇÑ È¿°ú¸¦ ¾òÀ» ¼ö ÀÖ´Ù. IDA* ¸¦ º´·Ä ¾Ë°í¸®ÁòÀ¸·Î ±¸ÇöÇϸé È¿À²À» ´õ¿í ³ôÀÏ ¼öµµ ÀÖ´Ù ([Powley, Ferguson, & Korf 1993] À» ÂüÁ¶).
ÀÌ ¹æ¹ýÀº º¸ÅëÀÇ
¹Ýº¹Àû ±íÀÌÁõ°¡ Ž»ö°ú ºñ½ÁÇÑ ¹æ½ÄÀ¸·Î ¼öÇàµÈ´Ù. ù ¹ø Ž»ö¿¡¼´Â °ª ÇѰè (cost
cut-off) ¸¦ ·Î ¼³Á¤ÇÑ´Ù.
Àº ½ÃÀÛ ³ëµåÀÌ´Ù. ¾Ë´Ù½ÃÇÇ, ¸ñÇ¥±îÁöÀÇ ÃÖÀû °æ·Î°ªÀº ÀÌ °ªº¸´Ù Å©°Å³ª °°´Ù
(¸¸ÀÏ
ÀÌ¸é °°°Ô µÈ´Ù.
À̹ǷΠ´õ ÀÛÀ» ¼ö´Â ¾ø´Ù). Ž»öÀº ¾î¶² ³ëµå¸¦ È®ÀåÇßÀ» ¶§ ÀÚ½Ä ³ëµåÀÇ
°ªÀÌ ÇѰ谪À» ³ÑÀ¸¸é µÇÃßÀû (backtracking) ÇÏ¸é¼ ±íÀ̿켱 ÇüÅ·Î
ÁøÇàÇÑ´Ù. ÀÌ ±íÀ̿켱 Ž»öÀÌ ¸ñÇ¥ ³ëµå¸¦ ã°í ³¡³´Ù¸é, ºÐ¸íÈ÷ ¸ñÇ¥±îÁöÀÇ ÃÖ´Ü
°æ·Î¸¦ ãÀº °ÍÀÌ´Ù. ¸¸ÀÏ ±×·¸Áö ¾ÊÀ¸¸é, ÃÖÀû °æ·ÎÀÇ °ªÀº ÀÌ ÇѰ谪º¸´Ù Å©´Ù°í
ÇÒ ¼ö ÀÖ´Ù. µû¶ó¼ ÇѰ谪À» Áõ°¡½ÃŰ°í ´Ù½Ã ±íÀ̿켱 Ž»öÀ» ½ÃÀÛÇÑ´Ù. ÃÖÀû °æ·ÎÀÇ
´ÙÀ½À¸·Î °¡´ÉÇÑ °ªÀº ¾ó¸¶Àΰ¡? ±× °ªÀº ÀÌÀüÀÇ ±íÀ̿켱 Ž»ö¿¡¼ ¹æ¹®Çß´ø (ÇÏÁö¸¸
È®ÀåµÇÁö´Â ¾ÊÀº) ³ëµåµéÀÇ
°ª Áß ÃÖ¼Ò°ªº¸´Ù Å©°Å³ª °°À» °ÍÀÌ´Ù.
°ªÀÌ ÃÖ¼ÒÀÎ ³ëµå°¡ ÃÖÀû °æ·Î»ó¿¡ ÀÖÀ» ¼ö ÀÖ´Â °ÍÀÌ´Ù (ÀÌÀüÀÇ ÇѰ谪°ú °°Àº
°ªÀ» °®´Â ÃÖÀû °æ·Î°¡ ¾ø´Ù´Â °ÍÀº ÀÌ¹Ì ¾Ë°í ÀÖ´Ù). ÀÌ
ÀÇ ÃÖ¼Ò°ªÀÌ ´ÙÀ½ ¹ø ±íÀ̿켱 Ž»ö¿¡¼ ÇѰ谪À¸·Î »ç¿ëµÈ´Ù. Á÷°üÀûÀ¸·Î IDA* °¡
¸ñÇ¥±îÁöÀÇ ÃÖ´Ü °æ·Î¸¦ ã´Â °ÍÀ» º¸ÀåÇÑ´Ù´Â °ÍÀ» ½±°Ô ¾Ë ¼ö ÀÖ´Ù ([Korf 1985]
¿Í [Korf 1993] ¿¡ ¿©±â¿¡ ´ëÇÑ Áõ¸íÀÌ ³ª¿Í ÀÖ´Ù. µÎ ¹øÀç ³í¹®¿¡¼´Â ´ÜÁ¶¼º
Á¶°ÇÀÌ ¸¸Á·µÇÁö ¾Ê´Â °æ¿ì¿¡ ÀÖ¾î¼ ¹Ýº¹Àû ±íÀÌ Áõ°¡ÀÇ ÇѰ迡 ´ëÇÏ¿© ³íÇϰí Àç±ÍÀû
ÃÖ»ó¿ì¼±Å½»ö (recursive best-first search) À̶ó´Â »õ·Î¿î ¾Ë°í¸®ÁòÀ» Á¦½ÃÇÏ¿´´Ù).
IDA* °¡
³ëµåÀÇ È®ÀåÀ» ¹Ýº¹ÇØ¾ß ÇÏÁö¸¸ (º¸ÅëÀÇ ¹Ýº¹Àû ±íÀÌÁõ°¡¿Í ¸¶Âù°¡Áö·Î) ¸Þ¸ð¸® ¿ä±¸·®ÀÇ
°¨¼Ò¿Í ±íÀ̿켱 Ž»öÀÇ ±¸Çö»óÀÇ È¿À²¼º (³Êºñ¿ì¼± Ž»ö¿¡ ºñÇÏ¿©) °ú °ü·ÃÇÏ¿©
Æ®·¹À̵å¿ÀÇÁ°¡ ÀÖ´Â °ÍÀÌ´Ù. ±×·±µ¥ Ž»ö°ø°£¿¡¼ ¸ðµç ³ëµåÀÇ °ªÀÌ ´Ù¸¥ °æ¿ì¿¡´Â ¾î¶² ÀÏÀÌ ¹ß»ýÇÏ´ÂÁö »ý°¢ÇØ º¸ÀÚ. ¹Ýº¹ÀÇ È¸¼ö°¡
°ªÀÌ ÃÖÀû °æ·ÎÀÇ °ªº¸´Ù ÀÛÀº ¸ðµç ³ëµåÀÇ ¼ö¿Í °°°Ô µÈ´Ù (Çã¿ë¼ºÀ» Æ÷±âÇÏ´Â
´ë°¡·Î ÀÌ ¹®Á¦¸¦ °³¼±ÇÒ ¼ö ÀÖ´Â ¹æ¹ýµéÀÌ ÀÖ´Ù. ¾î¶»°Ô ÇÏ¸é µÇ´ÂÁö »ý°¢ÇØ º¸´Â
°ÍÀº µ¶ÀÚÀÇ ¸òÀ¸·Î ³²°ÜµÎ°Ú´Ù)!
Korf °¡ Á¦¾ÈÇÑ Àç±ÍÀû ÃÖ»ó¿ì¼± Ž»ö (recursive
best-first search), RBFS ([kORF 1993]), À̶ó´Â Ž»ö ¹æ¹ýÀº IDA* º¸´Ù
¾à°£ ¸¹Àº ¸Þ¸ð¸®¸¦ »ç¿ëÇÏÁö¸¸ IDA* ¿¡ ºñÇÏ¿© ÀûÀº ¼öÀÇ ³ëµå¸¦ ¸¸µé¾î³½´Ù.
¾î¶² ³ëµå ÀÌ È®ÀåµÉ ¶§ RBFS ´Â
ÀÇ ÀÚ½Ä ³ëµåµéÀÇ
°ªÀ» °è»êÇÑ ´ÙÀ½,
°ú
ÀÇ ¸ðµç Á¶»ó ³ëµåµéÀÇ
°ªÀ» ´Ù½Ã °è»êÇÑ´Ù. ÀÌ Àç°è»ê °úÁ¤À»
°ªÀÇ Àü´Þ (backing up) À̶ó°í ÇÑ´Ù. Àü´Þ °úÁ¤Àº ´ÙÀ½°ú °°ÀÌ ¼öÇàµÈ´Ù.
Áö±Ý È®ÀåµÈ ³ëµåÀÇ ÀÚ½Ä ³ëµåµéÀÇ Àü´Þ°ªÀº ±× ³ëµåÀÇ
°ªÀÌ´Ù. ÀÚ½Ä ³ëµåµéÀÌ
ÀÎ ³ëµå
ÀÇ Àü´Þ°ª
Àº ´ÙÀ½°ú °°´Ù.
¿©±â¼ ´Â ³ëµå
ÀÇ Àü´Þ°ªÀÌ´Ù.
¸¸ÀÏ (Áö±Ý È®ÀåµÈ) ³ëµå ÀÇ ÀÚ½Ä ³ëµå Áß Çϳª°¡ ¸ðµç OPEN ¿¡ ÀÖ´Â ³ëµåµé Áß¿¡¼ °¡Àå ÀÛÀº
°ªÀ» °¡Áö°í ÀÖ´Ù¸é ±× ³ëµå¸¦ ´ÙÀ½À¸·Î È®ÀåÇÑ´Ù. ±×·¸Áö ¾Ê°í ³ëµå
ÀÇ ÀÚ½Ä ³ëµå°¡ ¾Æ´Ñ OPEN ¿¡ ÀÖ´Â ´Ù¸¥ ³ëµå
°¡ ÃÖ¼ÒÀÇ
°ªÀ» °¡Áö°í ÀÕ´Ù°í ÇÏÀÚ. ÀÌ °æ¿ì ¾Ë°í¸®ÁòÀº
°ú
ÀÇ °¡Àå °¡±î¿î °øÅë Á¶»ó
±îÁö µÇÃßÀûÇÑ´Ù.
À»
ÂÊÀ¸·Î °¡´Â °æ·Î»ó¿¡ ÀÖ´Â
ÀÇ ÀÚ½Ä ³ëµå¶ó°í ÇÏÀÚ. RBFS ´Â
À» ·çÆ®·Î ÇÏ´Â ¼ºêÆ®¸®¸¦ OPEN ¿¡¼ Á¦°ÅÇϰí,
ÀÇ
°ªÀ» Àü´Þ°ªÀ¸·Î º¯°æÇÏ¿© OPEN ¿¡ ³ÖÀº µÚ, ÃÖ¼ÒÀÇ
°ªÀ» °¡Áö°í ÀÖ´Â
¿¡¼ºÎÅÍ Å½»öÀ» °è¼ÓÇÑ´Ù.
ÀÌ ¾Ë°í¸®ÁòÀÇ ÁÖ¿ä °³³äÀ» ±×¸² 9 ¿¡ ³ªÅ¸³»¾ú´Ù.
Ž»öÆ®¸®´Â Ç×»ó ÇϳªÀÇ °æ·Î¿Í ±× °æ·Î»ó¿¡ ÀÖ´Â ³ëµåµéÀÇ ÇüÁ¦ (sibling) ³ëµåµé·Î¸¸
±¸¼ºµÈ´Ù. µû¶ó¼ ¸Þ¸ð¸® ¿ä±¸·®Àº Áö±Ý±îÁö Ž»öÇÑ ÃÖ»óÀÇ °æ·Î ±æÀÌ¿¡ ¼±ÇüÀûÀ¸·Î
ºñ·ÊÇÏ°Ô µÈ´Ù. ´Ü¸» (leaf) ³ëµåµéÀº ¸ðµÎ OPEN ¿¡ ÀÖÀ¸¸ç, Ž»öÆ®¸®ÀÇ ¸ðµç
³ëµåµéÀº Àü´ÞµÈ °ªÀ» °¡Áö°í ÀÖ´Ù.
±×¸² 9 Àç±ÍÀû ÃÖ»ó¿ì¼± Ž»ö
ÈÞ¸®½ºÆ½ ÇÔ¼öÀÇ ¼±ÅÃÀº A* ÀÇ È¿À²¼º¿¡
°áÁ¤ÀûÀÎ ¿µÇâÀ» ¹ÌÄ£´Ù. ¸¦ »ç¿ëÇϸé Çã¿ë¼ºÀº º¸ÀåµÇÁö¸¸ ±ÕÀϺñ¿ë Ž»öÀÌ µÇ¾î ÀϹÝÀûÀ¸·Î È¿À²¼ºÀÌ
¾ø´Ù.
¸¦
ÀÇ ÇÏÇѰª Áß¿¡¼ °¡Àå Å« °ªÀ¸·Î Çϸé Çã¿ë¼ºÀ» À¯ÁöÇÏ¸é¼ °¡Àå ÀûÀº ¼öÀÇ
³ëµåµéÀ» È®ÀåÇÏ°Ô µÈ´Ù. ¿¹¸¦ µé¾î 8 ÆÛÁñ¿¡¼
(
Àº Á¦ÀÚ¸®¿¡ ÀÖÁö ¾ÊÀº ŸÀÏ ¼ö) Àº
ÀÇ ÇÏÇѰªÀÌÁö¸¸, ¾î¶² ŸÀÏ ¹èÄ¡ÀÇ ³À̵µ (¸ñÇ¥±îÁö ³²Àº ½ºÅÜ ¼ö) ¿¡ ´ëÇÑ
ÁÁÀº ÃßÁ¤°ªÀ» Á¦°øÇÏÁö´Â ¸øÇÑ´Ù. º¸´Ù ³ªÀº ÃßÁ¤°ªÀº
À¸·Î¼,
Àº °¢ ŸÀÏÀÇ Á¦ÀÚ¸®·ÎºÎÅÍÀÇ (Áß°£ÀÇ Å¸ÀϵéÀº ¹«½ÃÇÑ) ¸ÇÇÏÆ° °Å¸® (Manhattan
distance) ÀÇ ÇÕÀÌ´Ù.
AI ÀÇ ÃÊâ±â¿¡ [Newell, Shaw, & Simon 1959, Newell
1964] ´Â Ž»öÀ» ¾È³»Çϱâ À§ÇØ °èȹÀ» ÀÛ¼ºÇÏ´Â °£´ÜÇÑ ¸ðµ¨À» Á¦½ÃÇÑ ¹Ù ÀÖ´Ù.
ºñ½ÁÇÑ °³³äÀ» ÁÁÀº ÈÞ¸®½ºÆ½ ÇÔ¼ö¸¦ ã´Â ¹®Á¦¿¡ Àû¿ëÇÑ °ÍÀÌ [Gaschnig 1979] ¿Í
[Pearl 1984, 4Àå] ¿¡ ±â¼úµÇ¾î ÀÖ´Ù. ¿¹¸¦ µé¾î, ŸÀÏÀÇ À̵¿¿¡ ´ëÇÑ Á¦ÇÑÀ» ÁÙÀÓÀ¸·Î½á
8 ÆÛÁñÀÇ Á¶°ÇÀ» ¿ÏȽÃų ¼ö ÀÖ´Ù. ¸¸ÀÏ °¢ ŸÀÏÀÌ ¸ñÇ¥ ÁöÁ¡±îÁö Á÷Á¢ (ÇÑ ½ºÅÜ¿¡)
¿òÁ÷ÀÏ ¼ö ÀÖ´Ù°í Çϸé, ¸ñÇ¥ »óűîÁöÀÇ ½ºÅÜ ¼ö´Â Á¦ÀÚ¸®¿¡ ÀÖÁö ¾ÊÀº ŸÀÏÀÇ ¼ö,
ÀÌ µÈ´Ù. ¾à°£ ´ú ¾ÇÈµÈ (±×·¯¹Ç·Î ´õ ÁÁÀº) ¸ðµ¨Àº ŸÀϵéÀÌ ÀÌ¹Ì ´Ù¸¥ ŸÀÏÀÌ
ÀÖ´õ¶óµµ ÀÎÁ¢ÇÑ ÀÚ¸®ÀÇ ¸ñÇ¥ ÀÚ¸®·ÎºÎÅÍÀÇ °Å¸®ÀÇ ÇÕ P(n) ÀÌ µÈ´Ù. ÀÌ·¯ÇÑ ¸ðµ¨µéÀº
»ç¶÷ÀÌ Á÷°üÀûÀ¸·Î ÃßÃøÇÏ´Â
ÇÔ¼ö¸¦ ¿¡ÀÌÀüÆ®°¡ ¾î¶»°Ô ÀÚµ¿ÀûÀ¸·Î °è»êÇØ³¾ ¼ö Àִ°¡¸¦ º¸¿©ÁØ´Ù.
Pearl Àº ŸÀÏÀÌ ºóÀÚ¸®·Î Çѹø¿¡ À̵¿ÇÒ ¼ö ÀÖ´Ù´Â ¸ðµ¨À» »ç¿ëÇϸé
º¸´Ù ¾à°£ ´õ ÁÁÀº
ÇÔ¼ö¸¦ °è»êÇÒ ¼ö ÀÖ´Ù´Â Á¡À» ÁöÀûÇÏ¿´´Ù. ¶Ç ´Ù¸¥ Á¶±Ý ´ú ¿ÏÈµÈ ¸ðµ¨Àº
ŸÀÏÀÌ ÀÎÁ¢ÇÑ ÀÚ¸®¸¦ µû¶ó ºóÀÚ¸®·Î À̵¿ÇÒ ¼ö ÀÖ´Ù°í ÇÏ´Â °ÍÀÌ´Ù. À̶§ ÀÎÁ¢ÇÑ
ÇÑ ÀÚ¸®·Î ¿òÁ÷ÀÌ´Â °ÍÀ» ÇѹøÀÇ À̵¿À¸·Î °è»êÇÑ´Ù.
Áöµµ¿¡¼ ±æÀ» ã´Â ¹®Á¦¿¡¼
À¯Å¬¸®µå °Å¸® (Á÷¼± °Å¸®) ¸¦ ÇÔ¼ö·Î »ç¿ëÇÏ´Â °Íµµ Á¶°ÇÀ» ¿ÏȽÃŲ ¸ðµ¨À̶ó°í ¸»ÇÒ ¼ö ÀÖ´Ù. Á¸ÀçÇÏ´Â
±æÀ» µû¶ó ¿©ÇàÇØ¾ß ÇÏ´Â ´ë½Å¿¡, ¿ÏÈµÈ ¸ðµ¨¿¡¼ÀÇ ¿©ÇàÀÚ´Â ¾î´À µµ½Ã·Î³ª Á÷¼±
°Å¸®·Î Á÷Á¢ "À̵¿" ÇÒ ¼ö ÀÖ´Ù. ¿ÏÈµÈ ¸ðµ¨¿¡¼ÀÇ ´äÀº ¿ø·¡ ¹®Á¦¿¡¼ÀÇ
´äº¸´Ù Àý´ë°ªÀÌ ´õ Å©Áö ¾ÊÀ¸¹Ç·Î, ÀÌ·¸°Ô ¼±ÅõÈ
ÇÔ¼ö´Â Ç×»ó Çã¿ë °¡´ÉÇÑ °ÍÀÌ´Ù! ÀÌ·± ÇÔ¼öµéÀº ¶ÇÇÑ Àϰü¼ºÀÌ ÀÖÀ¸¸ç,
µû¶ó¼ ÀÌ·± ÇÔ¼öµéÀ» ÀÌ¿ëÇÑ ¾Ë°í¸®ÁòÀº ÀÌÀü¿¡ È®ÀåÇß´ø ³ëµå¸¦ ´Ù½Ã ¹æ¹®ÇÒ Çʿ䰡
¾ø´Ù.
ÇÔ¼ö¸¦ ¼±ÅÃÇÒ ¶§´Â ±× ÇÔ¼ö¸¦ °è»êÇϱâ À§ÇØ ¾ó¸¶¸¸ÅÀÇ ³ë·ÂÀÌ ÇÊ¿äÇÑÁö¸¦
¹Ýµå½Ã °í·ÁÇØ¾ß ÇÑ´Ù. ´ú ¿ÏÈµÈ ¸ðµ¨Àϼö·Ï ÀϹÝÀûÀ¸·Î °è»êÇϱâ´Â ¾î·ÆÁö¸¸ ´õ
ÁÁÀº ÈÞ¸®½ºÆ½ ÇÔ¼ö°¡ µÈ´Ù.
¿Í ¿ÏÀüÈ÷ °°Àº ÈÞ¸®½ºÆ½ ÇÔ¼ö¸¦ »ç¿ëÇϸé È®ÀåÇÏ´Â ³ëµåÀÇ °³¼ö¸¦ ÃÖ¼Ò·Î ÁÙÀÏ
¼ö ÀÖÀ¸³ª, ±×·¯ÇÑ
¸¦ °è»êÇÏ·Á¸é ¿ø·¡ÀÇ ¹®Á¦¸¦ Ç®¾î¾ß¸¸ ÇÒ °ÍÀÌ´Ù. ÀϹÝÀûÀ¸·Î Á¤È®ÇÑ
ÇÔ¼ö¿¡ ÀÇÇØ ¾ò¾îÁö´Â À̵æ°ú ±× ÇÔ¼ö¸¦ °è»êÇÏ´Â ºñ¿ë »çÀÌ¿¡´Â Æ®·¹À̵å¿ÀÇÁ°¡
ÀÖ´Ù.
¸¹Àº °æ¿ì¿¡ ÀÇ ÇÏÇÑ (lower bound) ÀÌ ¾Æ´Ñ
ÇÔ¼ö¸¦ »ç¿ëÇϸé Çã¿ë¼ºÀ» Æ÷±âÇÏ´Â ´ë½Å Ž»öÀÇ È¿À²¼ºÀ» ³ôÀÏ ¼ö ÀÖ´Ù.
Áï, ÃÖÀûÀÓÀ» º¸ÀåÇÏ´Â °æ·Îº¸´Ù ÃÖÀûÀÌ ¾Æ´Ò ¼öµµ ÀÖ´Â °æ·Î°¡ ´õ ã±â ½¬¿î °ÍÀÌ´Ù.
¶ÇÇÑ
ÀÇ ÇÏÇÑÀÌ ¾Æ´Ñ
ÇÔ¼ö°¡ ¹Ýµå½Ã ÇÏÇÑÀÌ µÇ´Â ÇÔ¼öº¸´Ù °è»êÇϱ⵵ ½¬¿ï ¼ö ÀÖ´Ù. È®ÀåµÇ´Â
³ëµåÀÇ ¼öµµ ÁÙ¾îµé°í (Çã¿ë¼ºÀº ¾ø¾îÁöÁö¸¸), °è»ê·®µµ ÁÙ¾îµé±â ¶§¹®ÀÌ´Ù.
¶Ç
ÇÑ °¡Áö °¡´É¼ºÀº Æò°¡ ÇÔ¼ö¿¡¼ ¿Í
ÀÇ »ó´ëÀûÀÎ °¡ÁßÄ¡¸¦ Á¶Á¤ÇÏ´Â °ÍÀÌ´Ù. Áï,
°¡ ¾ç¼öÀÏ ¶§
¸¦ »ç¿ëÇÏ´Â °ÍÀÌ´Ù.
¾ÆÁÖ Å« °ªÀ̸é ÈÞ¸®½ºÆ½ ¿ä¼Ò°¡ °Á¶µÇ°í,
°¡ ¾ÆÁÖ ÀÛÀº °ªÀ̸é Ž»öÀÌ ³Êºñ¿ì¼± Ư¼ºÀ» ¸¹ÀÌ °®°Ô µÈ´Ù. ½ÇÇè¿¡ ÀÇÇϸé
ÀÇ °ªÀ» ³ëµåÀÇ ±íÀÌ¿¡ ¿ªºñ·ÊÇÏ°Ô º¯È½ÃŰ¸é Ž»öÀÇ È¿À²ÀÌ ³ô¾ÆÁö´Â °æ¿ì°¡
¸¹´Ù°í µÇ¾î ÀÖ´Ù. ±íÀ̰¡ ¾èÀº ºÎºÐ¿¡¼´Â Ž»öÀÌ ÈÞ¸®½ºÆ½ ¿ä¼Ò¿¡ ÁÖ·Î ÀÇÁ¸Çϰí,
±íÀ̰¡ ±í¾îÁö¸é Ž»öÀÌ Á¡Â÷ ³Êºñ¿ì¼±ÀÌ µÇ¾î, ¸ñÇ¥±îÁöÀÇ °æ·Î Áß Çϳª°¡ °á±¹
¹ß°ßµÇ´Â °ÍÀÌ´Ù.
±×¸² 10 ¾ç¹æÇâ Ž»ö
½ÃÀÛ ³ëµå¿Í ¸ñÇ¥ ³ëµå ¾çÂÊ¿¡¼ µ¿½Ã¿¡ Ž»öÀ» ¼öÇàÇÔÀ¸·Î½á Ž»öÀÇ È¿À²À» ³ôÀÏ ¼öµµ ÀÖÀ» °ÍÀÌ´Ù. ÀϹÝÀûÀ¸·Î ÀÌ·¯ÇÑ È¿À²ÀÇ Çâ»óÀº ³Êºñ¿ì¼± Ž»ö¿¡¼¸¸ ¾ò¾îÁú ¼ö ÀÖ´Ù. ³Êºñ¿ì¼± Ž»öÀÌ ¾ç¹æÇâÀ¸·Î ¼öÇàµÇ¸é Ž»öÀÇ Àü¹æÀÌ ½ÃÀÛ°ú ¸ñÇ¥ »çÀÌ¿¡¼ ¸¸³ª°Ô µÉ °ÍÀ̸ç (±×¸² 10a ÂüÁ¶) ³Êºñ¿ì¼± ¾ç¹æÇâ Ž»öÀÌ ÃÖÀû °æ·Î¸¦ ã´Â °ÍÀ» º¸ÀåÇØ ÁÖ´Â Á¾·á Á¶°ÇÀÌ ¼³Á¤µÈ ¹Ù ÀÖ´Ù [Pohl 1971]. ±×·¯³ª ÈÞ¸®½ºÆ½ Ž»öÀÌ ½ÃÀÛ°ú ¸ñÇ¥ ³ëµå ¾çÂÊ¿¡¼ ½ÃÀ۵Ǵ °æ¿ì, ¸¸ÀÏ ÈÞ¸®½ºÆ½ÀÌ Å½»öÀ» ¿ÇÁö ¾ÊÀº ¹æÇâÀ¸·Î ÀεµÇÏ°Ô µÈ´Ù¸é, µÎ Ž»öÀÇ Àü¹æÀº ÃÖÀû °æ·Î¿¡¼ ¸¸³ªÁö ¾ÊÀ» ¼öµµ ÀÖ´Ù (±×¸² 10b ÂüÁ¶).
Ž»öÀÇ È¿À²¼º¿¡ ´ëÇÑ À¯¿ëÇÑ ±âÁØ °¡¿îµ¥ Çϳª´Â
½ÇÁú ºÐ±â °è¼ö (effective branching factor) ÀÌ´Ù. À̰ÍÀº Ž»ö °úÁ¤ÀÌ ¾ó¸¶³ª Á¤È®ÇÏ°Ô ¸ñÇ¥¸¦ ÇâÇØ ÁýÁߵǾú´ÂÁö¸¦ ³ªÅ¸³½´Ù.
¾î¶² Ž»öÀÌ ±æÀ̰¡
ÀÎ °æ·Î¸¦ ãÀ¸¸é¼ ÃÑ
°³ÀÇ ³ëµå¸¦ »ý¼ºÇß´Ù°í ÇÏÀÚ.
´Â ´ÙÀ½ÀÇ ¼ºÁúÀ» ¸¸Á·ÇÏ´Â Æ®¸®¿¡¼ÀÇ °¢ ³ëµåÀÇ ÀÚ½Ä ³ëµå ¼ö¿Í °°´Ù.
µû¶ó¼ °æ·ÎÀÇ ±æÀÌ ¹× »ý¼ºµÈ ³ëµåÀÇ ÃÑ ¼ö
°ú
ÀÇ °ü°è´Â ´ÙÀ½ÀÇ ½ÄÀ¸·Î ³ªÅ¸³¾ ¼ö ÀÖ´Ù.
±×¸² 11 ¿©·¯ °¡Áö °ª¿¡ ´ëÇÑ
´ë
±×·¡ÇÁ
¸¦
¿Í
ÀÇ ÇÔ¼ö·Î ³ªÅ¸³¾ ¼ö´Â ¾øÁö¸¸, ´Ù¾çÇÑ
°ª¿¡ ´ëÇÑ
´ë
ÀÇ ±×·¡ÇÁ¸¦ ±×¸² 11 ¿¡ º¸¿´´Ù. 1 ¿¡ ±ÙÁ¢ÇÑ
°ªÀº Ž»öÀÌ ´Ù¸¥ ¹æÇâÀ¸·Î °ÅÀÇ ºÐ±âµÇÁö ¾Ê°í ¸ñÇ¥¸¦ ÇâÇØ ±Øµµ·Î ÁýÁßµÈ °æ¿ì¿¡
ÇØ´çÇÑ´Ù. ¹Ý´ë·Î, ¿©·¯ °¥·¡°¡ Àִ Ž»ö ±×·¡ÇÁ´Â ³ôÀº
°ªÀ» °®´Â´Ù.
½ÇÁú ºÐ±â °è¼ö°¡ °æ·ÎÀÇ ±æÀÌ¿¡ ÃæºÐÈ÷ µ¶¸³ÀûÀÎ ÀÌ»ó, ÀÌ
ÀڷḦ ÀÌ¿ëÇÏ¿© ¿©·¯ °æ¿ìÀÇ Å½»ö¿¡¼ ¾ó¸¶¸¸ÅÀÇ ³ëµå°¡ »ý¼ºµÉ °ÍÀÎÁö¸¦ ÃßÁ¤ÇÒ
¼ö ÀÖ´Ù. ¿¹¸¦ µé¾î, ±×¸² 11 À» ÀÌ¿ëÇÏ¿© À» Æò°¡ ÇÔ¼ö·Î ÀÌ¿ëÇÏ¸é ±×¸² 2 ¿¡ ÀÖ´Â 8 ÆÛÁñÀÇ
°ªÀÌ 1.2 ¶ó´Â °ÍÀ» °è»êÇÒ ¼ö ÀÖ´Ù. 30 ½ºÅÜÀÌ °É¸®´Â ´õ º¹ÀâÇÑ 8 ÆÛÁñ ¹®Á¦¸¦
Ǫ´Â µ¥ ÀÌ Æò°¡ ÇÔ¼ö¸¦ ÀÌ¿ëÇÏ¸é ¸î °³ÀÇ ³ëµå°¡ »ý¼ºµÇ´ÂÁö¸¦ ÃßÁ¤ÇÏ·Á ÇÑ´Ù°í
ÇÏÀÚ. ½ÇÁú ºÐ±â °è¼ö°¡ º¯ÇÏÁö ¾Ê´Â´Ù°í °¡Á¤Çϸé, ±×¸² 11 ·ÎºÎÅÍ 30 ½ºÅÜÀÌ °É¸®´Â
ÆÛÁñÀº ¾à 2,000 °³ÀÇ ³ëµå¸¦ »ý¼ºÇÑ´Ù´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù.
¿ä¾àÇϸé, ¾Ë°í¸®Áò A* ÀÇ È¿À²¿¡ ¿µÇâÀ» ¹ÌÄ¡´Â Áß¿äÇÑ ¿ä¼Ò´Â ¼¼ °¡Áö°¡ ÀÖ´Ù.
ÀûÀýÇÑ ÈÞ¸®½ºÆ½ ÇÔ¼ö¸¦ ¼±Á¤Çؾ߸¸ ÀÌ ¿ä¼ÒµéÀÇ ±ÕÇüÀ» ¸ÂÃß¾î Ž»öÀÇ È¿À²À» ±Ø´ëȽÃų ¼ö ÀÖ´Ù.
ÈÞ¸®½ºÆ½ Ž»öÀ» Æ÷ÇÔÇÏ¿©
Áö±Ý±îÁö À̾߱âÇÑ ¸ðµç Ž»ö ¹æ¹ýµéÀÇ ½Ã°£ º¹Àâµµ (time complexity) ´Â »ý¼ºµÇ´Â
³ëµåÀÇ ¼ö¸¦ À̶ó ÇÒ ¶§
ÀÌ´Ù (ÈÞ¸®½ºÆ½ ÇÔ¼ö´Â ÀÏÁ¤ÇÑ ½Ã°£ (constant time) ¿¡ °è»êµÉ ¼ö ÀÖ´Ù°í °¡Á¤ÇÏ¿´´Ù).
ƯÈ÷, ½ÇÁú ºÐ±â °è¼ö°¡
À̰í, ¾ÆÅ©µéÀÇ °ªÀº ¸ðµÎ °°À¸¸ç, ¸ñÇ¥ ³ëµå´Â ½ÃÀÛ ³ëµå·ÎºÎÅÍ ±íÀÌ
¿¡ ÀÖ´Ù°í ÇÒ ¶§, ³Êºñ¿ì¼± Ž»öÀÇ ½Ã°£ º¹Àâµµ´Â
ÀÌ´Ù. ¾ÆÅ©°ªµéÀÌ ¸ðµÎ ´Ù¸¥ °æ¿ì ±ÕÀϺñ¿ë Ž»ö
ÀÇ ½Ã°£ º¹Àâµµ´Â, ÃÖÀû ÇØÀÇ °ªÀÌ
ÀÌ°í ¾ÆÅ©ÀÇ ÃÖ¼Ò°ªÀÌ
ÀÏ ¶§,
ÀÌ´Ù [Korf 1992]. ¸¹Àº ½ÇÁ¦ÀûÀÎ ¹®Á¦µéÀÇ
(¶Ç´Â
) °ªÀº ÃÖÀûÇØÀÇ Å½»ö (ÈÞ¸®½ºÆ½ Ž»öÀ» Æ÷ÇÔÇÏ¿©) ÀÌ ºÒ°¡´ÉÇÒ Á¤µµ·Î Å©´Ù.
¿¹¸¦ µé¾î, ¸ñÇ¥°¡ 15¹øÀÇ ÇൿÀ» ÃëÇØ¾ß µµ´ÞÇÒ ¼ö ÀÖ´Â °Å¸®¿¡ ÀÖÀ» ¶§ Ž»öÀ»
ÀÌ¿ëÇÏ¿© °¡Àå ÁÁÀº ´ÙÀ½ ÇൿÀ» (°¡·É 4 °³ÀÇ °¡´ÉÇÑ Çൿ Áß¿¡¼) ã´Â´Ù¸é, Ž»ö
¾Ë°í¸®ÁòÀº ¾à
°³ÀÇ ³ëµå¸¦ È®ÀåÇØ¾ß ÇÑ´Ù. ÀÌ·± ±ä °è»êÀº ¿¡ÀÌÀüÆ®°¡ ¸î ºÐÀÇ ÀÏÃʳ»¿¡ ÆÇ´ÜÀ»
³»·Á¾ß ÇÏ´Â °æ¿ì¿¡´Â ½Ç¿ëÀûÀÌÁö ¸øÇÒ °ÍÀÌ´Ù. A* ÀÇ °ø°£ º¹Àâµµ (space
complexity) µµ È®ÀåµÈ ¸ðµç ³ëµåµéÀÌ Æ®¸® ±¸Á¶¿¡ ÀúÀåµÇ¾î¾ß Çϱ⠶§¹®¿¡ ½Ã°£
º¹Àâµµ¿Í °°´Ù.
¿¡ÀÌÀüÆ®´Â °¡Áö°í ÀÖ´Â ÀÚ¿ø¿¡ ´ëÇØ ½Ã°£»ó ±×¸®°í ¸Þ¸ð¸®»óÀÇ Á¦ÇÑÀÌ ÀÖÀ» °ÍÀ̹ǷÎ, ¸¹Àº °æ¿ì¿¡ ÀÖ¾î¼ ÃÖÀû ÇØ¸¦ ã´Â °ÍÀÌ ºÒ°¡´ÉÇÒ °ÍÀÌ´Ù. ÀÌ·± °æ¿ì¿¡´Â ÃÖÀûÀº ¾Æ´ÏÁö¸¸ ¹Þ¾ÆµéÀÏ ¼ö ÀÖ´Â ÇØ (¸¸Á·ÇÑ (satisfying) ÇØ¶ó°íµµ ÇÑ´Ù) ¶Ç´Â ºÎºÐ ÇØ¸¦ ã´Â °ÍÀ¸·Î ¸¸Á·ÇØ¾ß ÇÑ´Ù. °èȹ, Çൿ ±×¸®°í ÇнÀ¿¡¼´Â Á¦ÇÑµÈ ÀÚ¿øÀ» °¡Áö°í ÀÖ´Â ¿¡ÀÌÀüÆ®°¡ »ç¿ëÇÒ ¼ö ÀÖ´Â ´Ù¾çÇÑ ¹æ¹ýµéÀ» ¼Ò°³ÇÒ °ÍÀÌ´Ù.
heuristic search ´Â µÎ Á¾·ùÀÇ °è»êÀ» ¼öÇàÇÑ´Ù. ù°·Î, ½ÇÁ¦·Î ³ëµå¸¦ È®ÀåÇÏ°í °æ·Î ÀÚü¸¦ »ý¼ºÇÏ´Â °´Ã¼ ·¹º§ (object level) ÀÇ °è»êÀÌ ÀÖ´Ù. µÑ°·Î, ´ÙÀ½¿¡ ¾î´À ³ëµå¸¦ È®ÀåÇÒ °ÍÀÎÁö¸¦ °áÁ¤ÇÏ´Â ¸ÞŸ ·¹º§ (meta level) ÀÇ °è»êÀÌ ÀÖ´Ù. °´Ã¼ ·¹º§Àº ½Ç¼¼°è¿¡¼ÀÇ ¹°¸®ÀûÀÎ Çൿ¿¡ °üÇÑ °ÍÀ̰í, ¸ÞŸ ·¹º§Àº ±×·¡ÇÁ¿¡¼ÀÇ °è»ê¿¡ °üÇÑ °ÍÀÌ´Ù. °´Ã¼ ·¹º§°ú ¸ÞŸ ·¹º§ÀÇ ±¸ºÐÀº AI ¿¡¼ ÀÚÁÖ µîÀåÇÑ´Ù. À̵éÀº [Stuart Russell & Wefald 1991 (Russell, S., and Wefald, E., Do the Right Thing, Cambridge, MA: MIT Press, 1991.). Do the Right Thing] ¿¡ öÀúÇÏ°Ô ³íÀǵǾî ÀÖÀ¸¸ç, °èȹ, Çൿ ±×¸®°í ÇнÀ¿¡¼´Â ¼³¸íÇÒ ´ÜÃàµÈ (abbreviated) Ž»ö ¹æ¹ý¿¡ ÀÖ¾î¼ Æ¯È÷ Áß¿äÇÑ ¿ªÇÒÀ» ¼öÇàÇÑ´Ù.
ŸÀÏ ¸ÂÃ߱⠹®Á¦´Â ¸¹Àº AI ¿¬±¸Àڵ鿡 ÀÇÇØ ÈÞ¸®½ºÆ½ Ž»ö ¹æ¹ýÀ» ½ÃÇèÇϱâ À§ÇÑ Å×½ºÆ®º£µå (tastbed) ·Î »ç¿ëµÇ¾î ¿Ô´Ù. [Doran & Michie 1966 (Doran, J., and Michie, D., "Experiments with the Graph Traverser Program," Proc. Royal Society of London, vol. 294 (series A), pp.235-259, 1966.). Experiments with the Graph Traverse Program] ÀÇ ÃÊ±â ³í¹®ÀÌ 8 ÆÛÁñÀ» »ç¿ëÇß°í, ±× ÀÌÈÄ·Î »ç¶÷µéÀÌ ±×·¡ÇÁ¿¡¼ °æ·Î¸¦ ã´Â °úÁ¤¿¡ Æò°¡ ÇÔ¼ö¸¦ »ç¿ëÇϱ⠽ÃÀÛÇß´Ù.
1990 ³â¿¡ Korf ´Â "IDA* ·Î 15 ÆÛÁñÀº Ç® ¼ö ÀÖÁö¸¸ ±× ÀÌ»óÀÇ ÆÛÁñ (24 ÆÛÁñ µî) Àº ÇöÀçÀÇ ÄÄÇ»ÅͷΠó¸®ÇÒ ¼ö ¾ø´Ù" °í ÇÏ¿´´Ù [Korf 1990 ({Korf1990} Korf, R., "Real-Time Heuristic Search," Artificial Intelligence}, 42, 1990.), Realtime Heuristic search]. ÇÏÁö¸¸ ´õ °·ÂÇÑ ÄÄÇ»ÅÍ (ÃÊ´ç ¹é¸¸ °³ÀÇ ³ëµå¸¦ »ý¼ºÇÒ ¼ö ÀÖ´Â Sun Ultra Sparc ¿öÅ©½ºÅ×À̼Ç) ¿Í ´õ °·ÂÇÑ (ÀÚµ¿ÀûÀ¸·Î ã¾ÆÁø) ÈÞ¸®½ºÆ½À» »ç¿ëÇÏ¿© [Richard Korf & Taylor 1996 (Korf, R., and Taylor, L., "Finding Optimal Solutions to the Twenty-Four Puzzle," in Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), pp.1202-1207, Menlo Park, CA: AAAI Press, 1996.). Optimal Solution to 24 puzzles] ´Â ¹«ÀÛÀ§·Î ¸¸µé¾î³½ ´äÀÌ ÀÖ´Â 24 ÆÛÁñ ¹®Á¦¿¡ ´ëÇÑ ÃÖÀûÇØ¸¦ 2 ½Ã°£ 15 ºÐ¿¡¼ 1 °³¿ù »çÀÌÀÇ ½Ã°£¿¡ ã¾Æ³¾ ¼ö ÀÖ¾ú´Ù. [Richard Korf 1997 (Korf, R., "Finding Optimal Solutions to Rubik's Cube Using Pattern Databases," in Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), nl pp.700-705, Menlo Park, CA: AAAI Press, 1997.). Optimal Solution to Rubik's Cube Using Pattern Databases] ´Â IDA* ¸¦ 3 × 3 × 3 ·çºò½º Å¥ºê (Rubik's Cube) ÆÛÁñÀÇ ÃÖÀû ÇØ¸¦ ã´Â µ¥µµ Àû¿ëÇÏ¿´´Ù.
Ž»ö ±â¹ýµéÀ» ½ÃÇèÇϰí
°³¼±Çϱâ À§ÇÏ¿© ÆÛÁñµéÀÌ À¯¿ëÇÏ°Ô »ç¿ëµÇ¾î ¿ÔÁö¸¸, A* ¿Í ±âŸ ÈÞ¸®½ºÆ½
Ž»ö ¹æ¹ýµéÀº ¸¹Àº ½ÇÁ¦ ¹®Á¦¿¡µµ ¼º°øÀûÀ¸·Î Àû¿ëµÇ¾î ¿Ô´Ù. ÈÞ¸®½ºÆ½ ÇÔ¼ö¸¦
ã±â À§ÇÑ ¿ÏÈµÈ ¸ðµ¨¿¡ ´ëÇÏ¿© ´õ ÀÚ¼¼ÇÑ ³»¿ëÀº [Mostow & Prieditis
1989 (Mostow, J., and Prieditis, A.,
"Discovering Admissible Heuristics by Abstracting and Optimizing: A Transformational
Approach," in Proceedings of the Eleventh International Joint Conference
on Artificial Intelligence (IJCAI-89), pp.701-707, San Francisco: Morgan
Kaufmann, 1989.), Prieditis 1993 (Prieditis, A, "Machine Discovery of Effective
Admissible Heuristics," Machine Learning, 12(1-3):117-141, 1993.)] ¿¡ ³ª¿Í ÀÖ´Ù. [Pohl 1973
(Pohl, I., "The Avoidance of (Relative) Catastrophe,
Heuristic Competence, Genuine Dynamic Weighting and Computational Issues in
Heuristic Problem~Solving," in Proceedings of the Third International
Joint Conference on Artificial Intelligence (IJCAI-73), pp.20-23, San Francisco:
Morgan Kaufmann, 1973.)] Àº ÀÇ ÈÞ¸®½ºÆ½ ¿ä¼Ò¿¡ ´ëÇÑ °¡ÁßÄ¡¸¦ Á¶Á¤ÇÏ´Â ½ÇÇèÀ» ¼öÇàÇÏ¿´´Ù.
ÈÞ¸®½ºÆ½ Ž»ö¿¡ ´ëÇÑ °¡Àå °íÀüÀûÀΠåÀº [Judea Pearl 1984 (Pearl, J., Heuristics: Intelligent Search Strategies for Computer Problem Solving, Reading, MA: Addison-Wesley, 1984.). Heuristics Intelligent Search Strategies...] ÀÌ´Ù. [Laveen N. Kanal & Kumar 1988 (Kanal, L., and Kumar, V. (eds.), Search in Artificial Intelligence, Berlin: Springer-Verlag, 1988.). Search in AI] Àº Ž»ö¿¡ °üÇÑ ³í¹®µéÀ» ¸ð¾Æ³õÀº Ã¥ÀÌ´Ù. ÀÌ Ã¥ÀÇ Ã¹ ¹øÂ° ³í¹®Àº AI ¿Í OR (operations research) ¿¬±¸Àڵ鿡 ÀÇÇØ °¢°¢ µ¶¸³ÀûÀ¸·Î °³¹ßµÈ Ž»ö ¹æ¹ýµéÀ» Çϳª·Î ÅëÀϽÃų °ÍÀ» Á¦¾ÈÇϰí ÀÖ´Ù.