¾Ë°í¸®Áò
À¯ÇÑÇÑ ´Ü°è¸¦ ÅëÇØ ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇÑ ÀýÂ÷³ª ¹æ¹ýÀ¸·Î¼ ¿ø·¡´Â Àεµ¿¡¼ ¾Æ¶ø¸¦ °ÅÃÄ À¯·´¿¡ º¸±ÞµÈ ÇÊ»êÀ» ¶æÇϸç, ¾Æ¶øÀÇ ¼öÇÐÀÚÀÎ ¾ËÄ⸮Áî¹ÌÀÇ À̸§¿¡¼ À¯·¡ÇÑ´Ù.
¾Ë°í¸®ÁòÀº Àß Á¤ÀÇµÇ°í ¸í¹éÇÑ ±ÔÄ¢µéÀÇ ÁýÇÕ ¶Ç´Â À¯ÇÑ ¹øÀÇ ´Ü°è ³»¿¡¼ ¹®Á¦¸¦ Ç®±â À§ÇÑ °úÁ¤ÀÌ´Ù. ¿¹¸¦ µé¸é, ÁÖ¾îÁø Á¤È®µµ¿¡ ¸Âµµ·Ï xÀÇ ÄÚ»çÀÎ °ªÀ» °è»êÇϱâ À§ÇÑ ´ë¼öÀûÀÎ °úÁ¤µµ ¾Ë°í¸®Áò¿¡ ÇØ´çµÈ´Ù. °æÇèÀû Áö½Ä(heuristic)°ú ¹Ý´ëµÇ´Â ¿ë¾îÀÌ´Ù.
¿ªÇà·Ä
A¸¦ nÂ÷ Á¤»ç°¢Çà·Ä, ¶Ç E¸¦ nÂ÷ ´ÜÀ§Çà·ÄÀ̶ó°í ÇÒ ¶§ AB=BA=E °¡ µÇ´Â nÂ÷ Á¤»ç°¢Çà·Ä B°¡ Á¸ÀçÇϸé A´Â Á¤Ä¢À̶ó ÇÏ°í, ÀÌ ¶§ÀÇ Çà·Ä B¸¦ AÀÇ ¿ªÇà·ÄÀ̶ó Çϸç, A-1À¸·Î ³ªÅ¸³½´Ù.
ÀÓÀÇÀÇ Á¤»ç°¢Çà·Ä¿¡ ´ëÇÏ¿© ¿ªÇà·ÄÀÌ ¾ðÁ¦³ª Á¸ÀçÇÑ´Ù°í´Â ÇÒ ¼ö ¾øÀ¸³ª,¸¸ÀÏ Á¸ÀçÇÑ´Ù¸é ´Ü ÇÑ °¡Áö·Î Á¤ÇØÁø´Ù. A-1ÀÌ Á¸ÀçÇϱâ À§ÇÑ ÇÊ¿äÃæºÐÁ¶°ÇÀº ¡®AÀÇ Çà·Ä½Ä |A|¡Á0¡¯ÀÌ´Ù.
¹«ÇÑ´ë
¹«ÇÑÈ÷ Å« Àý´ë°ªÀ» ÃëÇÒ ¼ö ÀÖ´Â º¯¼ö·Î º¯¼ö x°¡ ¾ç(£«) ¶Ç´Â À½(£)À¸·Î¼ ±× ¿ª¼ö°¡ 0¿¡ ÇѾøÀÌ °¡±î¿öÁú ¶§ ÀÌ º¯¼ö´Â ¾ç ¶Ç´Â À½ÀÇ ¹«ÇÑ´ë°¡ µÈ´Ù°í Çϸç, ±âÈ£·Î ¡®x¡æ£«¡Ä¡¯ ¶Ç´Â ¡®x¡æ£¡¦(»ý·«)
|