정보처리학회논문지A (The KIPS Transactions:PartA)

한국정보처리학회 (Korea Information Processing Society)
권호 표지
DOI QR코드

DOI QR Code

제약만족 최적화 문제를 위한 백트래킹 탐색의 구조화

A Backtracking Search Framework for Constraint Satisfaction Optimization Problems

  • 손석원 (호서대학교 벤처전문대학원)
  • 투고 : 2011.02.08
  • 심사 : 2011.04.07
  • 발행 : 2011.06.30
PDF 다운로드
⟨ 이전 논문 다음 논문 ⟩

초록

모든 제약만족 최적화 문제의 해를 구하는 일반화된 알고리즘을 구하는 것은 매우 어렵다. 그러나 결정 변수의 특성에 따라 세분화된 문제는 해를 위한 알고리즘을 구하기에 더 쉽다는 가정을 할 수 있다. 이와 같은 가정 하에 문제를 세분화 시키는 문제분류규칙을 제안하고 세분화된 문제의 특성에 맞는 백트래킹 알고리즘을 개발한다. 백트래킹을 이용한 깊이우선탐색에서 해를 빨리 찾기 위한 방법 중 하나는 탐색되는 노드의 순서를 효과적으로 배열하는 것이다. 정적 특성이 우세한 무선 센서 네트워크의 클러스터 헤드 위치문제와 동적 및 정적 특성의 혼합특성을 갖는 RFID 리더 간섭 최소화 문제를 선택하여 최적의 변수 순서화 알고리즘을 개발하고 기존의 방법과 비교하였다. 결과적으로 문제를 세분화시킴으로써 체계적인 탐색을 위한 백트래킹의 구조화를 실현하였다. 또한 개발된 백트래킹 알고리즘의 성능이 우수함을 보였다.

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.

키워드

참고문헌

  1. M. Ercsey-Ravasz, T. Roska, and Z. Neda, "Cellular neural networks for NP-hard optimization," 11th Int'l Workshop on Cellular Neural Networks and Their Applications, pp.52-56, Jul., 2008.
  2. P. Hell and J. Nesetril, "Colouring, constraint satisfaction, and complexity," Computer Science Review, Vol.2, Issue3, pp.143-163, Dec., 2008. https://doi.org/10.1016/j.cosrev.2008.10.003
  3. F. Rossi, P. van Beek, and T. Walsh (Eds.), Handbook of Constraint Programming, Elsevier, 2006.
  4. Z. Yujun, X. Jinyun, and S. Haihe, "A category theoretic approach to search algorithms: Towards a unified implementation for branch-and-bound and backtracking," 4th Int'l Conference on Computer Science & Education, pp.845-850, Jul., 2009.
  5. S. Prestwich, "Local search and backtracking vs non-systematic backtracking," AAAI 2001 Fall Symposium on Using Uncertainty within Computation, 2001.
  6. H. Terashima-Marin, J.C. Ortiz-Bayliss, P. Ross, and M. Valenzuela-Rendon, "Hyper-heuristics for the dynamic variable ordering in constraint satisfaction problems," In proceedings of the 10th annual conference on genetic and evolutionary computation, pp.571-578, ACM, 2008.
  7. I. P. Gent, E. MacIntyre, P. Prosser, B. M. Smith, and T. Walsh, "An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem," in Principles and Practice of Constraint Programming, pp.179-193, 1996.
  8. S. W. Golomb and L. D. Baumert, "Backtrack programming," Journal of the ACM, Vol.12, No.4, pp.516-524, 1965. https://doi.org/10.1145/321296.321300
  9. R. M. Haralick and G. L. Elliott, "Increasing tree search efficiency for constraint satisfaction problems," Artificial Intelligence, Vol.14, No.3, pp.263-313, 1980. https://doi.org/10.1016/0004-3702(80)90051-X
  10. J. Patel, J.W. Chinneck, "Active-constraint variable ordering for faster feasibility of mixed integer linear programs," Mathematical Programming, Vol.110 Issue3, pp.445-474 Sep., 2007. https://doi.org/10.1007/s10107-006-0009-0
  11. F. Boussemart, F. Hemery, C. Lecoutre, and L. Sais, "Boosting systematic search by weighting constraints." In Proc. 16th European Conference on Artificial Intelligence-ECAI'04, pp.146-150, IOS, 2004.
  12. E. C. Freuder, "A sufficient condition for backtrack-free search," Journal of ACM, Vol.29, No.1, pp.24-32, 1982. https://doi.org/10.1145/322290.322292
  13. D. Brelaz, "New methods to color the vertices of a graph," Communication of the ACM, Vol.22, No.4, pp.251-256, 1979. https://doi.org/10.1145/359094.359101
  14. B. M. Smith, "The Brelaz heuristic and optimal static orderings." in CP series, Lecture Notes in Computer Science, J. Jaffar, Ed., Vol.1713. Springer, pp.405-418, 1999. https://doi.org/10.1007/978-3-540-48085-3_29
  15. C. Bessiere and J.-C. Regin, "MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems," in CP series. Lecture Notes in Computer Science, E. C. Freuder, Ed., Vol.1118. Springer, pp.61-75, 1996.
  16. R.J. Wallace, "Determining the principles underlying performance variation in csp heuristics," International Journal on Artificial Intelligence Tools, Vol.17 Issue5, pp.857-880, Oct., 2008, https://doi.org/10.1142/S0218213008004199
  17. B. Hnich, T. Walsh, and B. M. Smith, "Dual modelling of permutation and injection problems," Journal of Artificial Intelligence Ressearch, Vol.21, pp.357-391, 2004.
  18. W.B. Heinzelman, A. Chandrakasan, and H. Balakrishnan, ''An application-specific protocol architecture for wireless microsensor networks'', IEEE Transactions on Wireless Communications, 1(4), pp.660-670, 2002. https://doi.org/10.1109/TWC.2002.804190
  19. S. Zhou, Z. Luo, E. Wong, C.J. Tan, and J. Luo, "Interconnected RFID Reader Collision Model and its Application in Reader Anti-collision," 2007 IEEE International Conference on RFID, pp.212-219, 2007. https://doi.org/10.1109/RFID.2007.346171
  20. 김원태, 안광선, 이성준, "RFID 시스템에서 비트 변화 감지를 이용한 가변 슬롯 트리 기반 충돌 방지 알고리즘," 정보처리학회논문지A, 제16-A권, 제4호, pp.289-298, 2009. 8. https://doi.org/10.3745/KIPSTA.2009.16-A.4.289

피인용 문헌

  1. Channel Assignment for RFID Readers in Dense Reader Environments vol.18, pp.2, 2013, https://doi.org/10.9708/jksci.2013.18.2.069