Search

 

½±°Ô ¾ê±âÇϸé ÄÄÇ»ÅÍ°úÇп¡¼­ÀÇ Å½»ö (search) ¾Ë°í¸®ÁòÀº ¹®Á¦¸¦ ÀÔ·ÂÇؼ­ ±× ¹®Á¦¿¡ ´ëÇÑ ÇØ (solution)¸¦ ¾ò´Â ¾Ë°í¸®ÁòÀÌ´Ù. ¹®Á¦¸¦ Ç®±âÀ§ÇØ ÄÄÇ»ÅÍ°úÇÐÀÚ°¡ ¿¬±¸ÇÏ´Â ´ëºÎºÐÀÇ ¾Ë°í¸®ÁòµéÀº ÀÏÁ¾ÀÇ Å½»ö ¾Ë°í¸®ÁòµéÀÌ´Ù (¹®Á¦ÇØ°á (Problem Solving)). ¹®Á¦¸¦ Ǫ´Â °¡´ÉÇÑ Çظ¦ ¸ðµÎ ¸ð¾ÆµÐ ÁýÇÕÀ» Ž»ö°ø°£ (search space, »óÅ°ø°£ (State Space)) ¶ó°í ºÎ¸¥´Ù. ¹«Á¤º¸ Ž»ö (Uninformed Search) ¾Ë°í¸®ÁòÀº Ž»ö°ø°£À» Ž»öÇÏ´Â °¡Àå ´Ü¼øÇÏ°í Á÷°üÀûÀÎ (intuitive) ¹æ¹ýÀ» »ç¿ëÇÑ´Ù. ¹Ý¸é¿¡ Á¤º¸Å½»ö (informed search, ÈÞ¸®½ºÆ½ Ž»ö (Heuristic Search)) ¾Ë°í¸®ÁòÀº Ž»ö½Ã°£À» ÁÙÀ̱â À§ÇØ Å½»ö°ø°£ÀÇ ±¸Á¶¿¡ ´ëÇÑ Áö½ÄÀ» ÀÀ¿ëÇÏ´Â ÈÞ¸®½ºÆ½À» »ç¿ëÇÑ´Ù.

term   paper   site    lab   book  company   demo

¹«Á¤º¸ Ž»ö (Uninformed Search) Àº ¹®Á¦ÀÇ µ¶Æ¯ÇÑ ¼ºÁúÀ» °í·ÁÇÏÁö ¾Ê´Â ¾Ë°í¸®ÁòÀÌ´Ù. µû¶ó¼­ ½±°Ô ±¸Çö°¡´ÉÇÏ°í, ¶È°°Àº ±¸Çö¹æ½ÄÀ» Ãß»óÈ­ (abstraction) Çؼ­ ³ÐÀº ¹üÀ§ÀÇ ¹®Á¦µé¿¡ »ç¿ë°¡´ÉÇÏ´Ù. ¹®Á¦´Â ´ëºÎºÐÀÇ »óÅ°ø°£ÀÌ ¸Å¿ì Å©´Ù´Â °ÍÀ̸ç, ¹«Á¤º¸Å½»ö (ƯÈ÷ Æ®¸®ÀÇ °æ¿ì) Àº ÀÛÀº Å©±âÀÇ °æ¿ì¿¡¸¸ ÇÕ¸®ÀûÀÎ ½Ã°£ÀÌ ¼Ò¿äµÈ´Ù´Â °ÍÀÌ´Ù. µû¶ó¼­ Ž»ö½Ã°£À» ºü¸£°Ô ÇϱâÀ§ÇØ, ¶§·Î´Â Á¤º¸Å½»ö (informed search) ¸¸À» »ç¿ëÇÑ´Ù.

