cs50ai3-------Optimization

cs50ai3-------Optimization

基础知识

这节课主要讲了一些优化问题对应的算法求解，其实具体使用时还是需要具体分析，看哪些问题能够转化为我们学习的算法能够求解的形式
local search与hill climbing与linear programming这三种算法都比较直观简单，这里就不多讲
值得一提的是，课上讲了爬山算法的几种变体，具体如下图所示：

但是也不是变体就能一定解决陷入局部最优解的问题，也没有某种最好的方法，只有最适合的方法

接着是退火算法的介绍，顾名思义，这种算法避免陷入局部最优解的方法，是引入一个温度的概念，在刚开始的一段时间里温度较高，算法越有可能去做出随机的决策，随着时间流逝（算法迭代次数的增加），温度降低，做出随机决策的概率也降低
具体流程如下所示：

从起始状态开始，我们随机的选择一个neighbor state，计算我们选择的state比现在的state好了多少，用ΔE来表示，如果ΔE大于0，我们就选择neighbor，如果小于0，我们也有 eΔE/T的概率去选择较差的neighbor，观察这个概率式子我们可以发现，ΔE<0时，温度越高，越有可能做出这样的选择，而ΔE越小，做出这样选择的概率越低

然后是关于约束满足问题的讨论，比如说对于下面这个问题：

每个学生有A-G之间的几门课程，要求每个学生的课程之间不能在同一天考试，我们可以画出下面这样的图来表示它们之间的约束关系：

此类约束满足问题大致有以下特征：
Set of variables (x₁, x₂, …, xₙ) 一组变量
Set of domains for each variable {D₁, D₂, …, Dₙ} 每个变量有对应的值域
Set of constraints C 一组约束

接着介绍了不同种类的约束：
A Hard Constraint is a constraint that must be satisfied in a correct solution.
A Soft Constraint is a constraint that expresses which solution is preferred over others.
A Unary Constraint is a constraint that involves only one variable. In our example, a unary constraint would be saying that course A can’t have an exam on Monday {A ≠ Monday}.
A Binary Constraint is a constraint that involves two variables. This is the type of constraint that we used in the example above, saying that some two courses can’t have the same value {A ≠ B}.

接着重点讨论了如何使问题满足arc consistency的算法

对于两个变量之间的binary constraint与所有变量之间的binary constraint 我们可以分别采用以下算法来完成：

但是我们可以注意到ac-3算法是无法解决我们之前为学生安排考试的问题的，是因为它没有考虑到变量之间是如何连接的，我们可以使用之前search的思想来将这个csp问题转换为search问题：

我们可以采用回溯搜索来解决csp问题：

具体来说，对于之前的那个问题：

我们从A的第一个value出发，设置A=mon，再加入B，B=mon不符合约束，所以B=tue，以此类推，直到整个assignment不再更新

我们可以对回溯搜索进一步的优化
首先，我们可以在每次加入var=value之后，都运行ac-3算法来维护整体的arc-consistency，这样就可以利用我们的knowledge来进行inference，删除某些节点的value，简化搜索过程：

其次，在每次选择节点var时，我们可以优先选择domain中value最少的节点，在最开始value数目相同的时候，我们可以优先选择和其它节点连接最紧密的节点，即degree最大的节点，显然这样做可以最大的减少搜索深度与我们要搜索的空间：

最后，在遍历每个节点domain的value时，我们可以优先选择受到最小约束的value，这样做我们找到问题的一个solution的概率可以最大化：

比如对于上面这个问题，在选择c节点的value时，tue受到b，e，f三个节点的限制，wed受到b，e两个节点的限制，所以我们优先选择wed

课后题目

