Á¤º¸Ã³¸®ÇÐȸ ³í¹®Áö A
Current Result Document :
ÇѱÛÁ¦¸ñ(Korean Title) |
Á¦¾à¸¸Á· ÃÖÀûÈ ¹®Á¦¸¦ À§ÇÑ ¹éÆ®·¡Å· Ž»öÀÇ ±¸Á¶È |
¿µ¹®Á¦¸ñ(English Title) |
A Backtracking Search Framework for Constraint Satisfaction Optimization Problems |
ÀúÀÚ(Author) |
¼Õ¼®¿ø
Surgwon Sohn
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 18-A NO. 03 PP. 0115 ~ 0122 (2011. 06) |
Çѱ۳»¿ë (Korean Abstract) |
¸ðµç Á¦¾à¸¸Á· ÃÖÀûÈ ¹®Á¦ÀÇ Çظ¦ ±¸ÇÏ´Â ÀϹÝÈµÈ ¾Ë°í¸®ÁòÀ» ±¸ÇÏ´Â °ÍÀº ¸Å¿ì ¾î·Æ´Ù. ±×·¯³ª °áÁ¤ º¯¼öÀÇ Æ¯¼º¿¡ µû¶ó ¼¼ºÐÈµÈ ¹®Á¦´Â Çظ¦ À§ÇÑ ¾Ë°í¸®ÁòÀ» ±¸Çϱ⿡ ´õ ½±´Ù´Â °¡Á¤À» ÇÒ ¼ö ÀÖ´Ù. ÀÌ¿Í °°Àº °¡Á¤ ÇÏ¿¡ ¹®Á¦¸¦ ¼¼ºÐÈ ½ÃÅ°´Â ¹®Á¦ºÐ·ù±ÔÄ¢À» Á¦¾ÈÇÏ°í ¼¼ºÐÈ µÈ ¹®Á¦ÀÇ Æ¯¼º¿¡ ¸Â´Â ¹éÆ®·¡Å· ¾Ë°í¸®ÁòÀ» °³¹ßÇÑ´Ù. ¹éÆ®·¡Å·À» ÀÌ¿ëÇÑ ±íÀ̿켱Ž»ö¿¡¼ Çظ¦ »¡¸® ã±â À§ÇÑ ¹æ¹ý Áß Çϳª´Â Ž»öµÇ´Â ³ëµåÀÇ ¼ø¼¸¦ È¿°úÀûÀ¸·Î ¹è¿ÇÏ´Â °ÍÀÌ´Ù. Á¤Àû Ư¼ºÀÌ ¿ì¼¼ÇÑ ¹«¼± ¼¾¼ ³×Æ®¿öÅ©ÀÇ Å¬·¯½ºÅÍ Çìµå À§Ä¡¹®Á¦¿Í µ¿Àû ¹× Á¤Àû Ư¼ºÀÇ È¥ÇÕƯ¼ºÀ» °®´Â RFID ¸®´õ °£¼· ÃÖ¼ÒÈ ¹®Á¦¸¦ ¼±ÅÃÇÏ¿© ÃÖÀûÀÇ º¯¼ö ¼ø¼È ¾Ë°í¸®ÁòÀ» °³¹ßÇÏ°í ±âÁ¸ÀÇ ¹æ¹ý°ú ºñ±³ÇÏ¿´´Ù. °á°úÀûÀ¸·Î ¹®Á¦¸¦ ¼¼ºÐȽÃÅ´À¸·Î½á ü°èÀûÀΠŽ»öÀ» À§ÇÑ ¹éÆ®·¡Å·ÀÇ ±¸Á¶È¸¦ ½ÇÇöÇÏ¿´´Ù. ¶ÇÇÑ °³¹ßµÈ ¹éÆ®·¡Å· ¾Ë°í¸®ÁòÀÇ ¼º´ÉÀÌ ¿ì¼öÇÔÀ» º¸¿´´Ù. |
¿µ¹®³»¿ë (English Abstract) |
It is very hard to obtain a general algorithm for solution of all the constraint satisfaction optimization problems. However, if the whole problem is separated into subproblems by characteristics of decision variables, we can assume that an algorithm to obtain solutions of these subproblems is easier. Under the assumption, we propose a problem classifying rule which subdivide the whole problem, and develop backtracking algorithms fit for these subproblems. One of the methods of finding a quick solution is efficiently arrange for any order of the search tree nodes. We choose the cluster head positioning problem in wireless sensor networks in which static characteristics is dominant and interference minimization problem of RFID readers that has hybrid mixture of static and dynamic characteristics. For these problems, we develop optimal variable ordering algorithms, and compare with the conventional methods. As a result of classifying the problem into subproblems, we can realize a backtracking framework for systematic search. We also have shown that developed backtracking algorithms have good performance in their quality. |
Å°¿öµå(Keyword) |
¹éÆ®·¡Å· Ž»ö
Á¦¾à¸¸Á· ÃÖÀûÈ
º¯¼ö ¼ø¼È
¹®Á¦ºÐ·ù±ÔÄ¢
¹«¼±ÀÚ¿øÇÒ´ç
Backtracking Search
Constraint Satisfaction Optimization
Variable Ordering
Problem Classifying Rule
Radio Resource Allocation
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|