理解约束满足问题：地图着色算法

Question

我正在尝试针对给定算法的约束满足问题实现此递归回溯函数：

function BACKTRACKING-SEARCH(csp) returns solution/failure
    return RECURSIVE-BACKTRACKING({},csp)
function RECURSIVE-BACKTRACKING(assignment,csp) returns soln/failure
    if assignment is complete then return assignment
    var <- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
    for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do
        if value is consistent with assignment given CONSTRAINT[csp] then
            add {var = value} to assignment
            result <- RECURSIVE-BACKTRACKING(assignment, csp)
            if result != failure then return result
            remove {var = value} from assignment
    return failure

BACKTRACKING-SEARCH(csp) 中 csp 的输入是一个 csp class，其中包含 a) 状态列表，b) 颜色列表，以及 c) 状态为的有序字典键和值是不能具有相同颜色的状态的邻居列表。

问题是我很难理解算法是如何正确工作的。如果有人能给我这个算法的正确解释，我将不胜感激。我的一些具体问题是：

    if assignment is complete then return assignment

我假设由于赋值是作为一个空字典 {} 输入的，这将 return 解决方案，即包含状态及其颜色的字典。但是，我不明白如何检查作业是否完成？会不会像根据状态数检查字典的大小？

    var <- SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)

输入 csp class 包含一个状态列表，我假设这可能只是 var 等于从列表中弹出一个值？我想，让我感到困惑的是，根据我的输入，我不确定参数（VARIABLES[csp]、assignment、csp）在做什么。

    for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do

再次对（var、assignment、csp）的输入到底做了什么感到困惑。但我假设它会遍历状态字典中的每个值（邻居）？

        if value is consistent with assignment given CONSTRAINT[csp] then
            add {var = value} to assignment
            result <- RECURSIVE-BACKTRACKING(assignment, csp)
            if result != failure then return result
            remove {var = value} from assignment

如何正确检查值是否与给定约束[csp] 的赋值一致？我假设约束应该是我尚未实施的 csp class 之外的东西？我不明白这个 if 语句在检查方面做了什么。如果有人能清楚地解释这个if语句和if语句的主体，那将是非常有用的。

Answer 1

因此，在重新整理了一些大学文献（Peter Norvig 的人工智能：一种现代方法）之后，发现您手上的问题是递归 Backtracking as a way to find a solution for the Graph Coloring Problem 的应用，它也称为地图着色（考虑到它解决绘制地图所需颜色最小化问题的历史）。将地图中的每个国家替换为节点及其边界将为您提供一个图表，我们可以在其中应用递归回溯来找到解决方案。

递归回溯将作为深度优先树搜索下降图节点，在每个节点检查是否可以使用颜色。如果不是，则尝试下一种颜色，如果是，则尝试下一个未访问的相邻节点。如果对于给定节点，没有颜色满足条件，它将后退（回溯）并移动到兄弟节点（如果该节点没有兄弟节点，则移动到父节点的兄弟节点）。

所以，

I assume that since assignment is inputted as an empty dictionary {}, that this will return the solution, that is, the dictionary that contains states and their colors ... Would it be something like checking the size of the dictionary against the number of states?

是的，是的。一旦字典包含具有颜色的图形的所有节点，您就会有一个解决方案。

The input csp class contains a list of states, I assume this could just be var equal to popping off a value in the list?

该伪代码语法令人困惑，但总体思路是，您将有办法找出图形中尚未着色的节点。一种简单的方法是 return 字典中没有分配值的节点。因此，如果我正确理解语法，var 将存储一个节点。 VARIABLES[csp] 在我看来像是 CSP 结构中节点列表的表示。

I'm not sure what the parameters (VARIABLES[csp], assignment, csp) are doing, given my input

如上所述，赋值参数是一个字典，其中包含到目前为止评估的节点（以及未来的解决方案），csp 是包含 a,b 和 c 的结构。

Again, confused on what the inputs of (var, assignment, csp) are doing exactly. But I assume that it'll go through each value (neighbor) in dictionary of the state?

ORDER-DOMAIN-VALUES 似乎是一个函数，它将 return 您的 CSP 结构中的有序颜色集。 FOR 循环将遍历每种颜色，以便对其进行测试以满足该级别的问题。

 if value is consistent with assignment given CONSTRAINT[csp] then

在这里，您正在做的是使用该值测试约束，以确保它是真实的。在这种情况下，您要检查与该节点相邻的任何节点是否已经不具有该颜色。如果相邻节点具有该颜色，则跳过 IF 并迭代 for 循环以尝试下一种颜色。

如果没有相邻节点具有该颜色，则进入IF主体并将颜色为value的节点var添加到assigment字典（我相信{var = value}是一个元组表示，我会写成 {var,value}，但是哦，好吧）。然后再调用函数recursive backtracking，递归。如果递归调用returns非失败，return其结果（说明已经找到解）

如果它 return 失败了（意思是，它尝试了所有的颜色并且所有颜色都恰好被另一个相邻节点使用），然后从 assignment（解决方案）阵列并移至下一个颜色。如果所有颜色都用完了，return失败。

理解约束满足问题：地图着色算法

understanding constraint satisfaction problem: map coloring algorithm

algorithm

artificial-intelligence

recursive-backtracking