I am trying to design a good heuristic to solve a constraint satisfaction problem (CSP). I think that a possible heuristic to use is

$$h_1(\text{state}) = \text{number of conflicts in state}$$

However, of the possible solutions to the CSP, some have a lower cost (are better). So I can't just use $h_1$ as my heuristic.

Since the state space is pretty huge, I want to use the local search with a heuristic $h$, that guides my variable assignments towards a low-cost solution while reducing the conflicts. The way I am thinking about going about this is: of the variable assignments which do not cause conflicts (are valid), apply $h$ to them, pick the variable assignment which has the lowest/best value $h$ value. So $h$ would not handle conflicts, I would make sure any assignments considered by $h$ are guaranteed to be valid.

Ideally, though, I want $h$ to both drive down the conflicts to 0 and simultaneously guide the assignments to the lowest cost solution. Is this generally possible?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.