最小冲突的局部搜索法是用局部搜索方法解决CSP(约束满足问题)的一种方法。
CSP(约束满足问题):由一个变量集合和一个约束集合组成。问题的一个状态是由对一些或全部变量的一个赋值定义的完全赋值,每个变量都参与的赋值。问题的解是满足所有约束的完全赋值,或更进一步,使目标函数最大化。
我们可以这样理解这种算法:它是挑选整体状态的一个局部,在该部分内判断各个调整状态,在该局部范围内寻找最优解,然后进入下一个局部,直至找到使整体情况满足条件的解,这个解就是最终解。事实证明,局部最小冲突法对CSP问题往往有令人吃惊的效果。它们使用完全状态的形式化:初始状态给每个变量都赋一个值,后继函数通常一次改变一个变量的取值。
1