|
|
제 목 |
[RE]iLOG Solve에서 Domain Reduction Propagation에 대해서 |
|
작성자 |
김태현 |
작성일 |
2004-04-13 |
조회수 |
808 회 |
|
| 첨부파일 |
첨부된 파일없음.
|
|
안녕하세요..
1번 질문에 대한 답변입니다.
우선, Domain Reduction과 Propagation에 대한 설명을 먼저 간단히 드리겠습니다.
Domain Reduction 이라는 것은 어떤제약이나, 다른 변수의 Domain이 변경될 경우, 해당 변수의 불필요한 Domain을 제거 하는 일련의 방법을 말합니다.
이렇게 Domain의 변경이 이루어 지면, 그 변수와 연관된 또 다른 변수들도 마찬가지로 Domain Reduction이 일어나게 되어있습니다.
이런 도미노 현상을 Propagation 이라고 합니다.
간단히 예를 들면,
X = [5..20], Y = [0..10] Z = [0..20]; 이런 integer 변수가 있다고,
제약1: X < Y,
제약2: X + Z = 10;이 있다면
X의 domain은 제약 1에 의해 [5..9]까지만 남게 되고, X 변수가 포함된 제약2에 영향의 미쳐, Z의 domain도 줄어드는 현상이 벌어집니다.
어떤제약을 먼저들어가든지 간에 Domain Reduction과 Propagation이 일어난 후의 결과는 같습니다.
즉, 우선 순위는 존재하지 않습니다.
물론 Solver 내부 적으로 Domain Reduction과 Propagation의 Level을 조절할수 있는 기능이 있습니다..
즉, 문제의 난이도가 어려운 경우는 Propagation을 많이 하면 도움이 되겠지만, 문제의 난이도가 쉬운경우는 굳이 Propagation Level을 높게 하지 않아도 되겠죠..
2번 질문에 대한 답변입니다.
초기해를 찾는지, 최적해를 찾는지의 여부에 따라 원하는 답을 얻을수 있습니다.
초기해를 찾는 경우, 랜덤하게 선택되는게 아니고, 아시다시피 DFS, DDS, LDS등의 여러 search 방법에 의해 초기해를 찾을수 있습니다.
물론, Solver 내에서 핸들링이 가능합니다.
최적해를 찾는 경우는 먼저 초기해를 찾고, 초기해가 Low Bound가 되어 초기해를 갱신하면서 최적해를 찾습니다. 이과정에서 불필요한 node는 Propagation의 의해 저절로 탐색을 하지 않습니다.
도움이 되었는지 모르겠네요.. |
|
|
|
