人工智能作业-启发式搜索

Task1

1.迭代加深算法（盲目搜索和启发式搜索$A\ast$算法）完成九宫图的求解

盲目搜索算法选择了生成再测试算法，广度优先算法，迭代有界深度优先算法，为了优化，同样引入了OPEN表和CLOSE表。

这里选择的初始状态和目标状态如下，可以通过命令行输入对状态设定

init = np.array([2, 8, 3, 1, 6, 4, 7, 0, 5]).reshape(3, 3)
goal = np.array([1, 2, 3, 8, 0, 4, 7, 6, 5]).reshape(3, 3)

盲目搜索

迭代有界深度

for delimit in range(3, 100, 3):
    if queue.empty():
        queue.put(((-1)*start_node.depth, start_node))
        visited.clear()
        # 这里结合启发式搜索配置了close表，如果删除可能会出现死循环
        # 或者使用random包对direction集合随机选择方向
    while not queue.empty():
        node = queue.get()[1]  # (node.cost, node)
        if np.array_equal(node.state, self.goal):
            path = []
            while node.parent:
                path.append(node.state)
                node = node.parent
            path.append(node.state)
            return path[::-1]
        for direction in self.detect_actionset(node.state):
            new_state = self.move(node.state, direction)
            if str(new_state) in visited:
                continue
            # 5
            # 迭代有界加深，cost 为目前深度*(-1)
            if node.depth+1 < delimit:
                new_node = Node(new_state, node, node.depth+1,
                                (-1)*(node.depth+1))
                queue.put((node.cost, node))
                queue.put((new_node.cost, new_node))
                visited.add(str(new_state))
            break

算法结果|结果为5步，如果初始状态不算为一步

生成再测试

如果没有引入OPEN和CLOSE表或者对移动位置进行随机，那么会出现死循环的状况。下面是采用了记录表的盲目搜索

while not queue.empty():
    node = queue.get()[1]  # (node.cost, node)
    if np.array_equal(node.state, self.goal):
        path = []
        while node.parent:
            path.append(node.state)
            node = node.parent
        path.append(node.state)
        return path[::-1]
    for direction in self.detect_actionset(node.state):
        new_state = self.move(node.state, direction)
        # 如果new_node在close表里：
        if str(new_state) in visited:
            continue
        # 将cost改为0即可
        new_node = Node(new_state, node, node.depth+1,
                        0)
        queue.put((new_node.cost, new_node))
        visited.add(str(new_state))
return None

盲目搜索结果

广度优先

while not queue.empty():
    node = queue.get()[1]  # (node.cost, node)
    if np.array_equal(node.state, self.goal):
        path = []
        while node.parent:
            path.append(node.state)
            node = node.parent
        path.append(node.state)
        return path[::-1]
    for direction in self.detect_actionset(node.state):
        new_state = self.move(node.state, direction)
        # 如果new_node在close表里：
        if str(new_state) in visited:
            continue
        # 广度优先，cost 为目前深度
        new_node = Node(new_state, node, node.depth+1,
                        node.depth+1)
        queue.put((new_node.cost, new_node))
        visited.add(str(new_state))
return None

最后结果为同迭代有界深度算法得到的最优结果（因为该问题的搜索空间较小，同时解的深度较低）

启发式搜索

这里选择了GBFS算法和$IDA\ast$算法，其中GBFS算法使用了OPEN表和CLOSE表，但是扩展节点的时候没有考虑比较新节点是否在这两个表里面，所以得到是可行解而不是最优解。也有使用了比较的GBFS算法，该问题中两个得到解一致。

GBFS算法

 while not queue.empty():
    node = queue.get()[1]  # (node.cost, node)
    if np.array_equal(node.state, self.goal):
        path = []
        while node.parent:
            path.append(node.state)
            node = node.parent
        path.append(node.state)
        return path[::-1]
    for direction in self.detect_actionset(node.state):
        new_state = self.move(node.state, direction)
        # 如果new_node在close表里：
        for obj in visited:
            if (obj.state == new_state).any():
                if node.cost - (node.depth+1+self.count_distance(new_state)) < obj.parent.cost - (node.depth+1+self.count_distance(new_state)):
                    visited.remove(obj)
                    obj.parent = node
                    queue.put(obj)
                continue
        # 1
        # 启发式搜索A*，cost为目前深度+目前状态到目标状态的距离
        new_node = Node(new_state, node, node.depth+1,
                        node.depth+1+self.count_distance(new_state))
        if not queue.empty():
            if if_in_priority_queue(queue, new_node):
                continue
        queue.put((new_node.cost, new_node))
        visited.append(new_node)

最后结果也是5步完成,将对close表和open表的比较删除即可得到一般的GBFS算法

IDA*算法

if case == 3:
    start_node = Node(self.start, None, 0, 0)
    # 生成一个优先队列，代价（cost）越小的出列优先级越高
    queue = PriorityQueue()
    queue.put((self.Manhattan(self.start), start_node))
    visited = set()
    # IDA*
    delimit1 = 4
    delimit2 = 100
    while not queue.empty():
        node = queue.get()[1]  # (node.cost, node)
        if np.array_equal(node.state, self.goal):
            path = []
            while node.parent:
                path.append(node.state)
                node = node.parent
            path.append(node.state)
            return path[::-1]
        for direction in self.detect_actionset(node.state):
            new_state = self.move(node.state, direction)
            # 如果new_node在close表里：
            if str(new_state) in visited:
                continue
            # 5
            # IDA*，cost为目前深度+目前状态到目标状态的距离
            if node.depth+1+self.count_distance(new_state) <= delimit1:
                new_node = Node(new_state, node, node.depth+1,
                                node.depth+1+self.count_distance(new_state))
                queue.put((new_node.cost, new_node))
                # visited.add(str(new_state))
            else:
                delimit2 = min(delimit2, node.depth+1+self.count_distance(new_state))
        if queue.empty():
            if 1 < delimit1 <= 200:
                delimit1 = delimit2
                queue.put((self.Manhattan(self.start), start_node))
            elif delimit1 > 200:
                return None

最后结果也是5步完成。

其他启发式函数

除了曼哈顿距离外，这里的Puzzle类还有二范数，处于目标状态的数字个数作为距离等距离函数。在该问题中，所选用的三种距离结合GBFSA得到的结果相同，均为5步.