人工智能实验盲目搜索
目录
人工智能实验盲目搜索 1
一、 无信息搜索（盲目搜索） 1

1. 算法原理 1
2. 流程图和伪代码 3
3. 代码展示 6
4. 实验结果及分析 12
   二、 启发式搜索 13
5. 算法原理 13
6. 流程图和伪代码 14
7. 代码展示 16
8. 实验结果及分析 19
9. 算法原理
   1.1 搜索问题的形式化定义
   解决搜索问题时，首先需要对搜索问题进行形式化表述。搜索问题从以下几个方面表述：
   状态空间：对问题的形式化，表示需要进行搜索的空间
   动作：对真正动作的形式化，表示从一个状态到达另一个状态
   初始状态：表示当前的状态
   目标：表示需要达到的目标的状态
   启发方法：用于指挥搜索的前进方向的方法
   问题的解：一个从初始状态到达目标状态的动作序列
   搜索问题可以用状态空间树表示，每个节点对应着状态空间中的一种状态。节点的父节点表示产生该状态的上一个状态，父节点生成子节点时需要记录生成节点所采取的行动与代价。
   搜索算法的性能需要考虑一个方面：
   完备性：当问题有解时是否一定能找到解
   最优性：搜索策略是否一定能找到最优解
   时间复杂度：找到解所需要的时间，又称为搜索代价
   空间复杂度：执行搜索过程中需要多少内存空间
   1.2 无信息搜索的具体算法
   1.2.1 宽度优先搜索
   宽度优先搜索用一个先进先出的队列实现，节点的拓展顺序与目标节点的位置无关。从状态空间树上看，宽度优先搜索的拓展顺序是按树的层次顺序来进行的。这样一来，短的路径会在任何比它长的路径之前被遍历，因此宽度优先搜索具有完备性和最优性。
   定义$b$为问题中一个状态最大的后继状态个数，$d$为最短解的动作个数，则有：
   时间复杂度：$1+b+b^2+...+b^d+b(b^d-1)=O(b^{d+1})$
   空间复杂度：$b(b^d-1)=O(b^{d+1})$
   1.2.2 深度优先搜索
   把当前要扩展的状态的后继状态放在边界的最前面，边界上总是扩展最深的那个节点。在状态空间无限或在状态空间有限，但是存在无限的路径（例如存在回路） 的情况下不具有完备性。在状态空间有限，且对重复路径进行剪枝的情况下才有。不具有最优性。
   定义m是遍历过程中最长路径的长度，则有：
   
   时间复杂度：$O(b^m)$
   
   
   空间复杂度：$O(bm)$
   
   1.2.3 一致代价搜索
   边界中，按路径的成本升序排列，总是扩展成本最低的那条路径。当每种动作的成本是一样的时候，和宽度优先是一样的。假设每个动作的成本都大于某个大于0的常量，所有成本较低的路径都会在成本高的路径之前被扩展。给定成本，该成本的路径数量是有限的；成本小于最优路径的路径数量是有限的，最终，我们可以找到最短的路径，因此具备完备性和最优性。
   对于一致代价搜索，当最优解的成本为C* ，上述最低代价为 $s$，则有：
   时间复杂度：$O(b^{[C^{\ast }/s]+1})$
   空间复杂度：$O(b^{[C^{\ast }/s]+1})$
   1.2.4 深度受限搜索
   深度受限搜索是深度优先搜索，但是预先限制了搜索的深度L，因此无限长度的路径不会导致深度优先搜索无法停止的问题。 但只有当解路径的长度 ≤ L 时，才能找到解，故不具有完备性和最优性。
   时间复杂度：$O(b^L)$
   空间复杂度：$O(bL)$
   1.2.5 迭代加深搜索
   一开始设置深度限制为L = 0，迭代地增加深度限制，对于每个深度限制都进行深度受限搜索 。如果找到解，或者深度受限搜索没有节点可以扩展的时候可以停止当前迭代，并提高深度限制L 。如果没有节点可以被剪掉（深度限制不能再提高）仍然 没有找到解，那么说明已经搜索所有路径，因此这个搜索不存在解。具有完备性，且在每个动作的成本一致时具有最优性。
   时间复杂度：$(d+1)b^0+db+(d-1)b^2+...+b^d=O(b^d)$
   空间复杂度：$O(bd)$
   1.2.6 双向搜索
   同时进行从初始状态向前的搜索和从目标节点向后搜索，在两个搜索在中间相遇时停止搜索。假设两个搜索都使用宽度优先搜索，则具有完备性，在每条边/每个动作的成本一致的情况下具有最优性。
   时间复杂度：$O(b^{d/2})$
   空间复杂度：$O(b^{d/2})$

