°ú¸ñ¸í
ÀΰøÁö´É
°úÁ¦ÁÖÁ¦
A ¾Ë°í¸®ÁòÀ» ¼³¸íÇÏ°í »ýÈ° ¼ÓÀÇ ¾Ë°í¸®Áò ¿¹¸¦ 3°¡Áö ÀÛ¼ºÇϼ¼¿ä
¾ÆÀ̵ð
¼º¸í
¼·Ð:
ÀΰøÁö´ÉÀº ÄÄÇ»ÅÍ ½Ã½ºÅÛÀÌ Àΰ£ÀÇ ÇнÀ°ú Ãß·Ð ´É·ÂÀ» ¸ð¹æÇÏ°í ±¸ÇöÇÏ´Â ºÐ¾ßÀÔ´Ï´Ù. ÀΰøÁö´É ¾Ë°í¸®Áò Áß ÇϳªÀÎ A ¾Ë°í¸®Áò¿¡ ´ëÇØ ¼³¸íÇÏ°í, »ýÈ° ¼Ó¿¡¼ È°¿ëµÇ´Â ¾Ë°í¸®Áò ¿¹¸¦ ¼¼ °¡Áö Á¦½ÃÇϵµ·Ï ÇÏ°Ú½À´Ï´Ù.
º»·Ð:
1. A ¾Ë°í¸®Áò:
A ¾Ë°í¸®ÁòÀº ±×·¡ÇÁ Ž»ö ¾Ë°í¸®Áò Áß Çϳª·Î, ÃÖ´Ü °æ·Î ¹®Á¦¸¦ È¿À²ÀûÀ¸·Î ÇØ°áÇϱâ À§ÇØ »ç¿ëµÇ´Â ÀΰøÁö´É ¾Ë°í¸®ÁòÀÔ´Ï´Ù. A ¾Ë°í¸®ÁòÀº DijkstraÀÇ ¾Ë°í¸®Áò°ú ÈÞ¸®½ºÆ½ ÇÔ¼ö¸¦ °áÇÕÇÏ¿© ÃÖÀû °æ·Î¸¦ ã´Â µ¥¿¡ È°¿ëµË´Ï´Ù. À̹ø¿¡´Â A ¾Ë°í¸®ÁòÀÇ µ¿ÀÛ ¿ø¸®¿Í ±¸Ã¼ÀûÀÎ ´Ü°è¿¡ ´ëÇØ ÀÚ¼¼È÷ ¾Ë¾Æº¸µµ·Ï ÇÏ°Ú½À´Ï´Ù.
A ¾Ë°í¸®Áò µ¿ÀÛ ¿ø¸®:
A ¾Ë°í¸®ÁòÀº ±×·¡ÇÁ Ž»ö¿¡¼ ½ÃÀÛ ³ëµåºÎÅÍ ¸ñÇ¥ ³ëµå±îÁöÀÇ ÃÖ´Ü °æ·Î¸¦ ã´Â µ¥ »ç¿ëµË´Ï´Ù. ¾Ë°í¸®ÁòÀº ÇöÀç À§Ä¡¿¡¼ °¡Àå À¯¸ÁÇÑ ³ëµå¸¦ ¼±ÅÃÇÏ¿© ¸ñÀûÁö¿¡ µµ´ÞÇÒ ¶§±îÁö Ž»öÀ» ÁøÇàÇÕ´Ï´Ù. À̶§, °¢ ³ëµå¿¡´Â µÎ °¡Áö °ªÀÌ ÇÒ´çµË´Ï´Ù.
g(n): Ãâ¹ßÁ¡ºÎÅÍ ÇöÀç ³ë¡¦(»ý·«)
(1) ½ÃÀÛ ³ëµå¸¦ ¼±ÅÃÇÏ°í, ½ÃÀÛ ³ëµå¿¡ g(n) ¹× h(n) °ªÀ» ÇÒ´çÇÕ´Ï´Ù.
(2) ½ÃÀÛ ³ëµå¸¦ ¿¸°(open) ¸ñ·Ï¿¡ Ãß°¡ÇÕ´Ï´Ù.
(3) ¿¸° ¸ñ·Ï¿¡¼ °¡Àå ÀÛÀº f(n) °ªÀ» °¡Áø ³ëµå¸¦ ¼±ÅÃÇÕ´Ï´Ù.
(4) ¼±ÅÃÇÑ ³ëµå¸¦ ´ÝÈù(closed) ¸ñ·Ï¿¡ Ãß°¡ÇÕ´Ï´Ù.
(5) ¼±ÅÃÇÑ ³ëµå¿Í ¿¬°áµÈ ÀÎÁ¢ÇÑ ³ëµåµé¿¡ ´ëÇØ ´ÙÀ½ ÀÛ¾÷À» ¼öÇàÇÕ´Ï´Ù:
(6) ¸ñÀûÁö ³ëµå¿¡ µµ´ÞÇϰųª ¿¸° ¸ñ·ÏÀÌ ºñ¾îÁú ¶§±îÁö (3)ºÎÅÍ (5) ´Ü°è¸¦ ¹Ýº¹ÇÕ´Ï´Ù.
2. »ýÈ° ¼ÓÀÇ ¾Ë°í¸®Áò ¿¹:
|