À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ÀÀ¿ë
Áö´ÉÁ¤º¸½Ã½ºÅÛ ¿ø·Ð : Á¤È¯¹¬ ÆíÀú, 21¼¼±â»ç, 1999, Page 378~387
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÑ ¼øÈ¸ ¿ÜÆÇ¿ø ¹®Á¦
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÑ Á¶ÇÕ ÃÖÀûÈ ¹®Á¦
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀº ½Å°æ¸ÁÀ̳ª ÆÛÁö¿Í ºñ±³Çϸé ÀÀ¿ë¸é¿¡¼´Â ´Ù¼Ò ´Ê´Ù°í ÇÒ ¼ö ÀÖ´Ù. ±×·¯³ª À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡´Â ¸Å¿ì Å« °¡´É¼ºÀÌ ÀÖ´Ù. ¿©±â¼´Â ¼øÈ¸¿ÜÆÇ¿ø ¹®Á¦(TSP : Traveling Salesman Problem), ¹èÄ¡¼³°è ¹®Á¦(LSIÀÇ ¼³°è) µîÀÇ Á¶ÇÕ ÃÖÀûÈ ¹®Á¦¿Í °°Àº ÀÀ¿ë¿¡ ´ëÇØ¼ ¼³¸íÇÑ´Ù.
½Å°æ¸ÁÀ̳ª ÆÛÁö¿Í ¸¶Âù°¡Áö·Î À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ÀÀ¿ëÀ¸·Î¼ °úÇÐ, °øÇÐ, ºñÁî´Ï½º, »çȸ°úÇÐ µî ¸¹Àº ºÐ¾ß¿¡¼ ¿¬±¸µÇ°í ÀÖ´Ù. [Ç¥ 1]¿¡ Áö±Ý±îÁö ½ÇÁ¦·Î À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¿¬±¸´ë»óÀÌ µÈ ºÐ¾ß¿Í ±× ¿¹¸¦ ³ªÅ¸³½´Ù. Job Shop ½ºÄÉÁ층À̶õ Á¤ÇØÁø ´Ù¼öÀÇ ±â°è°¡ ÀÖ°í, À̵éÀ» »ç¿ëÇÏ¿© ¿©·¯°³ÀÇ ´Ù¸¥ ÀÏÀ» È¿À²ÀÌ ÁÁ°Ô ¼öÇàÇÏ´Â ½ºÄÉÁìÀ» ±¸ÇÏ´Â °ÍÀ̸ç, ½ÇÁ¦·Î »ý»êÇöÀå µî¿¡¼ ÀÚÁÖ ³ª¿À´Â ¹®Á¦ÀÌ´Ù.
[Ç¥ 1] À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ÀÀ¿ë ºÐ¾ß |
|
ÀÀ¿ë ºÐ¾ß |
ÀÀ ¿ë »ç ·Ê |
ÃÖ Àû È |
¼öÄ¡Àû ÇÔ¼öÀÇ ÃÖÀûÈ, °¡½º ÆÄÀÌÇÁ¶óÀÎÀÇ ÃÖÀûÈ, Àü·Â ¼ÛÀü¸ÁÀÇ ÃÖÀûÈ, ÄÄÇ»ÅÍ ÀÚÆÇÀÇ ÃÖÀû ¹èÁ¤ ¹®Á¦, Ç×°ø±â ½Â¹«¿ø ¹èÁ¤ ¹®Á¦, ¼øÈ¸ ¿ÜÆÇ¿ø ¹®Á¦, ±×·¡ÇÁ ºÐÇÒ ¹®Á¦, À¯ÀüÀÚ Á¤º¸ ÇØ¼® |
¼³ °è |
VLSI ȸ·Î ¼³°è, ºñÇà±â ³¯°³ÀÇ °ø±â ¿ªÇÐÀû ¼³°è, ¿£Áø ³ëÁñÀÇ ¼³°è, ÄÄÇ»ÅÍ Åë½Å¸ÁÀÇ ÃÖÀû ¼³°è, ½ÉÀå ¹Úµ¿±âÀÇ ¼³°è, µðÁöÅÐ ÇÊÅÍ ¼³°è, ÆÛÁö Á¦¾î±â ¼³°è |
ÀΰøÁö´É |
LISP ÇÁ·Î±×·¥ÀÇ ÀÚµ¿ »ý¼º, ¹®Á¦ÇØ°á ±ÔÄ¢ÀÇ ÀÚµ¿ ½Àµæ, ½Å°æ¸Á ÇÕ¼º ¹× ÇнÀ, ÆÐÅÏ ÀνÄ, ÀÚ¿¬¾ð¾î ó¸®, ¸ÖƼ¿¡ÀÌÀüÆ® ½Ã½ºÅÛ |
½Ã½ºÅÛ ºÐ¼®
|
½Ã½ºÅÛ µ¿Á¤, ÄÉÀÌ¿Àƽ ½Ã°è¿ÀÇ ¿¹Ãø, ȯÀ² º¯È ¿¹Ãø, ´Ü¹éÁú ±¸Á¶ ºÐ¼®, ÀçÁ¤ ¹× °æÁ¦ ºÐ¾ßÀÇ ¿¹Ãø ¹× ºÐ¼® ¹®Á¦ |
Á¦¾î ¹× ·Îº¸Æ½½º |
À̵¿ ·Îº¿ÀÇ °æ·Î °èȹ, ½Å°æ¸Á ¹× ÆÛÁö·ÎÁ÷°ú À¯Àü¾Ë°í¸®ÁòÀÇ °áÇÕ¿¡ ÀÇÇÑ Á¦¾î |
¿¹¸¦ µé¸é, ½ºÄÉÁ층 ¹®Á¦´Â ±âȹ, ¼³°è, »ý»ê, Àç°í°ü¸® µî¿¡¼ »ý±â°í, °æ¿ì¿¡ µû¶ó¼ ¸Å¿ì ±Ô¸ð°¡ Å©°í µ¿½Ã¿¡ º¹ÀâÇÑ ¹®Á¦°¡ µÈ´Ù. ÀÌ·¯ÇÑ °æ¿ì, Á¾·¡ÀÇ ¼ö¸®°èȹ¹ý µîÀÇ ¹æ¹ý¿¡¼´Â ´ëÇü ÄÄÇ»Å͸¦ ÀÌ¿ëÇØµµ ÇØ¸¦ ±¸ÇÏ´Â °ÍÀÌ °ï¶õÇÏ´Ù°í ¸»ÇÒ ¼ö ÀÖ´Ù.
¼øÈ¸ ¿ÜÆÇ¿ø ¹®Á¦¶õ Á¤ÇØÁø µµ½Ã¸¦ ¸ðµÎ Çѹø¸¸ ¹æ¹®ÇÏ´Â °¡Àå ªÀº °æ·Î¸¦ ±¸ÇÏ´Â ¹®Á¦ÀÌ´Ù. ¿©±â¼ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» »ç¿ëÇÏ¿© ÇØ°áÇÏ´Â ¹æ¹ý¿¡ ´ëÇØ¼ ¼³¸íÇÑ´Ù.
¼øÈ¸
¿ÜÆÇ¿ø ¹®Á¦ÀÇ ÇØ¸¦ ±¸ÇÒ °æ¿ì¿¡´Â ƯÈ÷ ±³¹è ¹æ¹ýÀ» °í·ÁÇØ¾ß¸¸ ÇÑ´Ù. ¿©±â¼´Â
±× ÀÌÀ¯¿Í ´ëÃ¥ ¹æ¹ý¿¡ ´ëÇØ¼ ¼³¸íÇÑ´Ù. µµ½Ã A·ÎºÎÅÍ µµ½ÃF±îÁö
6°³ÀÇ µµ½Ã°¡ ÀÖ´Ù°í °¡Á¤ÇÏÀÚ. °£´ÜÇÏ°Ô Çϱâ À§ÇÏ¿© ¿°»öü°¡ µµ½ÃÀÇ ¹æ¹® ¼ø¼¸¦
±×´ë·Î ³ªÅ¸³»°í ÀÖ´Ù°í ÇÑ´Ù.
¿¹¸¦ µé¸é, ¿°»öü°¡ C B D F A EÀÎ
°æ¿ì
µµ½Ã C ¡æµµ½Ã B ¡æ µµ½Ã D ¡æ µµ½Ã F ¡æ µµ½Ã A ¡æ µµ½Ã E
ÀÇ ¼ø¼·Î ¹æ¹®ÇÑ´Ù°í ÇÑ´Ù. ÀÌ·¯ÇÑ ÇüÅÂÀÇ ¿°»öü¸¦ 2°³ »ç¿ëÇÏ¿© ÀÏÁ¡±³¹è(one-point crossover)¸¦ ¼öÇàÇØ º¸ÀÚ.
±³¹è´Â 4¹øÂ° ½Éº¼°ú 5¹øÂ° ½Éº¼ »çÀÌ¿¡¼ ¼öÇàµÇ°í ÀÖ´Ù°í Çϸé, ÀÚ½ÄÀÇ ¿°»öü´Â ´ÙÀ½°ú °°ÀÌ »ý¼ºµÈ´Ù.
ºÎ¸ð 1 : C B D F | A E ¡æ ÀÚ½Ä 1 : C B D F | E C
ºÎ¸ð 2 : A D F B | E C ¡æ ÀÚ½Ä 2 : A D F B | A E
±³¹èÀ§Ä¡
±³¹èÀ§Ä¡
ÀÚ½Ä
1Àº µµ½Ã C¸¦ 2ȸ³ª ¹æ¹®ÇÏÁö¸¸ µµ½Ã A´Â ¹æ¹®ÇÏÁö ¾Ê´Â´Ù. ÀÚ½Ä 2´Â µµ½Ã A¸¦ 2ȸ
¹æ¹®Çϰí, ´ë½Å¿¡ µµ½Ã C´Â ¹æ¹®ÇÏÁö ¾Ê°Ô µÈ´Ù. ±³¹è¿¡ ÀÇÇØ¼ ÇØ·Î¼ÀÇ ÃÖÀú Á¶°ÇÀ»
¸¸Á·ÇÏÁö ¾ÊÀº °ÍÀÌ´Ù. ÀÌ·¯ÇÑ °³Ã¼´Â Ä¡»çÀ¯ÀüÀÚ(öÈÞÝë¶îîí)¸¦ °¡Áö°í ÀÖ´Ù°í ¸»ÇÒ
¼ö ÀÖ°í, ÇØÀÇ È帰¡ ¾Æ´Ï±â ¶§¹®¿¡ µµÅµȴÙ. Ä¡»çÀ¯ÀüÀÚ°¡ ¹ß»ýÇÏ¸é ³¶ºñ°¡ ¸¹¾ÆÁö±â
¶§¹®¿¡ °¡´ÉÇÑÇÑ ¹ß»ýÇÏÁö ¾Êµµ·Ï »ý°¢ÇÒ Çʿ䰡 ÀÖ´Ù. ÀÌ·¯ÇÑ ¹®Á¦¸¦ ÇØ°áÇϱâ À§Çؼ
ÄÚµù¿¡ ÀÇÇÑ ¹æ¹ý°ú °í¾ÈµÈ ±³¹è¹ý¿¡ ÀÇÇÑ ¹æ¹ýÀÌ Á¦¾ÈµÇ°í ÀÖ´Ù.
µû¶ó¼
ÄÚµù¿¡ ÀÇÇÑ ¹æ¹ýÀ¸·Î¼ ¼ø¼ Ç¥Çö(ordinal representation)À» ¼³¸íÇϰí, ±³¹è¹ý¿¡
ÀÇÇÑ ¹æ¹ýÀ¸·Î¼´Â ºÎºÐ ÀÏÄ¡ ±³¹è(partially matched crossover)À» ¼³¸íÇÑ´Ù.
(1) ¼ø¼Ç¥Çö(ÄÚµù¿¡ ÀÇÇÑ ¹æ¹ý)
¼ø¼Ç¥Çö¿¡¼´Â
¨ç
ÃÖÃÊ¿¡ µµ½Ã¸¦ ¾ËÆÄºª ¼ø¼·Î ´Ã¾î¼± µµ½Ã ¸®½ºÆ®¸¦ ¸¸µé¾î µÐ´Ù.
¨è ´ÙÀ½¿¡ ¹æ¹® ¼ø¼·Î ´Ã¾î¼± µµ½Ã°¡ ¾ËÆÄºª ¼øÀ¸·Î ´Ã¾î¼± µµ½Ã ¸®½ºÆ®ÀÇ ¿ÞÂÊÀ¸·ÎºÎÅÍ ¸î ¹øÂ°¿¡ Àִ°¡¸¦ Á¶»çÇϰí, ±× ¼ýÀڷΠġȯÇÑ´Ù. À̶§, µµ½Ã ¸®½ºÆ®·ÎºÎÅÍ ±× µµ½Ã(¾ËÆÄºª)¸¦ »èÁ¦Çϸç, ÀÌ·¯ÇÑ Á¶ÀÛÀ» ¹Ýº¹ÇÏ¿© °£´Ù.
±×·¯¸é, ¿¹¸¦ µé¾î ¼³¸íÇϱâ·Î ÇÑ´Ù. óÀ½¿¡ µµ½Ã¸¦ ¾ËÆÄºª ¼øÀ¸·Î ´Ã¾î¼± µµ½Ã ¸®½ºÆ®¸¦ ¸¸µç´Ù.
A
B C D E F
(¹æ¹®¼ø¼ : 1 2 3
4 5 6)
¾ÕÀÇ
ºÎ¸ð 1(C B D F A E)¸¦ ÄÚµùÇØ º¸ÀÚ.
¿ì¼± µµ½Ã C¿¡ ÁÖ¸ñÇÏ¸é µµ½Ã
¸®½ºÆ®ÀÇ ¿ÞÂʺÎÅÍ 3¹øÂ°¿¡ Àֱ⠶§¹®¿¡ ºÎ¸ð 1ÀÇ C¸¦ 3À¸·Î ġȯÇÑ´Ù. µ¿½Ã¿¡ µµ½Ã
¸®½ºÆ® C¸¦ »èÁ¦ÇÑ´Ù.
ºÎ¸ð 1 : 3 B D F A E (µµ½Ã ¸®½ºÆ® : A B D E F)
´ÙÀ½¿¡ µµ½Ã B¿¡ ÁÖ¸ñÇÏ¸é µµ½Ã ¸®½ºÆ®ÀÇ 2¹øÂ°¿¡ Àֱ⠶§¹®¿¡ ºÎ¸ð 1ÀÇ B¸¦ 2·Î ġȯÇÏ°í µµ½Ã ¸®½ºÆ®ÀÇ B¸¦ »èÁ¦ÇÑ´Ù.
ºÎ¸ð 1 : 3 2 D F A E (µµ½Ã ¸®½ºÆ® : A D E F)
°°Àº Á¶ÀÛÀ» ¹Ýº¹ÇØ °¡¸é
ºÎ¸ð 1 : 1 3 2 2 3 1 1 (µµ½Ã ¸®½ºÆ® : 0À¸·Î µÇ¾ú´Ù.)
ºÎ¸ð 2¿¡ ´ëÇØ¼µµ ¸¶Âù°¡Áö·Î
ºÎ¸ð
2 : A D F B E C (µµ½Ã ¸®½ºÆ® : A B C D E F)
ºÎ¸ð 2 : 1 3 4 1 2 1 (µµ½Ã
¸®½ºÆ® : 0À¸·Î µÇ¾ú´Ù.)
ÀÌ·¸°Ô ÇÏ¿© Ç¥ÇöµÈ 2°³ÀÇ ¿°»öü¿¡ ¾Õ¿¡¼¿Í ¸¶Âù°¡Áö·Î ÀÏÁ¡ ±³¹è¸¦ ¼öÇàÇØ º¸ÀÚ. ±³¹è´Â 4¹øÂ° ±âÈ£¿Í 5¹øÂ° ±âÈ£ »çÀÌ¿¡¼ ¼öÇàµÇ¾ú´Ù.
ºÎ¸ð 1 : 3 2 2 3 | 1 1 ¡æ ÀÚ½Ä 1 : 3 2 2 3 | 2 1
ºÎ¸ð 2 : 1 3 4 1 | 2 1 ¡æ ÀÚ½Ä 2 : 1 3 4 1 | 1 1
±³¹èÀ§Ä¡ ±³¹èÀ§Ä¡
ÀÚ½Ä 1, ÀÚ½Ä 2 °¢°¢¿¡ ´ëÇØ¼ ¾ÕÀÇ °æ¿ì¿Í °°Àº Á¶ÀÛÀ» ½Ç½ÃÇÑ´Ù. ¿¹¸¦ µé¸é, ÀÚ½Ä 1ÀÇ °æ¿ì,
ÀÚ½Ä 1 : 3 2 2 3 2 1 (µµ½Ã ¸®½ºÆ® : A B C D E F)
Á¦ÀÏ ¿ÞÂÊÀÇ 3¿¡ ÁÖ¸ñÇϸé, µµ½Ã ¸®½ºÆ® 3¹øÂ°´Â CÀ̱⠶§¹®¿¡ ÀÚ½Ä 1ÀÇ 3Àº C·Î ġȯÇÒ ¼ö°¡ ÀÖ´Ù. µ¿½Ã¿¡ µµ½Ã ¸®½ºÆ® C¸¦ Á¦°ÅÇÏ´Â Á¶ÀÛÀ» ¹Ýº¹ÇØ °£´Ù.
ÀÚ½Ä 1 : C 2 2 3 2 1 (µµ½Ã ¸®½ºÆ® : A B D E F)
±×·¯¸é,
ÀÚ½Ä 1 : 3 2 2 3 | 2 1 ¡æ C B D F E A
ÀÚ½Ä 2 : 1 3 4 1 | 1 1 ¡æ A D F B C E
±³¹èÀ§Ä¡
°¡ µÇ°í, °¢ µµ½Ã¸¦ ¸ðµÎ 1ȸ¸¸ ¹æ¹®ÇÏ´Â ¼øÈ¸ ¿ÜÆÇ¿ø ¹®Á¦ÀÇ ÇØ·Î¼ ÃÖÀú Á¶°ÇÀ» ¸¸Á·ÇÏ´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù.
(2)
ºÎºÐÀÏÄ¡ ±³¹è(±³¹è¹ý¿¡ ÀÇÇÑ ¹æ¹ý)
ºÎºÐÀÏÄ¡
±³¹è¿¡¼´Â
¡á 2°³ÀÇ ¿°»öü¿¡ ÀÖ¾î¼ ±³¹è½Ãų ºÎºÐÀ» °áÁ¤ÇÑ´Ù.
¡á ±×¸®°í ´ëÀÀµÇ´Â ½Éº¼ÀÇ Á¶¸¦ ¸¸µç´Ù.
¡á 2°³ÀÇ ¿°»öü¿¡ ÀÖ¾î¼ ´ëÀÀÇÒ ½Éº¼³¢¸®¸¦ ±³È¯ÇÑ´Ù.
[±×¸² 1] ºÎºÐÀÏÄ¡ ±³¹è
[±×¸² 1]Àº ºÎºÐÀÏÄ¡ ±³¹èÀÇ ¿¹¸¦ ³ªÅ¸³½´Ù. ÀÌ ¿¹¿¡¼´Â 7°ú 6, 2¿Í 4°¡ ±³¹è ºÎºÐ¿¡ ÀÖ¾î¼ ´ëÀÀÇϰí ÀÖ´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù. µû¶ó¼ °¢°¢ÀÇ ¿°»öü¿¡ ÀÖ¾î¼ 7°ú 6, 2¿Í 4¸¦ ±³È¯ÇÏ¿© ³ÖÀ½À¸·Î½á ±³¹è°¡ Á¾·áÇÑ´Ù. ÀÌ °æ¿ìµµ °¢ µµ½Ã¸¦ ¸ðµÎ 1ȸ¸¸ ¹æ¹®ÇÏ´Â ¿ÜÆÇ¿ø ¹®Á¦ÀÇ ÇØ·Î¼ ÃÖÀú Á¶°ÇÀ» ¸¸Á·ÇÏ´Â °ÍÀ» ¾Ë ¼ö ÀÖ´Ù.
¡á
¼ø¼Ç¥Çö
ÀÚ½Ä
1, ÀÚ½Ä 2´Â °¢°¢ ºÎ¸ð 1, ºÎ¸ð 2ÀÇ ±³¹è À§Ä¡·ÎºÎÅÍ ¿ÞÂÊÀ» °è½ÂÇÑ´Ù. ±×·¯³ª ¿À¸¥ÂÊ¿¡
´ëÇØ¼´Â ÀÚ½Ä 1Àº ºÎ¸ð 2ÀÇ ²÷¾îÁø ÂÊÀ», ÀÚ½Ä 2´Â ºÎ¸ð 1ÀÇ ²÷¾îÁø ÂÊÀ» °è½ÂÇϰÔ
µÈ´Ù. ƯÈ÷ ±³¹èÀ§Ä¡°¡ ¿°»öüÀÇ ¿ÞÂÊ¿¡ ¿À¸é, ¾çÄ£¸ðµÎ À¯Àü ÇüÁúÀÌ ¸¹Àº ºÎºÐÀ»
ÀÒ¾î ¹ö¸± À§Ç輺ÀÌ ÀÖ°Ô µÈ´Ù.
¡á
ºÎºÐÀÏÄ¡ ±³¹è
Ä¡»ç
À¯ÀüÀÚÀÇ ¹ß»ýÀ» ¹æÁöÇÏ´Â È¿°ú´Â ÀÖÁö¸¸, ¼ø¼Ç¥ÇöÀÇ °æ¿ì¿Í ¸¶Âù°¡Áö·Î ±³¹è¿¡
ÀÇÇØ¼ ¾çÄ£ÀÇ À¯ÀüÇüÁúÀ» ÀÒ¾î ¹ö¸± À§ÇèÀÌ ÀÖ´Ù. À̵éÀÇ °øÅëÁ¡Àº À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ
º»ÁúÀÎ Àû¸ñ°¡¼³(Âü°í)¿¡¼ÀÇ ºÎǰÀ¸·Î¼ÀÇ Àû¸ñÀÌ ÆÄ±«µÇ´Â À§Ç輺ÀÌ ÀÖ´Ù. ¼øÈ¸
¿ÜÆÇ¿ø ¹®Á¦¿¡¼ÀÇ "Àû¸ñ"Àº ºÎºÐÀûÀÎ ¹æ¹®¼ø¼(subtour)°¡ ÀÖ´Ù. ÀÌ ºÎºÐ
¹æ¹®¼ø¼¸¦ ÆÄ±«µÇÁö ¾Êµµ·Ï ±³¹è¸¦ ¼öÇàÇÏ·Á°í ÇÏ´Â ¾ÆÀ̵ð¾î(ºÎºÐ¹æ¹®-±³È¯ ±³¹è)¸¦
¿©±â¼ ¼Ò°³ÇÑ´Ù. ºÎºÐ¹æ¹®À» ÆÄ±«ÇÏÁö ¾Ê±â À§ÇÏ¿© ±³¹è½Ã 2°³ÀÇ ºÎ¸ð¿¡¼ °øÅëÀÇ
¿ä¼Ò¸¦ Æ÷ÇÔÇÑ ºÎºÐÀ» ã¾Æ³½´Ù. À̵éÀ» ±³È¯ ȤÀº ¿ª¼ø¿¡ ÀÇÇØ¼ ÀÚ½ÄÀ» »ý¼ºÇÏ´Â
°ÍÀÌ´Ù. [±×¸² 2]¿¡ ºÎºÐ¹æ¹® ±³È¯±³¹èÀÇ ¿¹¸¦ ³ªÅ¸³½´Ù.
ºÎ¸ð´Â
¾ÕÀÇ [±×¸² 1]ÀÇ °æ¿ì¿Í °°´Ù. 2°³ÀÇ ºÎ¸ð¿¡¼ °øÅëÀÇ ¿ä¼Ò¸¦ °¡Áö°í ÀÖ´Â ºÎºÐÀº
Á¡¼±À¸·Î µÑ·¯½×¿©Áø ºÎºÐÀÌ´Ù. ±×¿Í °ü·ÃÇÏ¿© °øÅë¿ä¼Ò´Â {2, 4, 5, 6}ÀÌ´Ù.
[±×¸² 2] ºÎºÐ¹æ¹®ÀÇ ±³È¯±³¹è
ÀÚ½ÄÀº ´ÙÀ½°ú °°ÀÌÇÏ¿© »ý¼ºµÈ´Ù.
ÀÚ½Ä
1 : ºÎ¸ð 1¿¡ ºÎ¸ð 2ÀÇ ºÎºÐ¹æ¹®(Á¡¼±ºÎºÐ)À» ±×´ë·Î °è½Â
ÀÚ½Ä 2 : ºÎ¸ð 2¿¡
ºÎ¸ð 1ÀÇ ºÎºÐ¹æ¹®(Á¡¼±ºÎºÐ)À» ±×´ë·Î °è½Â
ÀÚ½Ä 3 : ºÎ¸ð 1¿¡ ºÎ¸ð 2ÀÇ ºÎºÐ¹æ¹®(Á¡¼±ºÎºÐ)À»
¿ª¼øÀ¸·Î °è½Â
ÀÚ½Ä 4 : ºÎ¸ð 2¿¡ ºÎ¸ð 2ÀÇ ºÎºÐ¹æ¹®(Á¡¼±ºÎºÐ)À» ¿ª¼øÀ¸·Î °è½Â
ºÎºÐ¹æ¹® ±³È¯±³¹è¿¡¼´Â ÀÌ·¸°Ô ÇÏ¿© 2°³ÀÇ ºÎ¸ð·ÎºÎÅÍ ¿ø¸®ÀûÀ¸·Î 4°³ÀÇ ÀÚ½ÄÀÌ »ý¼º °¡´ÉÇÏ´Ù. ÀÌ ¹æ¹ýÀº À¯Àü¿¡ ÀÖ¾î ÇüÁú À¯ÀüÀ» Áß½ÃÇÑ ¹æ¹ýÀ̶ó°í ¸»ÇÒ ¼ö ÀÖ´Ù. ¼øÈ¸ ¿ÜÆÇ¿ø ¹®Á¦ »Ó¸¸ ¾Æ´Ï¶ó ´Ù¸¥ ¹®Á¦·ÎÀÇ ÀÀ¿ëÀÌ ÃæºÐÈ÷ °¡´ÉÇÑ ¾ÆÀ̵ð¾î¶ó°í ¸»ÇÒ ¼ö ÀÖÀ» °ÍÀÌ´Ù.
Àû ¸ñ °¡ ¼³ |
³ª¹«·Î ¸ðÇü °Ç¹°À» ¸¸µé ¶§, ¸ñÀ縦 °¡°øÇÏ¿© ¸¸µå´Â °Íº¸´Ù ÀÌ¹Ì ¾î¶² Àû¸ñÀ» Á¶ÇÕÇÏ¿© ¸¸µå´Â ÂÊÀÌ È¿À²ÀûÀÌ´Ù. À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡¼´Â ¿°»öü Áß¿¡¼ ³ôÀº ÀûÀÀµµ¸¦ º¸¿©ÁÖ´Â ºÎºÐÀ» Àû¸ñ¿¡ ºñÀ¯ÇÏ´Â °ÍÀÌ °¡´ÉÇÏ´Ù. |
¿©±â¼´Â ´Ü¼øÇÏ¸é¼ È¿°ú°¡ Å« ¹è³¶(Knapsack)¹®Á¦ÀÇ ÀÀ¿ë ¿¹¸¦ ¼³¸íÇϱâ·Î ÇÑ´Ù. ¹è³¶¹®Á¦¶õ [±×¸² 3]¿¡ º¸¿©ÁÖ´Â °Í°ú °°Àº ¹è³¶¿¡ ¹°°ÇÀ» ³ÖÀ» ¶§, Á¦ÇÑ ¿ë·®À» ³Ñ¾î¼Áö ¾Ê´Â ¹üÀ§¿¡¼ ä¿ö ³Ö´Â ¹æ¹ýÀ» ±¸ÇÏ´Â(ä¿ö³Ö´Â ȹ°À» °áÁ¤ÇÑ´Ù) °ÍÀÌ´Ù. ÀÌ ¹®Á¦´Â ¾ð¶æ º¸¾Æ¼´Â ¿¹Á¦¸¦ À§ÇÑ ¿¹Á¦°°Áö¸¸, ½ÇÀº ¸¹Àº ÀÀ¿ë¿¹ÀÇ ±âÃʰ¡ µÈ´Ù. ¿¹¸¦ µé¸é,
¡á ÀÏÁ¤ ¿¹»ê ³»¿¡¼ÀÇ ¹°ÀÚÀÇ ±¸ÀÔ
¡á Á¾¾÷¿øÀÇ ´É·Â¿¡ ±âÃÊÇÑ Àλç°ü¸®
¡á ±ÝÀ¶°Å·¡ ÀÇ»ç°áÁ¤(ÀÏÁ¤ÇÑ ÀÚ±ÝÀ» »ç¿ëÇÏ¿© À§ÇèÀÌ ÃÖ¼Ò°¡ µÇµµ·Ï ÇÏ´Â ÁÖ½Ä, ä±Ç
µîÀ¸·ÎÀÇ ÅõÀÚ¹ýÀ» °áÁ¤ÇÑ´Ù.
¡á ȹ°¿î¼Û ½Ã½ºÅÛ
µîÀ»
µé ¼ö ÀÖ´Ù. À̵éÀº "¾î¶² Á¶°ÇÀ» ¸¸Á·ÇÏ¸é¼ ÃÖ´ëÀÇ È¿À²À» 20kgÀ» ³ÑÁö ¾Ê´Â
¹üÀ§¿¡¼ °¡´ÉÇÑ ¸¹ÀÌ Ã¤¿ö³Ö´Â Á¶ÇÕÀ» ±¸ÇÑ´Ù"°í ÇÏ´Â °øÅë ºÎºÐÀÌ ÀÖ´Ù. µû¶ó¼,
À§ÀÇ ¿¹Á¦ À̿ܿ¡µµ ¸¹Àº ÀÀ¿ëÀÌ ÀÖ´Ù. ±×·¯¸é, ¹è³¶¹®Á¦¸¦ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ¸·Î
ÇØ°áÇÏ´Â ¹æ¹ýÀ» ¼³¸íÇϱâ·Î ÇÑ´Ù.
[±×¸² 3]°ú °°ÀÌ È¹°Àº ¸ðµÎ
10°³À̰í, ±× Áß¿¡¼ 20kgÀ» ³ÑÁö ¾Ê´Â ¹üÀ§¿¡¼ °¡´ÉÇÑÇÑ ¸¹ÀÌ ¹è³¶¿¡ ³Ö´Â Á¶ÇÕÀ»
±¸Çϱâ·Î ÇÑ´Ù.
[±×¸² 3] ¹è³¶¹®Á¦
(1)
À¯ÀüÀÚÇüÀÇ °áÁ¤
¿°»öüÀÇ
°¢ ºñÆ®¸¦ °¢ ȹ°¿¡ ´ëÀÀ½Ã۱â·Î ÇÑ´Ù. °á±¹ ¾î¶² ºñÆ®°¡ 1À̸é, ´ëÀÀÇϴ ȹ°À»
¹è³¶¿¡ ³Ö°í, 0ÀÌ¸é ³ÖÁö ¾Ê´Â´Ù. ȹ°Àº ¸ðµÎ 10°³À̱⠶§¹®¿¡ °¢ ¿°»öü´Â 10ºñÆ®
±æÀÌÀÇ 2Áø ºÎÈ£·Î Ç¥ÇöµÈ´Ù. ¿¹¸¦ µé¸é, ¾î¶² ¿°»öü¸¦ 1010100001À̶ó°í ÇßÀ» ¶§,
°ªÀÌ 1ÀÎ ºñÆ®´Â(¿ÞÂÊ¿¡¼ºÎÅÍ Çì¾Æ·Á¼) 1¹øÂ°, 3¹øÂ°, 5¹øÂ°À̱⠶§¹®¿¡ ȹ° 1,
ȹ° 3, ȹ° 5, ȹ° 10À» ¹è³¶¿¡ ³Ö´Â °ÍÀÌ µÈ´Ù.
(2)
ÀûÀÀµµÀÇ Æò°¡
ÀûÀÀµµ¸¦
°è»êÇÒ ¶§¿¡´Â
¡á °³Ã¼°¡ Á¶°ÇÀ» ¸¸Á·ÇÏ´Â °æ¿ì ¡æÃ¤¿ö ³Ö´Â ȹ°ÀÇ ¿ë·®ÀÇ ÇÕ°è
¡á Á¾¾÷¿øÀÇ ´É·Â¿¡ ±âÃÊÇÑ Àλç°ü¸® ¡æ¿ë·®À» ³Ñ¾î¼´Â ºÐ·®¿¡ ±âÃÊÇÏ¿© Àû´çÇÏÁö ¾Ê´Â °ª°ú
°°ÀÌ ¼³Á¤ÇÏ¿© µÎ¸é ÇØ°¡ µÇÁö ¾Ê´Â °³Ã¼´Â °¨¼ÒÇϰí ÇØ´Â Â÷·Ê·Î °¡Àå ÀûÀýÇÑ ÇØ¿¡ °¡±î
¿öÁö±â ½±°Ô µÈ´Ù.
ÈÄ¿¡ ¼±ÅÃÀ̳ª ±³¹è, µ¹¿¬º¯ÀÌ¿¡ °üÇØ¼´Â ¾ÕÀý¿¡¼ ¼³¸íÇÑ º¸ÅëÀÇ ¹æ¹ýÀ» »ç¿ëÇÒ ¼ö°¡ ÀÖ´Ù. ȹ°ÀÇ ¼ö°¡ 10ÀÎ °æ¿ì´Â Á¶ÇÕÀÇ ¼ö´Â °¢ ȹ°¿¡ ´ëÇØ¼ ³Ö´ÂÁö, ³ÖÁö ¾Ê´ÂÁö 2°¡Áö°¡ Àֱ⠶§¹®¿¡ 2ÀÇ 10½Â, Áï ¾à 1,000ÀÌ µÈ´Ù. ÀÌ Á¤µµÀ̸é, Çϳª Çϳª Á¶»çÇÏ¿© ¸ðµç Á¶ÇÕ¿¡ ´ëÇØ¼ Á¶»çÇØ °¡´Â °ÍÀÌ °¡´ÉÇÏ´Ù.
±×·¯³ª ȹ°ÀÇ ¼ö°¡ 40°³¿¡ ´ÞÇϸé, Á¶ÇÕÀÇ ¼ö´Â 1Á¶¸¦ ³Ñ°í, 55°³°¡ µÇ¸é Á¶ÀÌ»óÀÇ ´ÜÀ§ÀÎ Áï 1°æ(1µÚ¿¡ 0ÀÌ 16°³)À̳ª µÈ´Ù. ¾î¶² ¹®Çå¿¡ ÀÇÇϸé, ȹ°ÀÇ ¼ö°¡ 50°³ÀÎ °æ¿ì, ¸ðµç °æ¿ì¸¦ µé¾î¼ Á¶»çÇÏ´Â ´Ü¼øÇÑ ¹æ¹ý°ú ºñ±³ÇÏ¿© À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡ ÀÇÇÑ ¹æ¹ýÀº ¼ö¸¸¹è ºü¸£´Ù°í º¸°íµÇ°í ÀÖ´Ù. ¶ÇÇÑ ´Ù¸¥ ¹®Çå¿¡ ÀÇÇϸé, ȹ°ÀÇ ¼ö°¡ 40°³ÀÎ °æ¿ì, °³Àοë ÄÄÇ»ÅÍ¿¡¼µµ ¸î Ãʸ¸¿¡ ÇØ°áÇÒ ¼ö ÀÖ´Ù°í º¸°íµÇ°í ÀÖ´Ù. ´õ¿íÀÌ ¸ðµç °æ¿ì¸¦ µé¾î¼ Á¶»çÇÏ´Â ´Ü¼øÇÑ ¹æ¹ý°ú ºñ±³ÇÏ¿© ¼ö½Ê¸¸¹è ºü¸£´Ù°í º¸°íµÇ°í ÀÖ´Ù. ¾î´ÀÂÊÀ¸·Î ÇØµµ ¹è³¶¹®Á¦¿Í °°Àº "¾î¶² Á¶°ÇÀ» ¸¸Á·Çϸé¼, ÃÖ´ëÀÇ È¿À²À» °ÅµÑ ¼ö ÀÖ´Â Á¶ÇÕÀ» ±¸ÇÏ´Â ¹®Á¦"´Â À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡ ¸Å¿ì ÀûÀýÇÑ ºÐ¾ß¶ó°í ¸»ÇÒ ¼ö ÀÖ´Ù.
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀ» ÀÀ¿ëÇÒ ¶§ÀÇ ¿äÁ¡Àº ´ÙÀ½°ú °°´Ù.
¨ç
¹®Á¦°¡ À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡ ÀÇÇÑ ÇØ¹ý¿¡ ÀûÇÕÇѰ¡¸¦ ÆÇ´Ü
¹®Á¦°¡
¸¹Àº Á¶ÇÕ ÁßÀ¸·ÎºÎÅÍ ÇØ¸¦ ±¸ÇÏ´Â °Í°ú °°Àº ¼ºÁúÀ» °¡Á³´Â°¡ÀÇ ÆÇ´ÜÀÌ ¸Å¿ì Å«
¿äÁ¡ÀÌ´Ù.
¨è ÇØÀÇ ¸íÈ®ÇÑ Æò°¡¹ý
ÇØÀÇ
Æò°¡¹ýÀÌ ºÒ¸íÈ®ÇÏ¸é °¢ °³Ã¼ÀÇ ÀûÀÀµµÀÇ Á¤Àǵµ ºÒ¸íÈ®Çϰí, ¹«ÀǹÌÇØÁö¸ç ´ÜÁö
¸¹Àº ÇØ È常¸ÀÌ ¾ò¾îÁö°Ô µÈ´Ù.
´õ¿íÀÌ À¯ÀüÀÚ ¾Ë°í¸®Áò¿¡¼´Â
ÀûÀÀµµÀÇ °è»êÀ» ºóµµ·Î ¼öÇàÇϱ⠶§¹®¿¡ ÀûÀÀµµÀÇ °è»êÀÌ º¹ÀâÇÑ °æ¿ì¿¡´Â ¾ÆÁÖ
À¯È¿ÇÑ ¹æ¹ýÀÌ µÇÁö ¾Ê´Â´Ù.
¨é
ÇØ¸¦ À¯ÀüÀڷΠǥÇöÇÒ ¼ö Àִ°¡
¿°»öü
»ó¿¡¼ ´É¼÷ÇÏ°Ô Ç¥ÇöÇÒ ¼ö ÀÖ´ÂÁö ¾î¶²Áö°¡ À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ Å« ÀüÁ¦°¡ µÈ´Ù.
¶ÇÇÑ ±× ¶§, ³ª¹« ½×±â(Building block)°¡¼³¿¡ ÀÇÇÑ È¿°ú¸¦ °í·ÁÇÒ Çʿ䰡 ÀÖ´Ù. µ¿½Ã¿¡
¿°»öü »ó¿¡¼ °¡´ÉÇÑ °£´ÜÇÏ°Ô Ç¥ÇöµÉ ¼ö ÀÖµµ·Ï ¿°»öü »óÀ¸·ÎÀÇ ¹®Á¦ÀÇ Ç¥ÇöÀ»
¿¬±¸ÇÏ´Â °ÍÀÌ´Ù.
¶ÇÇÑ
°¢°¢ÀÇ ¹®Á¦¿¡ ´ëÇØ¼ ÄÚµù ¹æ¹ýÀÇ ¿¬±¸°¡ ÇÊ¿äÇÏ´Ù. Ç¥Çö ¹æ¹ýÀÇ ÁÁ°í ³ª»Ý¿¡ µû¶ó
½Ã½ºÅÛÀÇ Æ¯¼ºÀÌ Å©°Ô º¯Çϱ⠶§¹®ÀÌ´Ù.
À¯ÀüÀÚÇüÀ» °áÁ¤ÇÒ ¶§¿¡´Â
´ÙÀ½°ú °°Àº »çÇ×µéÀÌ Áß¿äÇÏ´Ù.
¡á ÇØ È帴 ¸ðµÎ ¿°»öü·Î¼ Ç¥ÇöÇÒ ¼ö ÀÖÀ» °Í
¡á ÇØ Èĺ¸¿Í ¿°»öü´Â 1´ë1·Î ´ëÀÀÁö¿ï ¼ö ÀÖÀ» °Í
¡á ºÎ¸ðÀÇ ÇüÁúÀ» ±³¹è¿¡ ÀÇÇØ ÀڽĿ¡°Ô ÀûÀýÇÏ°Ô ÀüÇØÁú ¼ö ÀÖÀ» °Í
¨ê
´Ù¸¥ ±â¼ú°úÀÇ Á¶ÇÕ
À¯ÀüÀÚ ¾Ë°í¸®ÁòÀÇ ¹®Á¦Á¡À¸·Î¼ ±¹¼ÒÀûÀΠŽ»ö ´É·ÂÀÌ ¾ø´Â °ÍÀ» µé ¼ö ÀÖ´Ù. µû¶ó¼ ´Ù¸¥
±â¼ú°úÀÇ Á¶ÇÕÀÌ ¸Å¿ì È¿°úÀûÀÌ´Ù.
¨ë
½ÇÁ¦ ½Ã½ºÅÛ¿¡¼ ÇØ°¡ ±¸ÇØÁöÁö ¾Ê¾ÒÀ» °æ¿ìÀÇ ´ëÀÀÃ¥
ÇØ¸¦
Ç×»ó ±¸ÇÒ ¼ö ÀÖ´Ù´Â º¸ÀåÀÌ ¾ø±â ¶§¹®¿¡ ±× ´ëÃ¥À» °í·ÁÇØµÑ Çʿ䰡 ÀÖ´Ù. ¿¹¸¦µé¸é,
±× ½ÃÁ¡¿¡¼ °¡Àå ÃÖÀûÀÇ °ÍÀ» ÇØ·Î¼ °£ÁÖÇϰųª ȤÀº ´Ù¸¥ Ãʱâ Áý´ÜÀ» »ç¿ëÇÏ¿©
´Ù½Ã ¹Ýº¹ÇÏ´Â ¹æ¹ý µîÀ» °í·ÁÇÒ ¼ö ÀÖ´Ù.