# 判断当前节点是否可以拓展并加入开放列表
def validNode(open_list, open_parent_node, g, x, y, x_expand, y_expand, min_idx):
    if maze[x_expand][y_expand] == '0' or maze[x_expand][y_expand] == 'E':
        if [x_expand, y_expand] in open_list:
            idx = open_list.index([x_expand, y_expand])
            if g[idx] < g[min_idx] + 1:
                g[idx] = g[min_idx] + 1
                open_parent_node[idx] = [x,y]
        else:
            open_list.append([x_expand,y_expand])
            open_parent_node.append([x,y])
            g.append(g[min_idx]+1)


# 拓展开放列表中的节点，启发函数为Lp距离
def expandNode(open_list, close_list, open_parent_node, close_parent_node, g):
    min_cost = 100000   # 当前最小开销
    min_idx = 0         # 开销最小的节点的下标
    p = 1               # Lp距离的p

    # 找到可扩展的开销最小的节点
    for i in range(len(open_list)):
        h = (abs(open_list[i][0] - end_node[0])**p + abs(open_list[i][1] - end_node[1])**p ) ** (1/p)
        # h = max(abs(open_list[i][0] - end_node[0]), abs(open_list[i][1] - end_node[1]))
        # h = 0
        h *= 4
        f = h + g[i]
        if f < min_cost:
            min_cost = f
            min_idx = i

    # 将该节点的可扩展节点加入开放列表
    x = open_list[min_idx][0]
    y = open_list[min_idx][1]
    maze[x][y] = '1'
    validNode(open_list, open_parent_node, g, x, y, x+1, y, min_idx)
    validNode(open_list, open_parent_node, g, x, y, x-1, y, min_idx)
    validNode(open_list, open_parent_node, g, x, y, x, y+1, min_idx)
    validNode(open_list, open_parent_node, g, x, y, x, y-1, min_idx)
    print(len(open_list))
    # 将该节点从开放列表中删除并加入关闭列表
    close_list.append([x,y])
    close_parent_node.append(open_parent_node[min_idx])
    expanded.add((x,y))
    del open_list[min_idx]
    del open_parent_node[min_idx]
    del g[min_idx]

# 读入迷宫数据
maze = []
with open('MazeData.txt', 'r') as f:
    for eachLine in f:
        line = []
        for eachPos in eachLine:
            if eachPos == '\n':
                break
            line.append(eachPos)
        maze.append(line)

# 找到起点和终点坐标，并加入开启列表
row = len(maze)
col = len(maze[0])
open_list = []              # 开启列表
open_parent_node = [None]   # 开启列表中每个节点对应的父节点
g = [0]                     # 开启列表中每个节点对应的 g(x) 值
close_list = []             # 关闭列表
close_parent_node = []      # 关闭列表中每个节点对应的父节点
end_node = []
expanded = set()
for i in range(row):
    for j in range(col):
        if maze[i][j] == 'S':
            open_list.append([i,j])
        if maze[i][j] == 'E':
            end_node = [i,j]

# 开始搜索
find_ans = False
while 1:
    # 若开启列表为空，则迷宫无解
    if open_list == []:
        find_ans = False
        break
    # 对节点进行拓展
    expandNode(open_list, close_list, open_parent_node, close_parent_node, g)
    # 若开放节点中存在终点节点则找到解
    if end_node in open_list:
        find_ans = True
        break

if find_ans == False:
    print('no answer for this maze')
else:
    idx = open_list.index(end_node)
    last_node = open_parent_node[idx]
    path = [end_node]
    while last_node is not None:
        path.append(last_node)
        last_node = close_parent_node[close_list.index(last_node)]
    path = path[::-1]
    print(len(expanded) + 1)
    print(len(path))
    print(path)
    # maze = []
    # with open('MazeData.txt', 'r') as f:
    #     for eachLine in f:
    #         maze.append(eachLine)
    # for i in range(row):
    #     for j in range(col):
    #         if [i,j] in path:
    #         if (i,j) in expanded:
    #             maze[i] = maze[i][:j] + 'X' + maze[i][j+1:]
    # with open('ans.txt', 'w') as f:
    #     for eachLine in maze:
    #         f.write(eachLine)