understanding:
该项目中有两个Python文件：crossword.py和generate.py。第一个完全是为您编写的，第二个有一些功能留给您来实现。
首先，我们来看看 crossword.py。该文件定义了两个类：Variable（代表填字游戏中的变量）和 Crossword（代表填字游戏本身）。
请注意，要创建变量，我们必须指定四个值：其行 i、列 j、其方向（常量 Variable.ACROSS 或常量 Variable.DOWN）及其长度。
Crossword 类需要两个值来创建新的纵横字谜游戏：一个定义谜题结构的 Structure_file（_ 用于表示空白单元格，任何其他字符表示不会被填充的单元格）和一个定义了 Words_file 用于拼图词汇的单词列表（每行一个）。每个文件的三个示例都可以在项目的数据目录中找到，也欢迎您创建自己的文件。
特别注意，对于任何填字游戏对象填字游戏，我们存储以下值：
crossword.height 是一个整数，表示填字游戏的高度。
crossword.width 是一个整数，表示填字游戏的宽度。
crossword.struct 是一个表示谜题结构的 2D 列表。对于任何有效的第 i 行和第 j 列，如果单元格为空白（必须在其中填充字符），crossword.struct[i][j] 将为 True，否则为 False（该单元格中不填充任何字符）。
crossword.words 是构建填字游戏时要从中提取的所有单词的集合。
crossword.variables 是拼图中所有变量的集合（每个变量都是一个 Variable 对象）。
crossword.overlaps 是一个字典，将一对变量映射到它们的重叠部分。对于任何两个不同的变量 v1 和 v2，如果两个变量没有重叠，则 crossword.overlaps[v1, v2] 将为 None；如果变量重叠，则为一对整数 (i, j)。 (i, j) 对应解释为 v1 值的第 i 个字符必须与 v2 值的第 j 个字符相同。
Crossword 对象还支持 Neighbors 方法，该方法返回与给定变量重叠的所有变量。也就是说，crossword.neighbors(v1) 将返回与变量 v1 相邻的所有变量的集合。
接下来，看一下generate.py。在这里，我们定义了一个 CrosswordCreator 类，我们将用它来解决填字游戏。创建 CrosswordCreator 对象时，它会获得一个应该是 Crossword 对象的填字游戏属性（因此具有上述所有属性）。每个 CrosswordCreator 对象还获得一个domains属性：一个字典，它将变量映射到变量可能采用的一组可能的单词作为值。最初，这组单词是我们词汇表中的所有单词，但我们很快就会编写函数来限制这些域。
我们还为您定义了一些函数来帮助您测试代码： print 将在终端上打印给定作业的填字游戏的表示形式（在该函数和其他地方，每个作业都是一个将变量映射到其对应的字典）字）。同时，保存将生成与给定作业相对应的图像文件（如果您还没有使用此功能，则需要 pip3 安装 Pillow）。 letter_grid 是 print 和 save 都使用的辅助函数，它会生成一个二维列表，其中包含给定作业的适当位置的所有字符
最后，注意solve函数。该函数做了三件事：首先，它调用enforce_node_consistency来强制填字游戏中的节点一致性，确保变量域中的每个值都满足一元约束。接下来，该函数调用 ac3 来强制弧一致性，确保满足二进制约束。最后，该函数对最初为空的赋值（空字典 dict()）调用回溯，以尝试计算问题的解决方案。
不过，force_node_consistency、ac3 和 backtrack 函数（以及其他函数）尚未实现。这就是留给你完成的地方

specification：
在generate.py中完成enforce_node_consistency、revise、ac3、assignment_complete、consistent、order_domain_values、selected_unassigned_variable和backtrack的实现，以便您的AI在可能的情况下生成完整的填字游戏。

force_node_consistency 函数应该更新 self.domains 以使每个变量都是节点一致的。
回想一下，当对于每个变量，其域中的每个值都与变量的一元约束一致时，就实现了节点一致性。在填字游戏中，这意味着确保变量域中的每个值的字母数量与变量的长度相同。
要从变量 v 的域中删除值 x，由于 self.domains 是将变量映射到值集的字典，因此可以调用 self.domains[v].remove(x)。
该函数不需要返回值。

revise函数应该使变量x与变量y一致。
x 和 y 都将是代表拼图中变量的 Variable 对象。
回想一下，当 x 域中的每个值在 y 域中都有一个不会引起冲突的可能值时，x 与 y 是弧一致的。（填字游戏中的冲突是指两个变量在其重叠的地方的value不一致。）
为了使 x 弧与 y 一致，您需要从 x 域中删除在 y 域中没有对应可能值的任何值。
回想一下，您可以访问 self.crossword.overlaps 来获取两个变量之间的重叠（如果有）。
y 的定义域应保持不变。
如果对 x 的域进行了修改，则该函数应返回 True；如果没有进行修改，它应该返回 False。