¸®½ºÆ® Ž»ö (list search) ¾Ë°í¸®ÁòÀº Ž»ö ¾Ë°í¸®ÁòÁß¿¡¼­ °¡Àå ±âº»ÀûÀÎ °ÍÀÌ´Ù. ¸ñÀûÀº ¾î¶² Å° (key) ¿¡ ÀÇÇØ ÁýÇÕÀÇ ÇÑ ¿ä¼Ò¸¦ ã´Â °ÍÀÌ´Ù (Å°¿Í °ü·ÃµÈ ´Ù¸¥ Á¤º¸¸¦ Æ÷ÇÔÇÏ´Â). ÀÌ°ÍÀÌ ÄÄÇ»ÅÍ°úÇп¡¼­ ÀϹÝÀûÀÎ ¹®Á¦À̱⠶§¹®¿¡, ÀÌ ¾Ë°í¸®ÁòÀÇ °è»êº¹Àâµµ´Â Àß ¿¬±¸µÇ¾ú´Ù. °¡Àå ½¬¿î ¾Ë°í¸®ÁòÀº ¼±ÇüŽ»ö (linear search) À¸·Î¼­ ¸®½ºÆ®ÀÇ °¢ ¿ä¼Ò¸¦ ¼ø¼­´ë·Î °Ë»çÇÑ´Ù. ........ ´ëºÎºÐÀÇ list search ¾Ë°í¸®Áò, Áï linear search, binary search, self-balancing binary search trees ¿Í °°Àº °ÍµéÀº ÁÖ¾îÁø Å°º¸´Ù ´õ Å©°Å³ª ÀÛÀº ¸ðµç °ªÀ» ã±âÀ§ÇØ ºÎ°¡ÀûÀÎ ºñ¿ëÀÌ °ÅÀÇ µéÁö ¾Êµµ·Ï È®ÀåµÉ ¼ö Àִµ¥, ±×°ÍÀº range search ¶ó°í ºÒ¸®¿î´Ù. ±×·¯³ª ¿¹¿ÜÀûÀ¸·Î hash tables Àº ±×·¯ÇÑ Å½»öÀ» È¿À²ÀûÀ¸·Î ¼öÇàÇÒ¼ö ¾ø´Ù.

Æ®¸®Å½»ö (Tree search) ¾Ë°í¸®ÁòÀº Ž»ö±â¼úÀÇ ÇÙ½ÉÀÌ´Ù. Æ®¸® (Tree) °¡ ¸í½ÃÀû (explicit) ÀÌµç ¾Ï½ÃÀû (implicit) À̵ç (¿¹¸¦µé¸é ¹ÙµÏ (Baduk) ¿¡¼­ ó·³) Æ®¸®ÀÇ ³ëµå¸¦ Ž»öÇÑ´Ù. ±âº»¿ø¸®´Â ÇϳªÀÇ ³ëµå°¡ ÀڷᱸÁ¶¿¡¼­ ¾ò¾îÁö°í ±× ÀڽĵéÀÌ °Ë»çµÇ¾î ÀڷᱸÁ¶¿¡ ´õÇØÁø´Ù´Â °ÍÀÌ´Ù. ÀڷᱸÁ¶¸¦ Á¶ÀÛÇÏ¿©, Æ®¸®´Â level º°·Î Ž»öÇϰųª (³Êºñ¿ì¼± Ž»ö (Breadth First Search)) ¸ÕÀú leaf node ¿¡ µµ´ÞÇÏ°í³ª¼­ backtracking (±íÀÌ¿ì¼± Ž»ö (Depth First Search)) ÇÏ´Â µîÀÇ ´Ù¸¥ ¼ø¼­·Î Ž»öÇÑ´Ù. Æ®¸®Å½»öÀÇ ´Ù¸¥ ¿¹µéÀº ¹Ýº¹Àû ±íÀÌÁõ°¡ Ž»ö (Iterative Deepening Depth-first Search), Depth-limited search, ¾ç¹æÇâ Ž»ö (Bidirectional Search), Uniform-cost search µîÀÌ ÀÖ´Ù.

