- 제약만족 최적화 문제를 위한 백트래킹 탐색의 구조화
- ㆍ 저자명
- 손석원,Sohn. Surg-Won
- ㆍ 간행물명
- 정보처리학회논문지. The KIPS transactions. Part A. Part A
- ㆍ 권/호정보
- 2011년|3호|pp.115-122 (8 pages)
- ㆍ 발행정보
- 한국정보처리학회
- ㆍ 파일정보
- 정기간행물| 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.