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) ±×·¡ÇÁ¸¦ ¸¸µé¾î ³»´Â °ÍÀÌ °¡´ÉÇÏ´Ù ........ Ž»ö °úÁ¤Àº ¸ñÇ¥ ³ëµå±îÁöÀÇ °æ·Î°¡ ã¾ÆÁö¸é Á¾·áµÈ´Ù. Á» ´õ °ø½ÄÀûÀ¸·Î À̾߱âÇϸé, »óÅ°ø°£ ±×·¡ÇÁÀÇ ¾Ï½ÃÀûÀΠǥÇö¿¡´Â ¼¼ °¡Áö ±âº» ¿ä¼Ò°¡ ÀÖ´Ù.

Å©°Ô µÎ Á¾·ùÀÇ Å½»ö (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