ac3 函数应该使用 AC3 算法来强制解决问题的弧一致性。回想一下，当每个变量域中的所有值都满足该变量的二进制约束时，就实现了弧一致性。
回想一下，AC3 算法维护一个要处理的弧队列。该函数采用一个名为 arcs 的可选参数，表示要处理的初始弧列表。如果 arcs 为 None，则您的函数应从问题中所有弧的初始队列开始。否则，您的算法应从仅包含弧列表中的弧的初始队列开始（其中每个弧都是变量 x 和不同变量 y 的元组 (x, y)）。
回想一下，要实现 AC3，您将一次修改队列中的每个弧。不过，每当您对域进行更改时，您可能需要向队列中添加额外的弧，以确保其他弧保持一致。
您可能会发现在 ac3 的实现中调用 revise 函数很有帮助。
如果在强制弧一致性的过程中，您从域中删除了所有剩余值，则返回 False（这意味着无法解决问题，因为变量不再有可能的值）。否则，返回 True。
您无需担心在此函数中强制执行单词唯一性（您将在一致函数中实现该检查。）

assignment_complete 函数应该（顾名思义）检查给定的分配是否完成。
assignment是一个字典，其中键是 Variable 对象，值是表示这些变量将采用的单词的字符串。
如果每个填字游戏变量都分配了一个值（无论该值是什么），则分配完成。
如果赋值完成，该函数应返回 True，否则返回 False。

consistent函数应该检查给定的分配是否一致。
如果满足问题的所有约束，则赋值是一致的：也就是说，所有值都是不同的，每个值都是正确的长度，并且相邻变量之间不存在冲突。
如果赋值一致，该函数应返回 True，否则返回 False。

order_domain_values 函数应返回 var 域中所有值的列表，并根据最小约束值启发式排序。
var 将是一个 Variable 对象，代表拼图中的变量。
回想一下，最小约束值启发法是根据相邻未分配变量排除的值的数量来计算的。
请注意，assignment中存在的任何变量如果已经有一个值，在计算排除相邻未赋值变量的值的数量时不应将其计算在内。
对于消除了的域值相邻变量的可能选择数量相同，任何顺序都是可以接受的。
回想一下，您可以访问 self.crossword.overlaps 来获取两个变量之间的重叠（如果有）。
首先通过以任意顺序返回值列表来实现此函数可能会有所帮助（这仍然应该生成正确的填字游戏）。一旦您的算法开始工作，您就可以返回并确保以正确的顺序返回值。
您可能会发现根据特定键对列表进行排序很有帮助：Python 包含一些有助于实现此目的的有用函数。

select_unassigned_variable 函数应根据最小剩余值启发式和度启发式返回填字游戏中尚未通过赋值进行分配的单个变量。
赋值是一个字典，其中键是 Variable 对象，值是表示这些变量将采用的单词的字符串。您可能会认为分配不会完成：并非所有变量都会出现在分配中。
您的函数应该返回一个 Variable 对象。您应该返回其域中剩余值数量最少的变量。如果变量之间存在联系，则应选择这些变量中度数最大（具有最多邻居）的变量。如果两种情况都存在平局，您可以在平局变量中任意选择。
首先通过返回任意未分配的变量（仍应生成正确的填字游戏）来实现此函数可能会有所帮助。一旦您的算法开始工作，您就可以返回并确保根据启发式返回一个变量。
您可能会发现根据特定键对列表进行排序很有帮助：Python 包含一些有助于实现此目的的有用函数。

backtrack函数应接受部分赋值作为输入，并使用回溯搜索，返回完整的令人满意的变量值赋值（如果可能的话）。

代码实践

本次crossword作业总体上就是一个csp问题的实践，用到的算法以及优化的思想在前面的基础知识部分均有涉及

首先是unary consistency与arc consistency的维护：

    def enforce_node_consistency(self):
        """
        Update `self.domains` such that each variable is node-consistent.
        (Remove any values that are inconsistent with a variable's unary
         constraints; in this case, the length of the word.)
        """
        for x in self.crossword.words:
            for v in self.domains.keys():
                if len(x) != v.length:
                    self.domains[v].remove(x)

    def revise(self, x, y):
        """
        Make variable `x` arc consistent with variable `y`.
        To do so, remove values from `self.domains[x]` for which there is no
        possible corresponding value for `y` in `self.domains[y]`.

        Return True if a revision was made to the domain of `x`; return
        False if no revision was made.
        """
        loc = self.crossword.overlaps[x, y]
        remove_words = []
        if loc != None:
            i, j = loc
            revised = False
            for word in self.domains[x]:
                flag = True
                for candi in self.domains[y]:
                    if word[i] == candi[j]:
                        flag = False
                        break
                if flag:
                    remove_words.append(word)
                    revised = True
            for w in remove_words:
                self.domains[x].remove(w)
            return revised
        return False

    def ac3(self, arcs=None):
        """
        Update `self.domains` such that each variable is arc consistent.
        If `arcs` is None, begin with initial list of all arcs in the problem.
        Otherwise, use `arcs` as the initial list of arcs to make consistent.

        Return True if arc consistency is enforced and no domains are empty;
        return False if one or more domains end up empty.
        """
        if not arcs:
            queue = []
            for variable1 in self.domains:
                for variable2 in self.crossword.neighbors(variable1):
                    if self.crossword.overlaps[variable1, variable2] is not None:
                        queue.append((variable1, variable2))

        while len(queue) > 0:
            x, y = queue.pop(0)
            if self.revise(x, y):
                if len(self.domains[x]) == 0:
                    return False
                for neighbour in self.crossword.neighbors(x):
                    if neighbour != y:
                        queue.append((neighbour, x))
            return True

