lab2实验报告¶

课程名称:当代人工智能	年级:22级	上机实践成绩:
指导教师:李翔	姓名:郭夏辉	学号:10211900416
上机实践名称:A*算法	上机实践日期:2023年10月20日	上机实践编号:No.2
组号:1-416	上机实践时间:2023年10月20日

一、实验目的¶

使用A*算法实现两道算法题，每道题有5个测试输入，你需要用你的算法去预测对应输出。

二、理论学习¶

什么是A star算法？它有什么优势呢？它在使用过程中有什么值得注意的地方呢？

在上课时，老师讲过了UCS和Greedy search两种搜索算法——前者基于BFS改进，每次展开的结点是当前已花费代价最小的节点，这属于过去的回顾；后者基于一个启发式函数，每次都在展望未来，展开估计代价最小的结点。虽然这两种算法确实相对于传统的DFS和BFS有所改进，但是依然存在不小的缺陷，UCS可能在遍历完整张图之后才能取到最优解，时间代价过大；Greedy search可能会因为启发式函数设计的不合理性，只得到了局部而不是全局的最优解。

A star算法综合了两种算法的优势，在回顾过去的同时展望未来，展开当前已花费代价（从起点到当前结点n的代价\(g(n)\) ）和启发式估计代价(从当前结点n到终点的估计代价为\(h(n)\) )总和(取\(f(n)=g(n)+h(n)\) )最小的节点。A star算法考虑启发的信息，有选择性地拓展结点，极大地减少了时间上的开销。

我们每次都希望得到一个\(f(n)\)值最小的结点以方便展开，这很自然地就想到了优先队列这种数据结构。在此基础之上，我们每次只用将队首的元素弹出，并将未曾加入过队列的结点加入队列。循环往复，直到目标结点从队列中弹出算法终止（我们如果第一次遇到目标结点，是不能退出的，还要将其加入队列中，然后目标节点从队列中再弹出时才终止，否则其最优性不能被保证）。

但是A star算法能够运用有两个重要的前置条件：可容性（admissible）和一致性（consistency）。

可容性：启发函数不会过高估计从当前结点n到目标结点的代价（即\(h(n) \leq h^{*}(n)\)，其中\(h^{*}(n)\)表示从结点n到目标结点的真实代价，这个真实代价我们目前还是不知道，靠的是估计得到一个\(h(n)\)）
一致性：假设结点n后继有一结点m,从n到目标结点的代价一定不超过“从m到目标结点的代价与 n到m的代价”之和（即\(h(n) \leq h(m)+cost(n,m)\),\(cost(n,m)\)表示从n到m的代价）

三、实验过程¶

题目一冰雪魔方的冰霜之道¶

在遥远的冰雪王国中，存在⼀个由9个神秘冰块组成的魔法魔方。在这个魔方中，有8块冰雪魔块，每块都雕刻有1-8中的一个数字（每个数字都是独特的）。魔方上还有一个没有雕刻数字的空冰块（即"0"）你可以滑动与空冰块相邻的冰块来改变魔块的位置。传说，当冰雪魔块按照⼀个特定的顺序排列（设定为1 3 5 7 0 2 6 8 4）时，魔法魔方将会显露出通往⼀个隐秘冰宫的冰霜之道。现在，你站在这个神秘的魔方前，试图通过最少的滑动步骤将冰雪魔块排列成目标顺序。

分析&思路¶

对于某个局面而言，它包含什么样的信息呢？一方面就是当前那8个填了数字的格子的位置，另一方面就是从启发式函数的角度定义的\(f(n),g(n),h(n)\)函数。每次从某个状态转化至下一状态的代价都是一样的——1，过去走过的代价\(g(n)\)的转移就是这么容易，因此我们的注意力主要应该放在如何设计\(h(n)\)，以及如何去转移。

最直接的思路，便是采用曼哈顿距离（\(\sum_{i=1}^{8}(|x_i-x_i^{*}|+|y_i-y_i^{*}| )\),其中\((x_i,y_i)\)为当前情况下数字\(i\)在方格中所在的位置，\((x_i^{*},y_i^{*})\)表示目标情况下数字\(i\)在方格中所在的位置）作为启发式函数\(h(n)\)。这样只考虑了方格中冰块“不受限移动”所需要的步数，而合法的方格中的冰块移动当且仅当空冰块与某冰块相邻近才能进行，所以这样设计的启发式函数一定满足可容性的条件。

