State Space
¹®Á¦ ÇØ°á (Problem Solving) Àº ´Ù¾çÇÑ ¹®Á¦ »óÅ·Π±¸¼ºµÈ ¹®Á¦ °ø°£ (problem space) ÀÇ Å½»ö (Search) À¸·Î ÈçÈ÷ ¼³¸íµÈ´Ù. ÇÑ »óÅ (state) ´Â ¹®Á¦ÀÇ ÇØ°á Á¤µµ¸¦ ³ªÅ¸³½´Ù. ¹®Á¦ ÇØ°áÀÚ°¡ óÀ½ ´ç¸éÇÏ´Â »óȲÀ» Ãʱ⠻óÅÂ, ¸ñÇ¥·Î °¡°í ÀÖ´Â »óȲÀ» Áß°£ »óÅÂ, ±×¸®°í ¸ñÇ¥¸¦ ¸ñÇ¥ »óÅ (goal state) ¶ó°í ÇÑ´Ù....... ¿©±â¼ ¹®Á¦´Â ¹®Á¦ °ø°£ÀÇ Ãʱ⠻óÅ¿¡¼ ¸ñÇ¥ »óÅ¿¡ À̸£±â±îÁö ÀÏ·ÃÀÇ °¡´ÉÇÑ Á¶ÀÛÀÚµéÀ» ã´Â °ÍÀÌ´Ù. '¹®Á¦' °ø°£Àº »óÅÂÀÇ ¹Ì·Î·Î ±×¸®°í Á¶ÀÛÀÚ´Â »óÅ °£À» À̵¿ÇÏ´Â Åë·Î·Î »ý°¢ÇÒ ¼ö ÀÖ´Ù. ÀÌ·¸°Ô »ý°¢Çϸé, 'ÇØ°á' Àº °Ë»ö (Search), Áï ¹®Á¦ ÇØ°áÀÚ°¡ »óŵéÀÇ ¹Ì·Î¿¡¼ ÀûÀýÇÑ Åë·Î¸¦ ã´Â °úÁ¤À» ÅëÇØ ÀÌ·ç¾îÁø´Ù. Ä«³×±â ¸á·±´ëÇб³ÀÇ Allen Newell °ú Herbert Simon ÀÌ ¹®Á¦ ÇØ°áÀ» »óÅ °ø°£ÀÇ °Ë»öÀ¸·Î º¸´Â ÀÔÀåÀ» ¹ßÀü½ÃÄ×°í, ÀÌ »ý°¢Àº ÀÎÁö½É¸®ÇÐ °ú ÀΰøÁö´É (Artificial Intelligence) ¸ðµÎ¿¡¼ Áö¹èÀûÀÎ ¹®Á¦ ÇØ°á ºÐ¼®ÀÌ µÇ¾ú´Ù. ..... (John R. Anderson 1995)
Chimpanzee problem solving : ħÆÒÁö´Â ¹Ù³ª³ª¸¦ ¾î¶»°Ô ¸ÔÀ» °ÍÀΰ¡?
½ÇÁ¦ÀûÀÎ ¹®Á¦µéÀÇ ´ëºÎºÐÀº Ž»ö°ø°£ÀÌ ³Ê¹« Å©±â
¶§¹®¿¡ ¸í½ÃÀûÀÎ ±×·¡ÇÁ·Î Ç¥ÇöÇÒ ¼ö ¾ø´Ù. ÀÌ °æ¿ì¿¡´Â ¸í½ÃÀûÀÎ (explicit) °èȹ
(planning) ¿¡¼ ¼³¸íÇÑ
±âº»ÀûÀΠŽ»ö ¹æ¹ý¿¡ ¼öÁ¤ÀÌ ÇÊ¿äÇÏ´Ù. ù°, ÀÌ·¯ÇÑ ¹®Á¦µéÀº Ž»ö ¹®Á¦·Î ¼³Á¤ÇÏ´Â
¹æ¹ý¿¡ ÀÖ¾î¼ ¸Å¿ì ½ÅÁßÇØ¾ß ÇÑ´Ù. µÑ°, ¹æ´ëÇÑ Å½»ö ±×·¡ÇÁ¸¦ ¾Ï½ÃÀûÀ¸·Î (implicitly)
Ç¥ÇöÇÏ´Â ¹æ¹ýÀÌ ÀÖ¾î¾ß ÇÑ´Ù. ¼Â°, ÀÌ·± ¹æ´ëÇÑ ±×·¡ÇÁ¸¦ Ž»öÇϱâ À§ÇÑ È¿À²ÀûÀÎ
¹æ¹ýÀÌ ÀÖ¾î¾ß ÇÑ´Ù...... ½ÃÀÛ »óÅ·κÎÅÍ ÇൿÀ» ÃëÇÏ¿© µµ´ÞµÉ ¼ö ÀÖ´Â
»óÅ°ø°£ ±×·¡ÇÁ¿¡¼ÀÇ ¿µ¿ªÀº ½ÃÀÛ »óÅÂÀÇ Á¤ÀÇ¿Í °¢ Çൿµé¿¡ ´ëÇÑ Á¤ÀÇ¿¡ ÀÇÇØ
¾Ï½ÃÀûÀ¸·Î Ç¥ÇöµÈ´Ù. µû¶ó¼ ¿øÄ¢ÀûÀ¸·Î ¾Ï½ÃÀûÀÎ (implicit) ±×·¡ÇÁ Ç¥ÇöÀ¸·ÎºÎÅÍ
¸í½ÃÀûÀÎ (explicit) ±×·¡ÇÁ¸¦ ¸¸µé¾î ³»´Â °ÍÀÌ °¡´ÉÇÏ´Ù ........
Ž»ö °úÁ¤Àº ¸ñÇ¥ ³ëµå±îÁöÀÇ °æ·Î°¡ ã¾ÆÁö¸é Á¾·áµÈ´Ù. Á» ´õ °ø½ÄÀûÀ¸·Î À̾߱âÇϸé,
»óÅ°ø°£ ±×·¡ÇÁÀÇ ¾Ï½ÃÀûÀΠǥÇö¿¡´Â ¼¼ °¡Áö ±âº» ¿ä¼Ò°¡ ÀÖ´Ù.
1. ½ÃÀÛ ³ëµå (start node) ÀÇ Ç¥Çö. ÀÌ°ÍÀº ¹®Á¦ÀÇ Ãʱ⠻óŸ¦ ³ªÅ¸³»´Â ÀÚ·á ±¸Á¶ÀÌ´Ù.
2. ÇϳªÀÇ »óŸ¦ ³ªÅ¸³»´Â Ç¥ÇöÀ» ¾î¶² Çൿ¿¡ ´ëÇÑ °á°ú »óŸ¦ ³ªÅ¸³»´Â Ç¥ÇöÀ¸·Î ¹Ù²Ù¾îÁÖ´Â ÇÔ¼ö. ÀÌ ÇÔ¼ö¸¦ ¿¬»êÀÚ (operator) ¶ó°í ÇÑ´Ù. ¿ì¸®°¡ ´Ù·ç´Â ¹®Á¦¿¡ ÀÖ¾î¼ À̵éÀº ÇൿÀÇ È¿°ú¿¡ ´ëÇÑ ¸ðµ¨ÀÌ´Ù. ¾î¶² ³ëµå¿¡ ÇϳªÀÇ ¿¬»êÀÚ°¡ Àû¿ëµÇ¸é ±× ³ëµåÀÇ ÀÚ½Ä ³ëµå Áß Çϳª¸¦ ¸¸µé¾î³»°Ô µÈ´Ù.
3. ¸ñÇ¥ Á¶°Ç (goal condition). ÀÌ°ÍÀº ¾î¶² »óÅ ǥÇö¿¡ ´ëÇØ Âü ¶Ç´Â °ÅÁþÀÌ µÇ´Â ÇÔ¼öÀ̰ųª, ¸ñÇ¥ »óÅ¿¡ ÇØ´çÇÏ´Â ½ÇÁ¦ »óÅ ǥÇöµéÀÇ ¸®½ºÆ®°¡ µÈ´Ù.
Å©°Ô µÎ Á¾·ùÀÇ Å½»ö (Search) ¹æ¹ýÀÌ ÀÖ´Ù. ±× Áß ÇÑ°¡Áö´Â ¸ñÇ¥±îÁöÀÇ °æ·Î¸¦ ã´Â µ¥ ÀÖ¾î¼ Å½»ö°ø°£ÀÇ ¾î¶² ÇÑ ºÎºÐÀ» ´Ù¸¥ ºÎºÐ¿¡ ºñÇØ ¼±È£ÇÒ ¸¸ÇÑ ÆÇ´Ü ±Ù°Å°¡ ¾ø´Â °æ¿ì¿¡ »ç¿ëÇÏ´Â ¹æ¹ýÀÌ´Ù. ÀÌ·± °æ¿ì¸¦ ¹«Á¤º¸ (uninformed or blind) Ž»ö À̶ó°í ÇÑ´Ù. ´Ù¸¥ ÇÑ °¡Áö´Â Ž»öÀ» ÇÑ ºÎºÐ¿¡ ÁýÁß½Ãų ¼ö ÀÖµµ·Ï ÇØÁÖ´Â ±× ¹®Á¦ °íÀ¯ÀÇ Á¤º¸°¡ ÀÖ´Â °æ¿ì¿¡ »ç¿ëÇÏ´Â ¹æ¹ýÀÌ´Ù. ÀÌ·± °æ¿ì¸¦ ÈÞ¸®½ºÆ½ (heuristic) Ž»ö À̶ó°í ÇÑ´Ù. ..... (Nils J.Nilsson 1998)
¹®Á¦ °ø°£°ú °Ë»ö (Problem Space and Search) : John R. Anderson
»óÅ°ø°£ ±×·¡ÇÁ (State-Space Graphs) »óÅ°ø°£ÀÇ ¼³Á¤ (Formulating the State Space) : Nils J.Nilsson