其次是检测当前纵横字谜是否已经完成，并且要检测填入的单词是否符合我们的限制，比如说单词的长度，单词与单词之间不能相同，重叠部分的单词应该相同等等

    def assignment_complete(self, assignment):
        """
        Return True if `assignment` is complete (i.e., assigns a value to each
        crossword variable); return False otherwise.
        """
        for variable in self.domains:
            if variable not in assignment:
                return False
        return True

    def consistent(self, assignment):
        """
        Return True if `assignment` is consistent (i.e., words fit in crossword
        puzzle without conflicting characters); return False otherwise.
        """
        # 检查长度是否满足谜语的长度
        for v, word in assignment.items():
            if v.length != len(word):
                return False
        # 检查每个单词是否不同
        if len(assignment) != len(set(assignment.values())):
            return False
        # 检查重叠的部分单词是否一致
        for var_pair, loc in self.crossword.overlaps.items():
            if loc != None:
                x, y = var_pair
                i, j = loc
                if x in assignment and y in assignment and assignment[x][i] != assignment[y][j]:
                    return False
        return True

然后是我们之前提到过的优化部分，第一部分就是在遍历每个变量的值域时，我们会选择受到最小约束的那部分，但是这里我搞了半天也没有看懂代码究竟是怎么实现的，于是作罢，第二部分比较简单，就是在选择变量时，选择值域较小与度较大的变量

    def order_domain_values(self, var, assignment):
        """
        Return a list of values in the domain of `var`, in order by
        the number of values they rule out for neighboring variables.
        The first value in the list, for example, should be the one
        that rules out the fewest values among the neighbors of `var`.
        """
        return list(self.domains[var])

    def select_unassigned_variable(self, assignment):
        """
        Return an unassigned variable not already part of `assignment`.
        Choose the variable with the minimum number of remaining values
        in its domain. If there is a tie, choose the variable with the highest
        degree. If there is a tie, any of the tied variables are acceptable
        return values.
        """
        # 获取所有未分配的变量
        unassigned = set(self.domains.keys()) - set(assignment.keys())
        # 如果没有未分配的变量，则返回 None
        if not unassigned:
            return None
        # 定义一个函数，用于比较变量的剩余值数量和度
        def variable_score(variable):
            # 获取变量的剩余值数量
            remaining_values = len(self.domains[variable])
            # 获取变量的度（与其他变量相邻的数量）
            degree = len(self.crossword.neighbors(variable))
            # 返回一个元组，包含剩余值数量和度，用于排序
            return (remaining_values, -degree)  # 使用负数表示度越高越好
        # 使用 variable_score 函数对未分配的变量进行排序
        sorted_variables = sorted(unassigned, key=variable_score)
        # 返回排序后的第一个变量，即剩余值数量最少且度最高的变量
        return sorted_variables[0]

最后就是之前的backtrack函数的伪代码的具体实现，利用了我们之前完成的一些函数即可：

    def backtrack(self, assignment):
        """
        Using Backtracking Search, take as input a partial assignment for the
        crossword and return a complete assignment if possible to do so.

        `assignment` is a mapping from variables (keys) to words (values).

        If no assignment is possible, return None.
        """
        if self.assignment_complete(assignment):
            return assignment
        unassigned_var = self.select_unassigned_variable(assignment)
        domain = self.order_domain_values(unassigned_var, assignment)
        for word in domain:
            new_assignment = assignment.copy()
            new_assignment[unassigned_var] = word
            if self.consistent(new_assignment):
                result = self.backtrack(new_assignment)
                if result != None:
                    return result
        return None