当然还有另外一种思路，便是采用“找不同”的方法，统计在方格相同位置，当前局面有多少个结点和目标结点不同(\(\sum_{i=1}^{3}\sum_{j=1}^{3}(I_{x_{ij}=x_{ij}^{*}}(x))\),其中\(I(x)\)为示性函数)。这个思路为什么也能实现呢？其实和我最开始的思路是类似的。在这样的情况下，还是只考虑了让冰块尽量不受限制移动，尽量减少了格子的移动，这一定是比真实的情况移动步数要少。上述两种思路的一致性显然得证，此处证明略过。

实现¶

定义状态类State

这里有一个需要注意的问题，即我们衡量、转移各状态靠的是\(f\)值，但是我们又把\(f,g,h\)等情况打包到\(State\)类中了，毕竟我们之后还要利用python现成的优先队列\(PriorityQueue\),这种情况下应该如何去比较两个\(State\)类实例呢？\(<\)号正常来说只能比较两个数值，要想进行类的比较就应该重载，使用__lt__方法来重定义比较方法。

还有个值得称道的地方就是使用ndarray的flatten方法将多维数组转化为一维数组，再配合where方法，可以很方便地求出当前状态与目标状态的曼哈顿距离。

class State:
    def __init__(self, matrix, g):
        self.matrix = matrix  # 当前状态的冰雪魔方
        self.g = g  # 真实   
        self.h = self.H() # 估计
        self.f = self.g + self.h
    # 重定义_lt_比较方法,使得类实例能够相互比较,根据f值大小从小到大排序
    def __lt__(self, other):
        return self.f < other.f

    def H(self):
        # 曼哈顿距离
        ans = 0
        for i in self.matrix.flatten():
            x = (np.where(self.matrix == i)[0][0] - np.where(Final == i)[0][0])
            y = (np.where(self.matrix == i)[1][0] - np.where(Final == i)[1][0])
            ans += (np.abs(x)+np.abs(y))
        return ans

另一种不同的思路只要改一下H函数的具体计算方式即可.但是在具体的实现过程中，我必须要特判当前位置0的情况，否则就会出现错误的结果。为什么这里有这样的讲究呢？这主要是因为0并不是实际存在的格子，我们移动它和移动真实存在的格子带来它的变化是等价的。这个问题最本质的东西是“移动”，如果都不移动了，我们还去考虑“这个点到目标的距离”，显然会造成冗余，是不太合适的。

    def H(self):
        # 思路2
        # 表示Matrix中非零元素的位置
        non_zero_elements_in_Matrix = self.matrix != 0
        diff_elements = non_zero_elements_in_Matrix & (Final != self.matrix)
        ans = np.sum(diff_elements)
        return ans

得到下一个可能的矩阵 FindNextMatrix(NowMatrix)

想从某状态转移到与之紧邻的下一状态，其实质还是将那个空冰块(0)上下左右去移动（当然要保证合法，不能越界）.

def FindNextMatrix(NowMatrix):
    NextMatrix = []
    # 把0上下左右移
    # 空格在哪里
    x = np.where(NowMatrix == 0)[0][0]
    y = np.where(NowMatrix == 0)[1][0]
    # 上
    if x-1 >= 0:
        tmp = NowMatrix.copy()
        tmp[x][y] = tmp[x-1][y]
        tmp[x-1][y] = 0
        NextMatrix.append(tmp)
    # 下
    if x+1 <= 2:
        tmp = NowMatrix.copy()
        tmp[x][y] = tmp[x + 1][y]
        tmp[x + 1][y] = 0
        NextMatrix.append(tmp)
    # 左
    if y-1 >= 0:
        tmp = NowMatrix.copy()
        tmp[x][y] = tmp[x][y-1]
        tmp[x][y-1] = 0
        NextMatrix.append(tmp)
    # 右
    if y+1 <= 2:
        tmp = NowMatrix.copy()
        tmp[x][y] = tmp[x][y+1]
        tmp[x][y+1] = 0
        NextMatrix.append(tmp)
    return NextMatrix

