Homework1

2018013402 方麟 im.fl@icloud.com 2021.04.07

第一题

1. 正确。UCS是在BFS上的扩展，当UCS中所有路径代价都为1时，UCS退化为BFS。
2. 正确。如果在起始点和目标点间有路径解存在，则该解的搜索深度一定是有限的，则BFS一定可以在有限时间内搜索完该深度之内的所有点，找到目标解。
3. 正确。一个有解的问题树（图）可能含有无穷分枝，DFS可能误入无穷分枝。如果误入无穷分枝（即深度无限），则不可能找到目标节点。
4. 正确。当算法的启发式函数=0时，算法退化为UCS。

第二题

1. 变量是k匹马的坐标

   变量的取值：

2. 变量受到的约束为：

3. 使用爬山法：从一个较小的k值开始，将k个马随机放在棋盘的k个位置作为初始状态。然后检测该状态是否有冲突，如果有冲突，则按照每匹马的冲突信息来调整马的位置，经过多次调整（climbing过程）后，如果没有冲突，则随即添加一匹马。重复以上过程，如果在当前状态下无法找到调整后没有冲突的状态，则返回当前k-1，为最大能放置的马的数量。value函数越大表示冲突越少。

   function K-HOURSE-HILL-CLIMBING(problem) returns a state that is a local maximum
    current_state = problem.initial()
    while true do
        result_state = current_state
        current_state.addHourseRandomly()
        while true do
            if current_state.isSatisfied()
                break
            modified_state = current_state.climbing()
            if value(modified_state) ≤ value(current_state)
                   break
            current_state = modified_state
        if current_state.isUnsatisfied()
            return result_state
   

第三题

约束弧有条，一共有个变量，每个变量的取值域中最多有个值。

按照题目提示，对每条弧，存储为中与取时相容的所有取值。

算法过程：

首先考察所有约束弧，对于条约束弧，每条约束弧考虑两个变量的所有取值，最大时间复杂度为，在考量的过程中更新所有的，如果所有大小都不为0，则说明问题存在解。如果出现大小为0，则将从的值域剔除，将入队。所有操作结束后，如果存在变量值域为空，则说明该弧相容模型无解。如果所有变量值域都不为空，则考虑所有的入队变量取值。最多有个变量取值入队，对，考虑，最多有个集合待考虑，如果集合内存在，则将从该集合中删除。若此时该集合为空，则将入队，并将从的值域剔除。重复进行此操作，直到队列中没有元素。若此时存在变量值域为空，则说明该弧相容模型无解。反之则说明该弧相容模型有解。这个过程的时间复杂度为，因为小于，所以上述过程的时间复杂度为。

第四题

作业一

搜索算法用时比较表

展开节点数比较表

路径代价比较表

分析：

四种迷宫规模都较小，搜索算法用时都较短。

BFS和算法因为其宽度优先的原理，在该四种规模的迷宫下可以找到路径代价低的解。算法是BFS和迪杰斯特拉算法的发展，由于有启发式函数，展开节点数比BFS少一些。

DFS因为其深度优先的原理，可能可以迅速找到一个可行解。虽然展开节点数较少，但是找的的解的路径代价都较高，找到的解往往不是最优解。

作业二

说明你的启发函数是良定义的：非负，一致性，并且在目标状态下的值为0：

代码如下：展开了8537个节点，效果很不错。

def foodHeuristic(state, problem): 
    position, foodGrid = state
    "*** YOUR CODE HERE ***"

    def x(elem):
        return elem[0]

    def manhattan(elem):
        return abs(elem[0] - position[0]) + abs(elem[1] - position[1])

    food_list = foodGrid.asList()[:]
    if len(food_list) == 0:
        return 0
    food_list.sort(key=x)
    food_list_left = []
    food_list_right = []
    food_list_equal = []
    for food in food_list:
        if food[0] > position[0]:
            food_list_right.append(food)
        elif food[0] < position[0]:
            food_list_left.append(food)
        else:
            food_list_equal.append(food)
    food_list_right.sort(key=manhattan, reverse=True)
    food_list_left.sort(key=manhattan, reverse=True)
    food_list_equal.sort(key=manhattan, reverse=True)
    right = medium = left = 0
    max_x = min_x = position[0]
    if len(food_list_right) > 0:
        right = manhattan(food_list_right[0])
        max_x = food_list_right[0][0]
    if len(food_list_left) > 0:
        left = manhattan(food_list_left[0])
        min_x = food_list_left[0][0]
    if len(food_list_equal) > 0:
        medium = manhattan(food_list_equal[0])
    if (left >= medium and left >= right) or (right >= medium and right >= left):
        count = 0
        hx = left + right
        for food in food_list:
            if food[0] < min_x:
                hx = hx + 1
            else:
                break
        food_list.reverse()
        for food in food_list:
            if food[0] > max_x:
                hx = hx + 1
            else:
                break
        return hx
    elif medium >= right and medium >= left:
        return medium + len(food_list) - len(food_list_equal)

非负：如果未达到目标状态，hx初始化为正整数，对hx做的所有操作是增加一个正整数，所以最后得到的hx一定是非负的，该启发式函数返回值是非负的。

一致性：对于任意状态，运行foodHeuristic函数。每次action所需要的代价为1，下面说明：

1. 如果离position曼哈顿距离最大的食物与position横坐标不同，将食物分为两部分，返回的横坐标小于position的所有食物的极大曼哈顿距离+横坐标大于position的所有食物的极大曼哈顿距离+所有横坐标在这两个有极大曼哈顿距离的食物的横坐标范围之外的食物数目（横坐标比左侧极值还要小，或比右侧极值还要大）。这样构造的满足，因为在左侧极值和右侧极值范围内的所有食物至少需要两个最大曼哈顿距离之和次action才能够吃完，在这两个有极大曼哈顿距离的食物的横坐标范围之外的食物至少需要其数目次action才能够吃完。所以将三者相加得到的值一定小于或等于吃豆人在该position吃完所有食物所需要的最少action次数。
2. 如果离position曼哈顿距离最大的食物与position横坐标相同，则返回的该最大曼哈顿距离+和position横坐标不同的所有食物数目。这样构造的满足，因为和position横坐标相同的所有食物至少需要该最大曼哈顿距离次action才能吃完，和position横坐标不同的所有食物至少需要其数目次action才能够吃完。所以将二者相加得到的值一定小于或等于吃豆人该position吃完所有食物所需要的最少action次数。

在目标状态下值为0：当到达目标状态，foodGrid.asList()为空列表，返回值为0。

作业三

见其他文件。