Cs188AI Wiki

General Info[]


Cutset conditioning is a structure improvement method that turns nearly tree structured CSPs into tree structure CSPs

Cutset conditioning.png


  1. Choose a cutset
  2. Instantiate that cutset in all possible ways
  3. Remove the values that conflict with the cutset assignment
  4. Solve the resulting tree structured CSP


  • The runtime is

Runtime Analysis[]

Assume that the cutset has nodes. There are ways to assign those nodes and result in variants. Then, since we are left with just tree structured CSPs, we know that th runtime for those is , but since there are only nodes in each variant, we get