A*  Algorithm

 

............ A* search algorithm (A star ¶ó°í ¹ßÀ½) Ãʱ⠳ëµå¿¡¼­ ¸ñÇ¥ ³ëµå±îÁöÀÇ °æ·Î¸¦ ã´Â ±×·¡ÇÁ Ž»ö ¾Ë°í¸®ÁòÀÌ´Ù. ¸ñÇ¥ ³ëµå±îÁöÀÇ °¡ÀåÁÁÀº °æ·Î¸¦ ÃßÁ¤ (estimate of the best route) Çϱâ À§ÇØ °¢ ³ëµå¿¡ ·©Å·À» ºÎ¿©ÇÏ´Â "heuristic estimate" ¸¦ »ç¿ëÇÏ°í ±× ¼ø¼­´ë·Î ³ëµå¸¦ ¹æ¹®ÇÑ´Ù. µû¶ó¼­ A* algorithm Àº best-first search ÀÇ ÇÑ ¿¹ÀÌ´Ù. A* algorithm Àº ±×·¡ÇÁ¿¡¼­ ÃÖ´Ü°æ·Î¸¦ ã´Â °ÍÀ» º¸ÀåÇϸç ÃÖ¼ÒÀÇ °è»ê (minimum computation) À¸·Î ¼öÇàÇÑ´Ù. ÃÖÃÊ·Î ¼Ò°³µÈ ³í¹® (A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs, 1968) ¿¡¼­ Çã¿ë¼º°ú ÃÖÀû¼º (admissibility and optimality properties) ÀÌ Áõ¸íµÇ¾ú´Ù. ............

A* ´Â ÃÖ´Ü °Å¸® ã±â (Path finding problem) ¿¡¼­ °¡Àå ÈǸ¢ÇÑ ¼±ÅÃÀÌ µÉ °ÍÀÌ´Ù. ¿Ö³ÄÇϸé Dijkstra's algorithm À̳ª Best-First Search (BFS) º¸´Ù ÈξÀ ºü¸£±â ¶§¹®ÀÌ´Ù. A* ´Â ÈÞ¸®½ºÆ½ ¹æ¹ý (ÀÇ»ç°áÁ¤À» ÇÒ ¶§ ÇØ´ç ¹®Á¦¿¡ ´ëÇÑ Á¤º¸¸¦ ÀÌ¿ëÇÏ´Â °Í) °ú Çü½ÄÀû ¹æ¹ý (formal method : ¹®Á¦¿Í °ü·ÃµÈ Á¤º¸¸¦ »ç¿ëÇÏÁö ¾ÊÁö¸¸ formally analyzed µÉ ¼ö ÀÖ´Â °Í)À» °áÇÕÇϱâ À§ÇØ 1968 ³â¿¡ °³¹ßµÇ¾ú´Ù. A* ÀÇ ´ë·«ÀÇ ±¸Á¶´Â ±×·¡ÇÁ Ž»ö ¾Ë°í¸®ÁòÀÌ´Ù. ±×·¯³ª ´Ù¸¥ ±×·¡ÇÁ Ž»ö ¾Ë°í¸®Áò°ú ´Ù¸¥ Á¡Àº ¸ñÇ¥¿¡ ¾ó¸¶³ª ±ÙÁ¢ÇÑ °ÍÀÎÁö¸¦ Æò°¡Çϴµ¥ ÈÞ¸®½ºÆ½ ÇÔ¼ö¸¦ »ç¿ëÇÑ´Ù´Â °ÍÀÌ´Ù. ÈÞ¸®½ºÆ½¿¡ ÀÇÇØ ¸ÕÀú °¡Àå ¹Ù¶÷Á÷ÇÑ ¹æÇâÀ» Ž»öÇÏ°Ô µÈ´Ù. ±× ¹æÇâÀÌ ½ÇÆÐÇÏ¸é ´Ù¸¥ °æ·Î¸¦ ã°Ô µÈ´Ù. ¿©±â¼­´Â A* ¾Ë°í¸®ÁòÀÇ ¼¼¼¼ÇÑ ºÎºÐ±îÁö´Â ´Ù·çÁö ¾Ê°í, A* °¡ ¾î¶»°Ô ¿òÁ÷ÀÌ´ÂÁö¸¦ ´Ù·ç¾î¼­ °ÔÀÓ¿¡ ¾î¶»°Ô ÀÀ¿ëµÇ´ÂÁö¿¡ ÃÊÁ¡À» ¸ÂÃá´Ù .............. (Amit's Thought on Path Finding : A* Algorithm)

