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

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    

csp在回溯搜索( csp )中的输入是一个csp类，它包含一个状态列表，( b)颜色列表，和( c)一个以状态为键的有序字典，其值是不能具有相同颜色的状态的邻居列表。

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

    if assignment is complete then return assignment

我假定，由于赋值被输入为空字典{}，这将返回解决方案，即包含状态及其颜色的字典。但是，我不明白我怎么才能检查作业是否完成？会不会像检查字典的大小和州数一样呢？

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

输入csp类包含一个状态列表，我假设这可能等于在列表中弹出一个值？我想，让我困惑的是，考虑到我的输入，我不确定参数(VARIABLEScsp、赋值、csp)在做什么。

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

再次，困惑的输入(var，赋值，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类的一部分。我不明白如果声明在检查方面做了什么。如果有人能清楚地解释这个if语句和if语句的正文，这将是非常有用的。

Answer 1

因此，在重新整理了一些大学文献(Peter的“人工智能:一种现代方法”)之后，你手中的问题是如何应用递归回溯来为图着色问题找到一个解决方案，这也被称为地图着色(考虑到它的历史，它可以解决绘制地图所需颜色最小化的问题)。将地图中的每个国家替换为一个节点及其边界，就会给出一个图，在这里我们可以应用递归回溯来找到解决方案。

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

所以,

我假设由于赋值输入为空字典{}，这将返回解决方案，即包含状态及其颜色的字典.会不会像检查字典的大小和州数一样呢？

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

输入csp类包含一个状态列表，我假设这可能等于在列表中弹出一个值？

这种伪代码语法是令人困惑的，但是一般的想法是，您将有一种方法来找出图中尚未着色的节点。一种简单的方法是从没有分配值的字典中返回一个节点。因此，如果我正确理解语法，var将存储一个节点。在我看来，VARIABLES[csp]似乎是CSP结构中节点列表的表示。

考虑到我的输入，我不确定参数(VARIABLEScsp、赋值、csp)在做什么

正如上面所提到的，赋值参数是一个字典，它包含到目前为止评估的节点(以及未来的解决方案)，而csp是包含a、b和c的结构。

再次，困惑的输入(var，赋值，csp)到底在做什么。但是我假设它会通过状态字典中的每个值(邻居)？

顺序域值似乎是一个函数，它将返回CSP结构中有序的颜色集。FOR循环将遍历每种颜色，以便测试它们以满足该级别的问题。

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

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

如果没有相邻节点具有该颜色，则输入If主体并将带有颜色var的节点value添加到assigment字典中(我相信{var = value}是一个元组表示，我会编写{var，value}，但是很好)。然后递归地再次调用函数递归回溯。如果递归调用返回非失败，则返回其结果(这意味着已找到解决方案)。

如果它返回一个失败(意思是，它尝试了所有的颜色，它们都碰巧被另一个相邻的节点使用)，那么从assignment (解决方案)数组中移除该节点({var，value})并移到下一个颜色。如果所有颜色都已用完，则返回失败。