A star算法的主流程
初始化优先队列，并将初始状态入队
弹出队首作为当前状态，以其为中心得到几个下一步可能的矩阵，遍历这些矩阵
如果下一步可能的矩阵已经走过了，跳过；没有走过的话将其加入队列中（\(g\)值要加1，因为转移了）
循环上述两步的工作，直到当前状态\(h\)值为0(说明已经到了目标情况)，终止。

这里我像多说一句，就是为了方便区分当前状态是否走过了，去比较两个ndarray数组显然是不太明智的，我将其转化为str类型，再利用in比较：

def Astar(start):
    pq = PriorityQueue()
    visited = []  # 已访问过
    g = 0 # 真实

    state = State(start, 0)
    pq.put(state)
    stateNow = pq.get()

    while stateNow.H() != 0: 
        # 中止条件:当估计距离为0
        visited.append(str(stateNow.matrix.flatten()))
        NextMatrix = FindNextMatrix(stateNow.matrix)
        for nextMatrix in NextMatrix:
            if str(nextMatrix.flatten()) in visited:
                continue 
            g = stateNow.g + 1
            stateNext = State(nextMatrix, g)
            pq.put(stateNext)
        stateNow = pq.get()

    print(g)

题目二杰克的金字塔探险¶

金字塔共有 N 个神秘的房间，其中 1 号房间位于塔顶，N 号房间位于塔底。在这些房间之间，有先知们预先设计好的 M 条秘密通道。这些房间按照它们所在的楼层顺序进行了编号。杰克想从塔顶房间一直探险到塔底，带走尽可能多的宝藏。然而，杰克对寻宝路线有着特别的要求：(1) 他希望走尽可能短的路径，但为了让探险更有趣和挑战性，他想尝试 K 条不同的较短路径。 (2) 他希望在探险过程中尽量节省体力，所以在选择通道时，他总是从所在楼层的高处到低处。现在问题来了，给你一份金字塔内房间之间通道的列表，每条通道用(\(X_i, Y_i, D_i\))表示，表示房间 \(X_i\) 和房间 \(Y_i\) 之间有一条长度为\(D_i\)的下行通道。你需要计算出杰克可以选择的 K 条最短路径的长度，以便了解他在探险过程中的消耗程度。

分析&思路¶

在这个题目中，和第一题类似，就是\(g\)值得计算相对来说是比较容易的——从节点n到其紧邻点m,\(g_m=g_n+dis<n,m>\).我们的精力再次地放到了设计\(h(n)\)上。

至于启发式函数\(h\)的选取，我基于贪心算法的思想，选择的是从当前节点\(n\)出度最小的边之权值。由\(n\)出发，假如还没有到达终点，那么至少还要走过一条边才能到达终点。这个问题中边权非负，并且可以保证终点没有出边，因此这样求得的\(h\)一定不超过当前结点到\(N\)的真实代价，满足可容性要求。

当然还有一种更好的思路。这个问题其实可以抽象出来，形成一个N结点，M条边的有向图，我们为了更好地估计从当前结点n到终点N的距离，为什么不尝试一下使用最短路算法求得最短路呢？这样可以得到一个更接近的估计值\(h\),对算法效率的提升有很大帮助。上述两种思路的一致性显然得证，此处证明略过。

无论什么思路，这个题目和第一题都有所区别——上一个题目只要一个最优解就行了，但是这个题要求前K优解，所以我们不能像第一题那样直接拿下一个可能要加入的状态是否已经visited,如果已经visited就不入队了。我们得到解的顺序是依\(f\)值顺序由小到大进行的（因为优先队列肯定是先弹出\(f\)值小的结点，再弹出\(f\)大的结点），然后在终点，由于\(f=g\)，这样就得到了从起点出发到终点的一个路径长度。又由于我们允许反复走，但是后走肯定没有先走那么优（因为先走的已经把那条更好的路径中的点给弹出了），所以循环迭代K次之后我们就可以得到需要的前K优解。

实现¶

由于和第一题还是很类似的，一些代码上的细节这里就不赘述了。

状态类State

