[인공지능] CSP Backtracking 탐색

Backtracking search

d : Domain 의 개수

n : 변수의 개수

d^n 개의 leaf node 수가 필요

 

Backtracking : DFS 방식으로 searching 하다가 오답임이 확정되면 더 깊이 들어가지 않고 돌아 나오는 기법

 

문제에 특화된(specific) heuristic 이 아닌 일반적인 heuristic 이 사용됨

 

값이 할당되지 않은 변수를 찾을 때 사용하는 hueristic

SA 를 해결할까? Q를 해결할까? 고민하는 단계를 말함

• MRV(Minumum-Remaining-Values) heuristic : fail first
  변수에 들어갈 수 있는 Domain 의 수가 몇개 안남아서 실패를 빨리 찾게해주는 기법
  

  

• Degree heuristic

• 차수(연결된 간선의 수) 가 높은 node 먼저 선택

• MRV 를 사용할 수 없는 상태 (initial state)에서 많이 사용

• 위 그림에서는 SA 가 차수 5로 선택됨

Value ordering 에서 사용하는 heuristic

Q를 해결하기로 결정했다면 Q 의 가능한 Domain, {r, b} 중 무엇을 할당할까 고민하는 문제

LCV (Least-Constraining-Value) heuristic (fail-last) 를 주로 사용

제약을 적게 두어서 경우의 수가 많은 domain 을 선택하는 것

 

위 그림에서는 Q가 r 을 선택했을 때 SA는 b, NSW는 g,b 로 총 3개, b를 선택했을 때 SA 가 None, NSW가 r,g로 2개 가능

따라서 경우의 수가 더 많은 b를 선택

 

Variable 과 Value ordering 기법이 다른것은 수학적으로 증명되진 않았으나 실험적으로 알려졌기 때문임