Áß°£°úÁ¦¹°
2019³â 2Çбâ ÀΰøÁö´É Áß°£½ÃÇè°úÁ¦¹° °øÅë(»óÅ°ø°£ Ž»ö, A* ¾Ë°í¸®Áò)
Àڷᱸ¼º³»¿ë ÀΰøÁö´É °úÁ¦¹° ¿Ï¼ºº»(°ßº»)
ÇØ´çÇаú ÄÄÇ»ÅÍ°úÇаú ÀÚ·áÃâ°£ÀÏ 2019³â 9¿ù 1ÀÏ
Çгâ/Çбâ 4Çгâ/2Çбâ ÆäÀÌÁö¼ö 6
ÀÚ·áÇüÅ ZIP (167.37 KB) ÀÚ·á°¡°Ý 8,100¿ø
Àڷᱸ¼º
ÄÄÇ»ÅÍ4_ÀΰøÁö´É_°øÅë_°úÁ¦¹°¿Ï¼ºº»(°ßº»).hwp
!! ÆǸŰ¡ ÁßÁö µÈ ÀÚ·áÀÔ´Ï´Ù.
* º» ÀÚ·á´Â ³ë¿ìÁ¸¿¡¼­ ½Ç½Ã°£À¸·Î Á¦°øÇÏ°í ÀÖ½À´Ï´Ù.
¢ºÀÚ·á¸ñÂ÷ ¹× ÁÖÁ¦
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)¶ó°í ÇÑ´Ù.




- Áß·« -
¢º±³È¯ ¹× ȯºÒ ±ÔÁ¤
ÀÚ·á´Â °áÁ¦ ¿Ï·á ÈÄ ¸¶ÀÌÆäÀÌÁö¿¡¼­ ÆÄÀÏ·Î ´Ù¿î·Îµå ¹ÞÀ¸½Ç ¼ö ÀÖ½À´Ï´Ù.
ÀڷḦ ´Ù¿î·Îµå ¹ÞÁö ¾ÊÀº °æ¿ì ȯºÒÀÌ °¡´ÉÇϸç, ´Ù¿î·Îµå ÈÄ¿¡´Â ȯºÒÀÌ ºÒ°¡ÇÕ´Ï´Ù.
(´Ü, ÀÚ·áÀÇ ³»¿ë¿¡ ¿À·ù°¡ Àְųª ¸ñÂ÷ÀÇ ³»¿ë°ú ´Ù¸¦ °æ¿ì ȯºÒÀÌ °¡´ÉÇÕ´Ï´Ù.)