±×·¡ÇÁ ÀÌ·Ð (Graph Theory) ¿¡¼­ÀÇ ¸¹Àº ¹®Á¦µéÀÌ Å½»ö¾Ë°í¸®ÁòÀ¸·Î ÇØ°áµÉ ¼ö Àִµ¥, ¿¹¸¦µé¸é Dijkstra's algorithm, Kruskal's algorithm, nearest neighbour algorithm, Prim's algorithm °ú °°Àº °ÍÀÌ´Ù. ÀÌ·±°ÍµéÀº Æ®¸®¾Ë°í¸®ÁòÀÇ È®ÀåÀ̶ó°í º¼ ¼ö ÀÖ´Ù.

Á¤º¸Å½»ö (informed search, ÈÞ¸®½ºÆ½ Ž»ö (Heuristic Search)) ¿¡¼­´Â ±× ¹®Á¦¿¡¸¸  µ¶Æ¯ÇÑ ¾î¶² ÈÞ¸®½ºÆ½ÀÌ ÇϳªÀÇ °¡À̵å·Î¼­ »ç¿ëµÈ´Ù. ÁÁÀº ÈÞ¸®½ºÆ½ (Heuristic) Àº Á¤º¸Å½»öÀ» µå¶ó¸¶Æ½ÇÏ°Ô ¸¸µé¸ç ¾î¶² ¹«Á¤º¸Å½»öº¸´Ùµµ ´É°¡ÇÏ´Â ¼º´ÉÀ» ³½´Ù. ¸®½ºÆ®¿¡¼­´Â Ź¿ùÇÑ informed list-search ¾Ë°í¸®ÁòÀº °ÅÀÇ ¾ø´Ù. °¡±îÀÌ¿¡ ±× ¹®Á¦¿¡ ¹ÙÅÁÇÑ ÈÞ¸®½ºÆ½ÀÌ ÀÖ´Â hashing functionÀ» °¡Áø hash table Àº °¡´ÉÇÑ ¿µ¿ªÀÌ´Ù. ´ëºÎºÐÀÇ Á¤º¸Å½»ö ¾Ë°í¸®ÁòÀº Æ®¸®¿¡¼­ »ç¿ëµÇ¸ç ÃÖ»ó¿ì¼± Ž»ö (Best-first Search), A* ¾Ë°í¸®Áò ¿Í °°Àº °ÍÀÌ´Ù. ¹«Á¤º¸Å½»ö ¾Ë°í¸®Áò¿¡¼­ ó·³ Á¤º¸Å½»öµµ È®ÀåµÇ¾î ±×·¡ÇÁ (Graph) ¿¡¼­ ÀÛµ¿ÇÒ ¼ö ÀÖ´Ù.

°ÔÀÓ (Game) ÇÁ·Î±×·¥°ú machine planning °ú °°Àº ÀΰøÁö´É (Artificial Intelligence) ÀÇ ´Ù¸¥ À¯ÇüµéÀº ÃÖ¼ÒÃÖ´ë (Mini-max) ¾Ë°í¸®Áò, search tree pruning, ¾ËÆĺ£Å¸ °¡ÁöÄ¡±â (Alpha-Beta Pruning) °ú °°Àº Ž»ö ¾Ë°í¸®ÁòÀ» »ç¿ëÇϴµ¥ ±×·¯ÇÑ °ÍÀ» Àû´ëŽ»ö (adversarial search) ¶ó°í ÇÑ´Ù.

Á¦¾à ¸¸Á· (constriant satisfaction) Àº Á¦¾àÁ¶°Ç ¸¸Á· ¹®Á¦ (Constraint Satisfaction Problem) ¸¦ Ǫ´Â Ž»öÀÇ À¯ÇüÀ¸·Î¼­, ÇϳªÀÇ °æ·Î¸¦ ã±âº¸´Ù´Â ´Ü¼øÈ÷ º¯¼ö¿¡ ÇÒ´çµÈ °ªÀ» ã´Â °ÍÀÌ´Ù. ±× º¯¼öµéÀº ¾î¶² ¼ø¼­·Îµµ ó¸®µÉ ¼ö Àֱ⠶§¹®¿¡ º¸ÅëÀÇ Æ®¸®Å½»ö ¾Ë°í¸®ÁòÀº ³Ê¹« ºñÈ¿À²ÀûÀÌ´Ù.  Á¦¾à ¹®Á¦¸¦ Ǫ´Â ¹æ¹ýµéÀº combinatorial search ¿Í backtracking ¸¦ µé ¼ö Àִµ¥, µÑ´Ù Á¦¾à¹®Á¦µé°ú °ü·ÃµÈ ÀÚÀ¯µµ (freedom) À» ÀÌ¿ëÇÑ´Ù.