class State:
    def __init__(self,room, g):
        self.room = room
        self.g = g
        self.h = self.H()
        self.f = self.g + self.h
    def __lt__(self, other):
        return self.f < other.f
    def H(self):  
        if self.room == N:  # 已经到底部了
            return 0
        minn = 66666666 
        #找到最小的出边
        for i in islink[self.room]:
            if dis[self.room,i] < minn:
                minn = dis[self.room,i]

        if(minn == 66666666):
            return 0
        else:
            return minn

另一种思路的\(h\)函数写法如下所示，这里我们每次都要去求从当前结点n到终点N的距离，我把问题反过来考虑——我是不是可以去预先地求得从结点N到各结点的单源最短路长度？我采用的是dijkstra算法来求最短路：

d = None
def dijkstra(N,dis):
    vis = [False] * (N+1)
    d = [66666666] * (N+1)
    d[N] = 0
    pq = PriorityQueue()
    pq.put((0,N))
    while not pq.empty():
        dist,node = pq.get()
        if vis[node]:
            continue
        vis[node]=True
        for nei in range(1,N+1):
            if dis[node][nei]>0:
                new_dist = dist+dis[node][nei]
                if new_dist < d[nei]:
                    d[nei] = new_dist
                    pq.put((new_dist,nei))
    return d

class State:
#other code
    def H(self):
        # 另一种思路
        return d[self.room]


#other code
if __name__ == "__main__":
# other code
    d = dijkstra(N,dis2)
    Astar(1)

得到下一个可能的房间

def FindNextRoom(NowRoom):
    NextRoom = []
    for i in islink[NowRoom]:
        NextRoom.append(i)

    return NextRoom

A star算法的主流程
初始化优先队列，并将初始状态入队
弹出队首作为当前状态，如果它已经是终点了，记录到cost中；
如果它还不是终点，以其为起点得到直接有边相邻的结点，遍历这些结点，并把所有这些结点入队
循环上述两步的工作，直到队列为空或者在cost中已经产生了K条记录，终止。

def Astar(start):
    pq = PriorityQueue()
    cost = [] # 每条路径的代价
    state = State(start, 0)
    pq.put(state)

    # 找K条路
    while not pq.empty() and len(cost) < K:
        state = pq.get()
        if state.room == N:  # 到底了
            cost.append(state.g)
        NextRoom = FindNextRoom(state.room)
        for i in NextRoom:
            stateNext = State(i, state.g + dis[state.room, i])
            pq.put(stateNext)

    if len(cost) < K:
        for i in range(K - len(cost)):
            cost.append(-1)

    for i in cost:
        print(i)

四、实验结果与感想¶

题目一冰雪魔方的冰霜之道¶

思路一的结果：

Input: 135720684
1
Input: 105732684
1
Input: 015732684
2
Input: 135782604
1
Input: 715032684
3

思路二的结果：

Input: 135720684
1
Input: 105732684
1
Input: 015732684
2
Input: 135782604
1
Input: 715032684
3

题目二杰克的金字塔探险¶

样例1：

3
3
-1
-1

样例2：

样例3：

样例4：

4
4
5
-1
-1
-1
-1

样例5：

两种思路的输出是一致的，这里限于篇幅就不复制粘贴了。

总结和感想¶

A star算法是一种经典的启发式搜索算法，它结合了UCS和Greedy search的特点，不仅能确保得到最优解，而且还有十分良好的运行效率。A star算法的核心在于设计启发函数，确保其满足理论上的那两个特性。面对这次实验中的这两个实际问题，我感觉很有收获，一来是感受到了设计启发式函数的综合与精巧，我这两个问题都设计了两种启发式函数；二来是更加深刻地理解了搜索这一人工智能中常见的过程。

lab2实验报告¶

一、实验目的¶

二、理论学习¶

三、实验过程¶

题目一 冰雪魔方的冰霜之道¶

分析&思路¶

实现¶

题目二 杰克的金字塔探险¶

分析&思路¶

实现¶

四、实验结果与感想¶

题目一 冰雪魔方的冰霜之道¶

题目二 杰克的金字塔探险¶

总结和感想¶

题目一冰雪魔方的冰霜之道¶

题目二杰克的金字塔探险¶

题目一冰雪魔方的冰霜之道¶

题目二杰克的金字塔探险¶