A* algorithm Àº ¸¹Àº Á¾·áÀÇ ¹®Á¦ ÇØ°á¿¡ ÀÌ¿ëµÅ ¿ÔÀ¸¸ç °ÔÀÓ °³¹ß¿¡¼­ È¿À²ÀûÀÎ path finding À¸·Î ¸¹ÀÌ ¾²ÀδÙ.  A* ´Â °ø°£¾ÈÀÇ ¾î¶² ƯÁ¤ state ¿¡¼­ ÀÎÁ¢ÇÑ state¸¦ Á¶»çÇØ ³ª°¡¸é¼­ ½ÃÀÛ state¿¡¼­ ¸ñÇ¥ state ±îÁö °¡Àå ½Ñ ºñ¿ëÀÇ °æ·Î¸¦ ã´Â algorithm ÀÌ´Ù ........ A* algorithm ÀÌ ¾²ÀÎ À¯¸íÇÑ ¹®Á¦´Â 1Ä­ÀÌ ºó 15 puzzle ÀÌ´Ù.  4*4 ¿¡¼­ Çϳª°¡ ºó 15 puzzle¿¡¼­ ¾î¶² state ¶õ 15°³ ŸÀϵéÀÇ Æ¯Á¤ÇÑ ¹èÄ¡¸¦ ÀǹÌÇÏ°í, ÀÎÁ¢ÇÑ state ¶õ ÇϳªÀÇ Å¸ÀÏÀ» ºó °÷À¸·Î À̵¿½ÃÅ´À¸·Î½á »õ·ÎÀÌ »ý±â´Â ƯÁ¤ÇÑ ¹èÄ¡¸¦ ÀǹÌÇÑ´Ù ...... ºñ½ÁÇÏ°Ô path finding ¹®Á¦¿¡¼­ ¾î¶² state ´Â °ÔÀÓ ¼¼°è¿¡¼­ unit ÀÌ Â÷ÁöÇÏ°í Àִ ƯÁ¤ÇÑ À§Ä¡·Î ±¸¼ºµÇ¸ç, ÀÎÁ¢ÇÑ state ´Â ±× À¯´ÖÀÌ Çѹø¿¡, Á÷Á¢ À̵¿ÇÒ ¼ö ÀÖ´Â ÀÎÁ¢ÇÑ À§Ä¡µé·Î ±¸¼ºµÈ´Ù.

A* algorithm ÀÇ ±âº»Àº ¾ÆÁ÷ Á¶»çÇÏÁö ¾ÊÀº stateµé Áß °¡Àå À¯¿ëÇÒ µíÇÑ state¸¦ Á¶»çÇÏ´Â °úÁ¤À» ¹Ýº¹ÇÏ´Â °ÍÀÌ´Ù. Á¶»çÁß ¸ñÇ¥µÈ state ¶ó°í ÆǴܵǸé algorithm Àº ³¡³ª°í, ±×·¸Áö ¾ÊÀ¸¸é ¸ñÇ¥¿¡ µµ´ÞÇÒ¶§±îÁö °è¼Ó ÀÎÁ¢ state¸¦ Á¶»çÇسª°£´Ù ..... A* °¡ °ü¸®ÇÏ´Â stateÀÇ list ´Â µÎ Á¾·ùÀÌ´Ù.  Çϳª´Â ¾ÆÁ÷ Á¶»çÇÏÁö ¾ÊÀº »óŵéÀÌ ´ã±ä 'Open list' ÀÌ°í ´Ù¸¥ Çϳª´Â ÀÌ¹Ì Á¶»çÇÑ »óŵéÀ» ´ãÀº 'Closed list' ÀÌ´Ù. óÀ½  algorithmÀ» ½ÃÀÛÇÒ ¶§ Ž»öµÈ °÷ÀÌ ¾øÀ¸¹Ç·Î Closed list µéÀº ºñ¾î ÀÖ°í, Open list ´Â óÀ½ À§Ä¡- Áï ½ÃÀÛ state ¸¸ °®°í ÀÖ´Ù.

