1
$\begingroup$

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?

$\endgroup$

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.