2019³â 2Çбâ ÀΰøÁö´É Áß°£½ÃÇè°úÁ¦¹° °øÅë(»óÅ°ø°£ Ž»ö, A* ¾Ë°í¸®Áò) |
---|
* º» ÀÚ·á´Â ³ë¿ìÁ¸¿¡¼ ½Ç½Ã°£À¸·Î Á¦°øÇÏ°í ÀÖ½À´Ï´Ù.
¢ºÀÚ·á¸ñÂ÷ ¹× ÁÖÁ¦
A ÁöÁ¡¿¡¼ Ãâ¹ßÇÏ¿© H ÁöÁ¡À¸·Î °¡´Â °æ·Î¸¦ ã´Â ¹®Á¦¸¦ ÇØ°áÇÏ·Á°í ÇÑ´Ù. °¢ ÁöÁ¡ »çÀÌÀÇ °Å¸®(´ÜÀ§´Â km)¿Í ±× ±¸°£ÀÇ ÁÖÇà¼Óµµ(´ÜÀ§´Â km/h, ¾ç ¹æÇâÀÌ µ¿ÀÏÇÏ´Ù°í °¡Á¤ÇÔ)´Â [±×¸²1]°ú °°°í, °¢ ÁöÁ¡À¸·ÎºÎÅÍ H±îÁöÀÇ Á÷¼±°Å¸®´Â [±×¸²2]¿Í °°´Ù.
(°¡) »óÅ°ø°£ Ž»öÀ¸·Î ÀÌ ¹®Á¦¸¦ Ç®ÀÌÇÏ´Â ¹æ¹ýÀÇ °³³äÀ» ¼³¸íÇ϶ó. (³ª) A* ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÏ¿© ÃִܱæÀÌ °æ·Î¸¦ ±¸ÇÏ·Á°í ÇÑ´Ù. [±×¸²2]¸¦ ¿¹Ãø ºñ¿ëÀ» ±¸Çϴµ¥ È°¿ëÇÏ¿© Æò°¡ÇÔ¼ö¸¦ Á¤ÀÇÇÏ°í, ÀÌ¿¡ µû¸¥ Ž»ö Æ®¸®¸¦ º¸¿©¶ó. °¢ Ž»ö Æ®¸®ÀÇ °¢°¢ÀÇ ³ëµå¿¡´Â È®Àå ¼ø¹ø°ú Æò°¡ÇÔ¼ö °ªÀ» Ç¥½ÃÇ϶ó. (´Ù) A* ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÏ¿© Ãּҽ𣠰æ·Î¸¦ ±¸ÇÏ·Á°í ÇÑ´Ù. ¿¹Ãø ºñ¿ëÀº Æò±Õ½Ã¼Ó 17km/h¸¦ °¡Á¤ÇÏ¿© [±×¸²2]¸¦ ¹ÙÅÁÀ¸·Î Á¤ÇÏ°í, ÀÌ¿¡ µû¶ó Æò°¡ÇÔ¼ö¸¦ Á¤ÀÇÇ϶ó. ÀÌ¿¡ µû¸¥ Ž»ö Æ®¸®¸¦ (³ª)¿Í µ¿ÀÏÇÑ ¹æ¹ýÀ¸·Î º¸¿©¶ó. - ¸ñ Â÷ - ¥°. »óÅ°ø°£ Ž»öÀ¸·Î ÀÌ ¹®Á¦¸¦ Ç®ÀÌÇÏ´Â ¹æ¹ýÀÇ °³³äÀ» ¼³¸íÇ϶ó. 1. »óÅ °ø°£ Ž»öÀÇ °³³ä 2. ¿¡ÀÌ ½ºÅ¸ ¾Ë°í¸®Áò ¹®Á¦ Ç®À̸¦ À§ÇÑ °³³ä ¥±. A* ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÏ¿© ÃִܱæÀÌ °æ·Î¸¦ ±¸ÇÏ·Á°í ÇÑ´Ù. [±×¸²2]¸¦ ¿¹Ãø ºñ¿ëÀ» ±¸Çϴµ¥ È°¿ëÇÏ¿© Æò°¡ÇÔ¼ö¸¦ Á¤ÀÇÇÏ°í, ÀÌ¿¡ µû¸¥ Ž»ö Æ®¸®¸¦ º¸¿©¶ó. °¢ Ž»ö Æ®¸®ÀÇ °¢°¢ÀÇ ³ëµå¿¡´Â È®Àå ¼ø¹ø°ú Æò°¡ÇÔ¼ö °ªÀ» Ç¥½ÃÇ϶ó. ¥². A* ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÏ¿© Ãּҽ𣠰æ·Î¸¦ ±¸ÇÏ·Á°í ÇÑ´Ù. ¿¹Ãø ºñ¿ëÀº Æò±Õ½Ã¼Ó 17km/h¸¦ °¡Á¤ÇÏ¿© [±×¸²2]¸¦ ¹ÙÅÁÀ¸·Î Á¤ÇÏ°í, ÀÌ¿¡ µû¶ó Æò°¡ÇÔ¼ö¸¦ Á¤ÀÇÇ϶ó. ÀÌ¿¡ µû¸¥ Ž»ö Æ®¸®¸¦ (³ª)¿Í µ¿ÀÏÇÑ ¹æ¹ýÀ¸·Î º¸¿©¶ó. Âü°í¹®Çå ¢ºÀÚ·á³»¿ë ¹Ì¸®º¸±â
¥°. »óÅ°ø°£ Ž»öÀ¸·Î ÀÌ ¹®Á¦¸¦ Ç®ÀÌÇÏ´Â ¹æ¹ýÀÇ °³³äÀ» ¼³¸íÇ϶ó.
1. »óÅ °ø°£ Ž»öÀÇ °³³ä »óÅ °ø°£ Ž»öÀº ÃÖÀû ¸ñÇ¥¸¦ ´Þ¼ºÇϱâ À§ÇÑ Áß°£ °úÁ¤À» ÇϳªÀÇ »óÅ·Πº¸°í °¢°¢ »óÅ¿¡¼ ÃÖÀûÀÇ ¼±ÅÃÀ» ÇÏ¿© ÃÖÁ¾ÀûÀ¸·Î ÃÖ¼Ò ºñ¿ëÀ¸·Î ¸ñÇ¥¸¦ ´Þ¼ºÇÏ´Â ÀÏ·ÃÀÇ ¿¬»êÀÚ¸¦ ã´Â °úÁ¤À» ÀǹÌÇÑ´Ù. »óÅ °ø°£ Ž»ö ¹æ½Ä¿¡ ´ÙÀͽºÆ®¶ó ¾Ë°í¸®Áò, ¿¡À̽ºÅ¸ ¾Ë°í¸®Áò µî ¿©·¯ ¾Ë°í¸®ÁòÀÌ ÀÖ´Ù. ÀÌ ±Û¿¡¼ ¿¡ÀÌ ½ºÅ¸ ¾Ë°í¸®ÁòÀ» Åä´ë·Î ¹æ´ëÇÑ »óÅ °ø°£À» È¿À²ÀûÀ¸·Î Ãà¼ÒÇÏ¿© ¹®Á¦¸¦ ÇØ°áÇÑ´Ù. ¿¡À̽ºÅ¸ ¾Ë°í¸®ÁòÀº Ž»öÇÏÁö ¾ÊÀº ³ëµåµé Áß¿¡¼ »çÀü¿¡ Á¤ÇØ ³õÀº ÇÔ¼öÀÇ °ªÀÌ °¡Àå ÃÖÀûÀÎ Á¤Á¡À» ¼±ÅÃÇÏ´Â Best-First-Search ¹æ½ÄÀ» È°¿ëÇÏ°í ÀÖ´Ù. °¢°¢ÀÇ ³ëµå¿¡ ´ëÇÑ Æò°¡ÇÔ¼ö´Â Ãâ¹ß ³ëµå¿¡¼ ³ëµå k±îÁö µµ´ÞÇϴµ¥ µå´Â ºñ¿ë°ú ³ëµå K¿¡¼ ¸ñÇ¥ ³ëµå¿¡ µµ´ÞÇϴµ¥ µå´Â ºñ¿ëÀÇ ÇÕÀ¸·Î ³ªÅ¸³½´Ù. Ãâ¹ß ³ëµå¿¡¼ À̵¿ °¡´ÉÇÑ ³ëµåµéÀÇ Æò°¡ÇÔ¼ö °ªÀ» ºñ±³ÇØ ÃÖ¼Ò ºñ¿ëÀ¸·Î °¥ ¼ö ÀÖ´Â ³ëµå¸¦ ¼±ÅÃÇÏ°í Ž»öÇßÀ¸³ª ¼±ÅõÇÁö ¾ÊÀº ³ëµå´Â Æò°¡ ´ë»ó¿¡¼ Á¦¿ÜÇϴ Ž»ö °úÁ¤À» ¸ñÇ¥ ³ëµå¿¡ µµ´ÞÇÒ ¶§±îÁö ¹Ýº¹ÇÑ´Ù. ¿¡À̽ºÅ¸ ¾Ë°í¸®ÁòÀÌ ´Ù¸¥ »óÅ °ø°£ ¾Ë°í¸®Áò°ú ´Ù¸£°Ô ÃßÁ¤ÀÜ¿©°Å¸®¸¦ »ç¿ëÇÏ¿© Ž»öÀ» Çϱ⠶§¹®¿¡ ¿©Å¸ ¾Ë°í¸®Áòº¸´Ù Ž»ö ´Ü°è°¡ ÁÙ¾îµé¾î Ž»ö ½Ã°£ÀÌ ÇöÀúÈ÷ ÁÙ¾îµç´Ù. 2. ¿¡ÀÌ ½ºÅ¸ ¾Ë°í¸®Áò ¹®Á¦ Ç®À̸¦ À§ÇÑ °³³ä ¿¡À̽ºÅ¸ ¾Ë°í¸®ÁòÀÇ ³ëµå¿¡ ´ëÇÑ Æò°¡ÇÔ¼ö¸¦ Á¤ÀÇÇÏ¸é ´ÙÀ½°ú °°´Ù. ¡®Ãâ¹ß³ëµå·ÎºÎÅÍ ¸ñÇ¥ ³ëµå±îÁöÀÇ °æ·Îºñ¿ë¡¯À» f(k)À̶ó°í ÇÏ°í ¡®Ãâ¹ß³ëµå·ÎºÎÅÍ ³ëµå k±îÁöÀÇ °æ·Îºñ¿ë¡¯À» g(k)¶ó°í ÇÏ°í ¡®³ëµå k·ÎºÎÅÍ ¸ñÇ¥³ëµå±îÁöÀÇ ¿¹Ãø °æ·Îºñ¿ë¡¯À» h(k)¶ó°í ÇÑ´Ù. - Áß·« - |
¢º±³È¯ ¹× ȯºÒ ±ÔÁ¤
ÀÚ·á´Â °áÁ¦ ¿Ï·á ÈÄ ¸¶ÀÌÆäÀÌÁö¿¡¼ ÆÄÀÏ·Î ´Ù¿î·Îµå ¹ÞÀ¸½Ç ¼ö ÀÖ½À´Ï´Ù.
ÀڷḦ ´Ù¿î·Îµå ¹ÞÁö ¾ÊÀº °æ¿ì ȯºÒÀÌ °¡´ÉÇϸç, ´Ù¿î·Îµå ÈÄ¿¡´Â ȯºÒÀÌ ºÒ°¡ÇÕ´Ï´Ù. (´Ü, ÀÚ·áÀÇ ³»¿ë¿¡ ¿À·ù°¡ Àְųª ¸ñÂ÷ÀÇ ³»¿ë°ú ´Ù¸¦ °æ¿ì ȯºÒÀÌ °¡´ÉÇÕ´Ï´Ù.) |