algorithm Àº ¼öÇàµÇ¸é¼­ Open list Áß °¡Àå À¯¸ÁÇÑ °Í(1)À» °¡Á®¿Í ´ÙÀ½ state¸¦ °è»êÇÏ°í, À̵éÀº Open list µé¿¡¼­´Â »èÁ¦µÈ´Ù. ±× state °¡ ¸ñÇ¥ÇÑ state °¡ ¾Æ´Ï¸é ÀÎÁ¢ÇÑ À§Ä¡µéÀ» Á¤·ÄÇؼ­ ¾ÆÁ÷ Ž»öµÇÁö ¾ÊÀº °÷À̶ó¸é Open list ¿¡ ³Ö°í, ÀÌ¹Ì Open list ¿¡ ÀÖ´Â °ÍÀ϶§´Â ±× À§Ä¡¸¦ ÅëÇÏ´Â »õ·Î¿î °æ·Î°¡ ÀÌÀü º¸´Ù ºñ¿ëÀÌ ½Î¸é ±× state ÀÇ Á¤º¸¸¦ °»½ÅÇØÁØ´Ù. ¹Ý´ë·Î ±× À§Ä¡µéÀÌ Closed list ¿¡ ÀÖ´Â °ÍÀ̶ó¸é ÀÌ¹Ì search ÇÑ °ÍÀ̹ǷΠ¹«½ÃÇÑ´Ù. ¸ñÇ¥¿¡ µµ´ÞÇϱâ Àü¿¡ Open list °¡ ºó´Ù¸é ÀÌ°ÍÀº start point¿¡¼­ ¸ñÇ¥ÇÑ °÷À¸·Î °¡´Â °æ·Î°¡ Á¸ÀçÇÏÁö ¾Ê´Â´Ù´Â ¶æÀÌ´Ù ......... À¯¸ÁÇÑ state¶õ ±× À§Ä¡¸¦ Áö³ª¼­ ¸ñÇ¥¿¡ µµ´ÞÇÏ´Â °æ·ÎÀÇ ºñ¿ëÀÌ °¡Àå ½Î°Å³ª ¶Ç´Â °¡Àå ½Ò °¡´É¼ºÀÌ Å« À§Ä¡¸¦ ¸»ÇÑ´Ù ........

A* ´Â ¸î°¡Áö À¯¿ëÇÑ Æ¯Â¡µéÀ» °¡Áö°í ÀÖ´Ù.

À» ³ëµå °ú ¸ñÇ¥ ³ëµå »çÀÌÀÇ ÃÖ´Ü °æ·Î ( ¿¡¼­ ¸ðµç ¸ñÇ¥ ³ëµå±îÁöÀÇ ¸ðµç °¡´ÉÇÑ °æ·Î Áß¿¡¼­) ÀÇ ½ÇÁ¦ °ªÀ̶ó°í ÇÏÀÚ. À» ½ÃÀÛ ³ëµå ¿¡¼­ ±îÁöÀÇ ÃÖ´Ü °æ·ÎÀÇ °ªÀ̶ó°í ÇÏÀÚ. ±×·¯¸é Àº ¿¡¼­ ¸ñÇ¥ ³ëµå±îÁö ³ëµå À» ÅëÇÏ¿© °¥ ¼ö ÀÖ´Â ¸ðµç °¡´ÉÇÑ °æ·Î Áß¿¡¼­ ÃÖ´Ü °æ·ÎÀÇ °ªÀÌ µÈ´Ù. ±×¸®°í ´Â ¿¡¼­ ¸ñÇ¥ ³ëµå±îÁöÀÇ (Á¶°Ç ¾ø´Â) ÃÖ´Ü °æ·ÎÀÇ °ªÀ» ³ªÅ¸³½´Ù. °¢ ³ëµå ¿¡ ´ëÇÏ¿© (ÈÞ¸®½ºÆ½ ¿ä¼Ò) À» ÀÇ ÃßÁ¤°ª À̶ó°í ÇÏ°í, (±íÀÌ ¿ä¼Ò) À» A* ¿¡ ÀÇÇÏ¿© Áö±Ý±îÁö ¹ß°ßµÈ ³ëµå ±îÁöÀÇ °æ·Î Áß¿¡¼­ ÃÖ´Ü °æ·ÎÀÇ °ªÀ̶ó°í ÇÏÀÚ. ¾Ë°í¸®Áò A* ¿¡¼­´Â  ¸¦ Æò°¡ ÇÔ¼ö ·Î »ç¿ëÇÑ´Ù. ¾Ë°í¸®Áò A* ¿¡¼­  ÀÌ 0 ÀÌ¸é ±ÕÀϺñ¿ë Ž»öÀÌ µÈ´Ù ............... (Nils J.Nilsson 1998)

term :

±×·¡ÇÁ (Graph)   Å½»ö (Search)    ÈÞ¸®½ºÆ½ (Heuristic)   ÃÖ´Ü°æ·Î ã±â ¹®Á¦ (Shortest Path Finding Problem)    ¹®Á¦ÇØ°á (Problem Solving)   ÈÞ¸®½ºÆ½ Ž»ö (Heuristic Search)   ÃÖ»ó¿ì¼± Ž»ö (Best-first Search)   A * ¾Ë°í¸®Áò   

site :

Wikipedia : A* Algorithm

A* Algorithm : AI Java Implemented

paper :

A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs : Peter E. Hart, Nils J.Nilsson, Bertram Raphael, IEEE Trans. on Systems Science and Cybernetics, Vol. SSC-4, No. 2, pp 100-107, (July 1968).

A* ¾Ë°í¸®Áò (Algorithm A*) : Nils J.Nilsson

A* ¾Ë°í¸®ÁòÀÇ È޿츮½ºÆ½ À¯µµ ¹æ¹ý : À¯¼®ÀÎ