string search algorithm ´Â strings ³»¿¡ ÀÖ´Â ÆÐÅϵéÀ» Ž»öÇÑ´Ù. ÀÌ°ÍÀ» ´õ È¿À²ÀûÀ¸·Î ¸¸µå´Â À¯¸íÇÑ ÀڷᱸÁ¶´Â  suffix tree ÀÌ´Ù. À¯Àü¾Ë°í¸®Áò (Genetic Algorithm) Àº »óÅ°ø°£ (State Space) À» °¨¼Ò½ÃÅ°±â À§ÇÑ ÈÞ¸®½ºÆ½À¸·Î¼­ ÁøÈ­ (Evolution) ¿¡¼­ ¾ò¾îÁø ¾ÆÀ̵ð¾î¸¦ »ç¿ëÇÑ´Ù. ¸ðÀÇ ´ã±ÝÁú (Simulated Annealing) Àº ÀÏÁ¾ÀÇ È®·ü (probabilistic) Å½»ö ¾Ë°í¸®ÁòÀÌ´Ù

°øÂ¥Á¡½É Á¤¸® (No-Free-Lunch theorems) ´Â  "°øÂ¥Á¡½É °°Àº °ÍÀº ¾ø´Ù (there ain't no such thing as a free lunch)"¿¡¼­ ³ª¿Â ¸íĪÀ¸·Î¼­, ¸ðµç ¼öÇÐÀûÀ¸·Î °¡´ÉÇÑ ¹®Á¦¿¡ ´ëÇØ, °¢°¢ÀÇ Å½»ö¾Ë°í¸®ÁòÀÌ Æò±ÕÀûÀ¸·Î ¼öÇàÇÏ´Â (do on average as well as any other) ÀÌÀ¯¸¦ ¼³¸íÇÑ´Ù. ÀÌ°ÍÀº °¢ Ž»ö¾Ë°í¸®Áò¿¡ Á¸ÀçÇÏ´Â ÆíÂ÷ (bias) ¶§¹®À̸ç, ¾Ë°í¸£ÁòÀÌ ¸¸µå´Â °¡Á¤µéÀÌ ¶§¶§·Î Á¤È®ÇÏÁö ¾Ê±â ¶§¹®ÀÌ´Ù. °øÂ¥Á¡½É Á¤¸®´Â ÇØ´ç ¿µ¿ª¿¡ »ç¿ë°¡´ÉÇÑ Áö½ÄÀÌ ¸¹Áö ¾ÊÀº °¡¿îµ¥¼­ »ç¿ëµÇ´Â À¯Àü¾Ë°í¸®Áò (Genetic Algorithm) °ú ¸ðÀÇ ´ã±ÝÁú (Simulated Annealing) °ú °°Àº Åë»óÀûÀΠŽ»ö¾Ë°í¸®Áò¿¡ ´ëÇÑ ¹Ý¹Ú ³í¸®·Î¼­ »ç¿ëµÈ´Ù. (No-Free-Lunch theorems for search) ....... (Wikipedia : Search algorithm)

site :

AI Topics : Web Search     AI Topics : Search

Wikipedia : Search algorithm     Wikipedia : Web search engine

°Ë»öÀÇ °³¿ä : ÀüºÏ´ë ¹Ú¼øö ±³¼ö´Ô µ¿¿µ»ó

AI on the Web : Search and Game Playing : Stuart Russell

video :

Innovations in AI and Search : CITRIS : Peter Norbig, 2009/09/02