人工智能原理实验2(1)——八数码问题(BFS、DFS、UCS、IDS、A*算法)

????实验内容????

要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态(左)到目标状态(右)
在这里插入图片描述在这里插入图片描述

????BFS、DFS实现????

一些定义

表示数据结构
在这里插入图片描述

open表的设计
两者都是同一种open表数据结构(python 中的列表list),为实现不同的算法,在实现时只需要依据算法特点设定元素进出list的顺序即可
BFS:依据先进先出规则,新加入的状态节点放到list的末尾
在这里插入图片描述
DFS:依据先进后出规则,新加入的状态节点放入到list的首位
在这里插入图片描述

状态扩展规则表示
八数码用一个3×3的矩阵来存储
通过交换空格(数字0)与其他数字的位置,实现状态扩展
在这里插入图片描述
考虑特殊边界情况:

  • 当空格(数字0)在矩阵的最左一列时,不能向左移动在这里插入图片描述
  • 当空格(数字0)在矩阵的最右一列时,不能向右移动在这里插入图片描述
  • 当空格(数字0)在矩阵的最上一行时,不能向上移动在这里插入图片描述
  • 当空格(数字0)在矩阵的最下一行时,不能向下移动在这里插入图片描述
    ??代码逻辑??
    在这里插入图片描述

BFS代码

# BFS
import numpy as np
import copy
import matplotlib.pyplot as plt
import time

# 状态节点类
class Node:
    def __init__(self,data,depth,parent):
        self.data=data # 存储状态,3×3格子
        self.depth=depth # 深度
        self.parent = parent # 父节点,方便回溯出最佳路径
        
# BFS_solve
class BFS:
    # 初始化
    def __init__(self,initial,goals):
        self.initial=Node(np.reshape(initial,(3,3)),0,"None") # 初始状态
        self.goals=Node(np.reshape(goals,(3,3)),0,"None") # 目标状态
        self.open_=[self.initial] # 将初始状态加入open表
        self.close_=[] # close表

    # 展示最终路径
    def __show_path(self,node):
        arr=node.data
        # 创建颜色映射,0用红色表示,其他用绿色表示
        colors = [['pink' if num == 0 else 'lightgreen' for num in row] for row in arr]
        fig, ax = plt.subplots(figsize=(1.2, 1.2))
        ax.axis('off') # 隐藏坐标轴

        # 创建表格对象
        table = plt.table(cellText=arr,
                          cellColours=colors,
                          loc='center',
                          cellLoc='center')

        table.set_fontsize(15) # 设置格子的字体大小
        table.scale(1, 1) # 调整表格布局

        # 设置单元格的宽度和高度
        cell_width = 1.0 / 3.0
        cell_height = 1.0 / 3.0

        # 设置每个单元格的宽度和高度相等,使其为正方形
        for i in range(3):
            for j in range(3):
                cell = table.get_celld()[(i, j)]
                cell.set_width(cell_width)
                cell.set_height(cell_height)

        plt.show() # 显示图像
    
    # 交换格子位置
    def __move(self,n,postion,row,col):
        if postion =="left":
            n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]
        elif postion == "right":
            n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]
        elif postion == "up":
            n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]
        elif postion == "down":
            n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]
        return n

    # 判断新状态和close表和open表是否重复状态
    def __is_exist(self,three_result,close_,open_):
        for i in range(len(close_)):
            if (three_result == close_[i].data).all():
                return True
        for i in range(len(open_)):
            if (three_result == open_[i].data).all():
                return True
        return False

    def solve(self):
        cnt = 0 # 遍历节点次数
        depth=1 # 深度
        while self.open_:
            # 打印open和close表,观察它们的变化
#             print(f"====??????遍历第{cnt}个节点时: open表??????====")
#             for state in self.open_:
#                  print(state.data)
#             print(f"====??????遍历第{cnt}个节点时: close表??????====")
#             for state in self.close_:
#                  print(state.data)
            
            cnt = cnt+1
            # 初始化算子
            direction=['up', 'down', 'right', 'left']
            # 从open表中删除第一个状态并放入close表中
            n = self.open_.pop(0)
            self.close_.append(n)

            # 打印过程
#             print(f"==== 层数:{n.depth} ====")
#             print(f"访问第{cnt}个节点:
{n.data}")
            
            
            # ==================结束条件==================
            if (n.data == self.goals.data).all():
                resultAll=[]
                resultAll.append(n)
                while n.parent!="None": # 回溯路径
                    resultAll.append(n.parent)
                    n = n.parent
                
                resultAll_len=len(resultAll)
                print("展示最优BFS路径: ")
                for j in range(resultAll_len):
                    print(f"======??????第{j}步??????======")
                    result = resultAll.pop(-1) # 弹出
                    self.__show_path(result)
                print("==================BFS结束搜索==================")
                print(f"总共遍历的节点数目:{cnt}")
                print(f"找到的可行路径的节点数目:{resultAll_len}")
                break

            # ==================生成n的所有子状态,并加入到open表后方================
            # 找出空格位置
            postion = np.where(n.data == 0)
            i = postion[0]
            j = postion[1]
            length_down=n.data.shape[0]
            length_right=n.data.shape[1]

            # 避免误操作
            if i==0: # 清除上操作:在第一行,不能向上移动
                direction.remove("up")
            if j==0: # 清除左操作:在第一列,不能向左移动
                direction.remove("left")
            if i == length_down-1: # 清除下操作:在末行,不能向下移动
                direction.remove("down")
            if j == length_right-1: # 清除右操作:在末列,不能向右移动
                direction.remove("right")

            # 遍历所有可能子状态
            for p in range(len(direction)):
                copy_n = copy.deepcopy(n)
                three_result = self.__move(copy_n.data,direction
,i,j) # 判断是否存在于close表 if (self.__is_exist(three_result,self.close_,self.open_)): continue self.open_.append(Node(three_result,n.depth+1,n)) # 插入到open尾部,先进先出 # 初始化状态 initial_state=[2,8,3,1,6,4,7,0,5] goal_state=[1,2,3,8,0,4,7,6,5] start_time = time.time() # 记录程序开始时间 bfs = BFS(initial_state,goal_state) bfs.solve() end_time = time.time() # 记录程序结束时间 print(f"程序的运行时间为:{(end_time-start_time)*1000} ms")

DFS代码

# DFS
import numpy as np
import copy
import matplotlib.pyplot as plt
import time

# 状态节点类
class Node:
    def __init__(self,data,depth,parent):
        self.data=data # 存储状态,3×3格子
        self.depth=depth # 深度
        self.parent = parent # 父节点,方便回溯出最佳路径
        
# BFS_solve
class DFS:
    # 初始化
    def __init__(self,initial,goals):
        self.initial=Node(np.reshape(initial,(3,3)),0,"None") # 初始状态
        self.goals=Node(np.reshape(goals,(3,3)),0,"None") # 目标状态
        self.open_=[self.initial] # 将初始状态加入open表
        self.close_=[] # close表
        self.max_depth=10 # 最大搜索深度

    # 展示最终路径
    def __show_path(self,node):
        arr=node.data
        # 创建颜色映射,0用红色表示,其他用绿色表示
        colors = [['pink' if num == 0 else 'lightgreen' for num in row] for row in arr]
        fig, ax = plt.subplots(figsize=(1.2, 1.2))
        ax.axis('off') # 隐藏坐标轴

        # 创建表格对象
        table = plt.table(cellText=arr,
                          cellColours=colors,
                          loc='center',
                          cellLoc='center')

        table.set_fontsize(15) # 设置格子的字体大小
        table.scale(1, 1) # 调整表格布局

        # 设置单元格的宽度和高度
        cell_width = 1.0 / 3.0
        cell_height = 1.0 / 3.0

        # 设置每个单元格的宽度和高度相等,使其为正方形
        for i in range(3):
            for j in range(3):
                cell = table.get_celld()[(i, j)]
                cell.set_width(cell_width)
                cell.set_height(cell_height)

        plt.show() # 显示图像
    
    # 交换格子位置
    def __move(self,n,postion,row,col):
        if postion =="left":
            n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]
        elif postion == "right":
            n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]
        elif postion == "up":
            n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]
        elif postion == "down":
            n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]
        return n

    # 判断新状态和close表和open表是否重复状态
    def __is_exist(self,three_result,close_,open_):
        for i in range(len(close_)):
            if (three_result == close_[i].data).all():
                return True
        for i in range(len(open_)):
            if (three_result == open_[i].data).all():
                return True
        return False
    
    def solve(self):
        #遍历个数
        cnt = 0
        depth=1
        while self.open_:
            # 打印open和close表,观察它们的变化
#             print(f"====??????遍历第{cnt}个节点时: open表??????====")
#             for state in self.open_:
#                  print(state.data)
#             print(f"====??????遍历第{cnt}个节点时: close表??????====")
#             for state in self.close_:
#                  print(state.data)
            
            cnt = cnt+1
            # 初始化算子
            direction=['up', 'down', 'right', 'left']
            # 从open表中删除第一个状态并放入close表中
            n = self.open_.pop(0)
            self.close_.append(n)

            # 打印过程
#             print(f"==== 层数:{n.depth} ====")
#             print(f"访问第{cnt}个节点:
{n.data}")
            
            # ==================结束条件==================
            if (n.data == self.goals.data).all():
                resultAll=[]
                resultAll.append(n)
                while n.parent!="None": # 回溯路径
                    resultAll.append(n.parent)
                    n = n.parent
            
                resultAll_len=len(resultAll)
                print("展示DFS路径: ")
                for j in range(resultAll_len):
                    print(f"======??????第{j}步??????======")
                    result = resultAll.pop(-1) # 弹出
                    self.__show_path(result)
                print("==================DFS结束搜索==================")
                print(f"总共遍历的节点数目:{cnt}")
                print(f"找到的可行路径的节点数目:{resultAll_len}")
                break

            # ==================生成n的所有子状态,并加入到open表================
            # 找出空格位置
            postion = np.where(n.data == 0)
            i = postion[0]
            j = postion[1]
            length_down=n.data.shape[0]
            length_right=n.data.shape[1]

            # 避免误操作
            if i==0: # 清除上操作:在第一行,不能向上移动
                direction.remove("up")
            if j==0: # 清除左操作:在第一列,不能向左移动
                direction.remove("left")
            if i == length_down-1: # 清除下操作:在末行,不能向下移动
                direction.remove("down")
            if j == length_right-1: # 清除右操作:在末列,不能向右移动
                direction.remove("right")

            # 设定搜索的最大深度,不然会一直递归下去
            if n.depth>=self.max_depth:
                continue
                
            # 遍历所有可能子状态
            for p in range(len(direction)):
                copy_n = copy.deepcopy(n)
                three_result = self.__move(copy_n.data,direction
,i,j) # 判断是否存在于close表 if (self.__is_exist(three_result,self.close_,self.open_)): continue self.open_.insert(0,Node(three_result,n.depth+1,n)) # 新状态插入到open表最前面,确保往下深度搜索 # 初始化状态 initial_state=[2,8,3,1,6,4,7,0,5] goal_state=[1,2,3,8,0,4,7,6,5] start_time = time.time() # 记录程序开始时间 dfs = DFS(initial_state,goal_state) dfs.solve() end_time = time.time() # 记录程序结束时间 print(f"程序的运行时间为:{(end_time-start_time)*1000} ms")

运行结果(最优路径展示)

BFS
在这里插入图片描述在这里插入图片描述
在这里插入图片描述

DFS(设置最高深度为10时的结果)
在这里插入图片描述在这里插入图片描述
在这里插入图片描述

????UCS、IDS????

BFS、DFS的拔高算法

UCS代码实现

# UCS
import numpy as np
import heapq
import matplotlib.pyplot as plt
import time

# 状态节点类
class Node:
    def __init__(self, data, cost, parent):
        self.data = data  # 存储状态,3×3格子
        self.cost = cost  # 代价
        self.parent = parent  # 父节点,方便回溯出最佳路径

# UCS_solve
class UCS:
    # 初始化
    def __init__(self, initial, goals):
        self.initial = Node(np.reshape(initial, (3, 3)), 0, "None")  # 初始状态
        self.goals = Node(np.reshape(goals, (3, 3)), 0, "None")  # 目标状态
        self.open_ = []  # open表使用优先队列
        self.close_ = []  # close表

    # 展示最终路径
    def __show_path(self, node):
        arr = node.data
        # 创建颜色映射,0用红色表示,其他用绿色表示
        colors = [['pink' if num == 0 else 'lightgreen' for num in row] for row in arr]
        fig, ax = plt.subplots(figsize=(1.2, 1.2))
        ax.axis('off')  # 隐藏坐标轴

        # 创建表格对象
        table = plt.table(cellText=arr,
                          cellColours=colors,
                          loc='center',
                          cellLoc='center')

        table.set_fontsize(15)  # 设置格子的字体大小
        table.scale(1, 1)  # 调整表格布局

        # 设置单元格的宽度和高度
        cell_width = 1.0 / 3.0
        cell_height = 1.0 / 3.0

        # 设置每个单元格的宽度和高度相等,使其为正方形
        for i in range(3):
            for j in range(3):
                cell = table.get_celld()[(i, j)]
                cell.set_width(cell_width)
                cell.set_height(cell_height)

        plt.show()  # 显示图像

    # 交换格子位置
    def __move(self, n, postion, row, col):
        if postion == "left":
            n[row, col], n[row, col - 1] = n[row, col - 1], n[row, col]
        elif postion == "right":
            n[row, col], n[row, col + 1] = n[row, col + 1], n[row, col]
        elif postion == "up":
            n[row, col], n[row - 1, col] = n[row - 1, col], n[row, col]
        elif postion == "down":
            n[row, col], n[row + 1, col] = n[row + 1, col], n[row, col]
        return n

    # 判断新状态和close表和open表是否重复状态
    def __is_exist(self, three_result, close_, open_):
        for i in range(len(close_)):
            if (three_result == close_[i].data).all():
                return True
        for i in range(len(open_)):
            if (three_result == open_[i][2].data).all():
                return True
        return False

    def solve(self):
        # 添加初始状态到open表,优先队列加入三元组(cost,id,Node)
        heapq.heappush(self.open_, (0, id(self.initial), self.initial))
        cnt=0
        while self.open_:
            # 取出代价最小的节点
            cost, _, node = heapq.heappop(self.open_)
            self.close_.append(node)
            
            cnt+=1
            if (node.data == self.goals.data).all():
                resultAll = []
                resultAll.append(node)
                while node.parent != "None":  # 回溯路径
                    resultAll.append(node.parent)
                    node = node.parent

                resultAll_len = len(resultAll)
                print("展示UCS路径: ")
                for j in range(resultAll_len):
                    print(f"======??????第{j}步??????======")
                    result = resultAll.pop(-1)  # 弹出
                    self.__show_path(result)
                print("==================UCS结束搜索==================")
                print(f"总共遍历的节点数目:{cnt}")
                print(f"找到的可行路径的节点数目:{resultAll_len}")
                break

            # ======================生成n的所有子状态,并加入到open表====================
            postion = np.where(node.data == 0)
            i = postion[0][0]
            j = postion[1][0]
            direction = ['up', 'down', 'right', 'left']
            length_down = node.data.shape[0]
            length_right = node.data.shape[1]

            # 避免误操作
            if i==0: # 清除上操作:在第一行,不能向上移动
                direction.remove("up")
            if j==0: # 清除左操作:在第一列,不能向左移动
                direction.remove("left")
            if i == length_down-1: # 清除下操作:在末行,不能向下移动
                direction.remove("down")
            if j == length_right-1: # 清除右操作:在末列,不能向右移动
                direction.remove("right")
            
            # 遍历所有可能子状态
            for p in range(len(direction)):
                copy_n = np.copy(node.data)
                new_data = self.__move(copy_n, direction
, i, j) if self.__is_exist(new_data, self.close_, self.open_): continue new_node = Node(new_data, node.cost + 1, node) heapq.heappush(self.open_, (new_node.cost, id(new_node), new_node)) # 初始化状态 initial_state = [2, 8, 3, 1, 6, 4, 7, 0, 5] goal_state = [1, 2, 3, 8, 0, 4, 7, 6, 5] start_time = time.time() # 记录程序开始时间 ucs = UCS(initial_state, goal_state) ucs.solve() end_time = time.time() # 记录程序结束时间 print(f"程序的运行时间为:{(end_time-start_time)*1000} ms")

IDS代码实现

# IDS
# 状态节点类
import copy
class Node:
    def __init__(self,data,depth,parent):
        self.data=data # 存储状态,3×3格子
        self.depth=depth # 深度
        self.parent = parent # 父节点,方便回溯出最佳路径
class IDS:
    # 初始化
    def __init__(self,initial,goals):
        self.initial=Node(np.reshape(initial,(3,3)),0,"None") # 初始状态
        self.goals=Node(np.reshape(goals,(3,3)),0,"None") # 目标状态
        self.max_depth=10 # 最大搜索深度

        # 展示最终路径
    def __show_path(self,node):
        arr=node.data
        # 创建颜色映射,0用红色表示,其他用绿色表示
        colors = [['pink' if num == 0 else 'lightgreen' for num in row] for row in arr]
        fig, ax = plt.subplots(figsize=(1.2, 1.2))
        ax.axis('off') # 隐藏坐标轴

        # 创建表格对象
        table = plt.table(cellText=arr,
                          cellColours=colors,
                          loc='center',
                          cellLoc='center')

        table.set_fontsize(15) # 设置格子的字体大小
        table.scale(1, 1) # 调整表格布局

        # 设置单元格的宽度和高度
        cell_width = 1.0 / 3.0
        cell_height = 1.0 / 3.0

        # 设置每个单元格的宽度和高度相等,使其为正方形
        for i in range(3):
            for j in range(3):
                cell = table.get_celld()[(i, j)]
                cell.set_width(cell_width)
                cell.set_height(cell_height)

        plt.show() # 显示图像
        
    
    # 交换格子位置
    def __move(self,n,postion,row,col):
        if postion =="left":
            n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]
        elif postion == "right":
            n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]
        elif postion == "up":
            n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]
        elif postion == "down":
            n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]
        return n

    def __depth_limited_DFS(self, node, depth_limit):
        if (node.data == self.goals.data).all():
            return [node]
        if depth_limit <= 0:
            return []
        if node.depth >= depth_limit:
            return []
        
        direction=['up', 'down', 'right', 'left']
        
        # ======================生成n的所有子状态====================
        postion = np.where(node.data == 0)
        i = postion[0]
        j = postion[1]
        length_down=node.data.shape[0]
        length_right=node.data.shape[1]

        result = []
        
        # 避免误操作
        if i==0: # 清除上操作:在第一行,不能向上移动
            direction.remove("up")
        if j==0: # 清除左操作:在第一列,不能向左移动
            direction.remove("left")
        if i == length_down-1: # 清除下操作:在末行,不能向下移动
            direction.remove("down")
        if j == length_right-1: # 清除右操作:在末列,不能向右移动
            direction.remove("right")
        
        for p in range(len(direction)):
            copy_n = copy.deepcopy(node)
            three_result = self.__move(copy_n.data,direction
, i, j) child_node = Node(three_result, node.depth + 1, node) result.append(child_node) res = self.__depth_limited_DFS(child_node, depth_limit - 1) if res: return [child_node] + res return [] def solve(self): for depth_limit in range(self.max_depth + 1): result = self.__depth_limited_DFS(self.initial, depth_limit) if result: print("展示IDS路径: ") for node in result: self.__show_path(node) print("==================IDS结束搜索==================") print(f"找到的可行路径的节点数目:{len(result)}") return print("未找到可行路径") # 初始化状态 initial_state=[2,8,3,1,6,4,7,0,5] goal_state=[1,2,3,8,0,4,7,6,5] start_time = time.time() # 记录程序开始时间 ids = IDS(initial_state,goal_state) ids.solve() end_time = time.time() # 记录程序结束时间 print(f"程序的运行时间为:{(end_time-start_time)*1000} ms")

????A*实现????

表示数据结构
相比之前BFS多加了启发函数得分,以及重载了open表对于各个状态节点的排序规则,让启发函数得分小的排在open表前面
在这里插入图片描述

open表的设计
依据启发函数得分的原则,每次取出启发函数得分score最小的状态节点
在这里插入图片描述

搜索空间展示

左图为代码结果,右图为左图形象化的空间图(手画)
在这里插入图片描述在这里插入图片描述

A*代码

# A*
import numpy as np
import copy
import math
import matplotlib.pyplot as plt
import time

# 状态节点类
class Node:
    def __init__(self,data,depth,parent,score):
        self.data = data # 存储状态,3×3格子
        self.depth = depth # 深度
        self.parent = parent # 父节点,方便回溯出最佳路径
        self.score = score # 启发函数得分
    
    def __lt__(self, other): # 重载node节点间的大小关系,依据score比较大小
        return self.score < other.score
        
class A:
    def __init__(self,initial,goals):
        self.initial=Node(np.reshape(initial,(3,3)),0,"None",0) # 初始状态
        self.goals=Node(np.reshape(goals,(3,3)),0,"None",0) # 目标状态
        self.open_=[self.initial]  # 将初始状态加入open表
        self.close_=[]
        self.__cal_score(self.initial,self.goals) # 初始节点启发函数得分

    # 估价函数——错位数
    def __cal_score(self,node,goals):
        gn = node.depth  # g(n):当前状态的深度
        hn = np.count_nonzero(node.data-goals.data)  # h(n):当前状态与目标状态的不同位置个数
        node.score = gn+hn
#         node.score = gn
        node.score = hn
    
        return node
    
    
    # 估价函数——曼哈顿距离
    def __cal_score_manhattan(self,node,goals):
        distance=0
        arr=node.data
        for i in range(3):
            for j in range(3):
                if arr[i][j]!=0:
                    x,y=divmod(arr[i][j]-1,3)
                    distance+=abs(x-i)+abs(y-j)
        node.score=distance
        return node
    
    # 估价函数——欧式距离
    def __cal_score_euclidean(self,node,goals):
        distance=0
        arr=node.data
        for i in range(3):
            for j in range(3):
                if arr[i][j]!=0:
                    x, y = divmod(arr[i][j] - 1, 3)
                    distance += ((x - i) ** 2 + (y - j) ** 2) ** 0.5
        node.score=distance
        return node
    
    
    # 展示最终路径
    def __show_path(self,node):
        arr=node.data
        # 创建颜色映射,0用红色表示,其他用绿色表示
        colors = [['pink' if num == 0 else 'lightgreen' for num in row] for row in arr]
        fig, ax = plt.subplots(figsize=(1.2, 1.2))
        ax.axis('off') # 隐藏坐标轴

        # 创建表格对象
        table = plt.table(cellText=arr,
                          cellColours=colors,
                          loc='center',
                          cellLoc='center')

        table.set_fontsize(15) # 设置格子的字体大小
        table.scale(1, 1) # 调整表格布局

        # 设置单元格的宽度和高度
        cell_width = 1.0 / 3.0
        cell_height = 1.0 / 3.0

        # 设置每个单元格的宽度和高度相等,使其为正方形
        for i in range(3):
            for j in range(3):
                cell = table.get_celld()[(i, j)]
                cell.set_width(cell_width)
                cell.set_height(cell_height)

        plt.show() # 显示图像


    # 交换格子位置
    def __move(self,n,postion,row,col):
        if postion =="left":
            n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]
        elif postion == "right":
            n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]
        elif postion == "up":
            n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]
        elif postion == "down":
            n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]
        return n

    # 判断新状态和close表和open表是否重复状态
    def __is_exist(self,three_result,close_,open_):
        for i in range(len(close_)):
            if (three_result == close_[i].data).all():
                return True
        for i in range(len(open_)):
            if (three_result == open_[i].data).all():
                return True
        return False


    def solve(self):
        
        cnt = 0 # 遍历节点次数
        depth =1
        while self.open_:
            # 打印open和close表,观察它们的变化
#             print(f"====??????遍历第{cnt}个节点时: open表??????====")
#             for state in self.open_:
#                  print(state.data)
#             print(f"====??????遍历第{cnt}个节点时: close表??????====")
#             for state in self.close_:
#                  print(state.data)

            cnt = cnt+1
            #初始化算子
            direction=['up', 'down', 'right', 'left']
            #从open表中删除第一个状态并放入close表中
            n = self.open_.pop(0)
            self.close_.append(n)

            # 打印过程
#             print(f"==== 层数:{n.depth},  启发函数值得分:{n.score} ====")
#             print(f"访问第{cnt}个节点:
{n.data}")
#             self.__show_path(n)
            
            # ==================结束条件==================
            if (n.data == self.goals.data).all():
                resultAll=[]
                resultAll.append(n)
                while n.parent!="None": # 回溯路径
                    resultAll.append(n.parent)
                    n = n.parent
            
                resultAll_len=len(resultAll)
                print("展示最优A*路径: ")
                for j in range(resultAll_len):
                    print(f"======??????第{j}步??????======")
                    result = resultAll.pop(-1) # 弹出
                    self.__show_path(result)
                print("==================A*结束搜索==================")
                print(f"总共遍历的节点数目:{cnt}")
                print(f"找到的可行路径的节点数目:{resultAll_len}")
                break

            # ==================生成n的所有子状态,并加入到open表后方================
            # 找出空格位置
            postion = np.where(n.data == 0)
            i = postion[0]
            j = postion[1]
            length_down=n.data.shape[0]
            length_right=n.data.shape[1]


            # 避免误操作
            if i==0: # 清除上操作:在第一行,不能向上移动
                direction.remove("up")
            if j==0: # 清除左操作:在第一列,不能向左移动
                direction.remove("left")
            if i == length_down-1: # 清除下操作:在末行,不能向下移动
                direction.remove("down")
            if j == length_right-1: # 清除右操作:在末列,不能向右移动
                direction.remove("right")

            # 遍历所有可能子状态
            for p in range(len(direction)):
                copy_n = copy.deepcopy(n)
                three_result = self.__move(copy_n.data,direction
,i,j) # 判断是否存在于close表 if (self.__is_exist(three_result,self.close_,self.open_)): continue # 评估当前节点的启发函数得分score score_t = self.__cal_score(Node(three_result,n.depth+1,n,0),self.goals) # 错位数 # score_t = self.__cal_score_manhattan(Node(three_result,n.depth+1,n,0),self.goals) # 曼哈顿距离 # score_t = self.__cal_score_euclidean(Node(three_result,n.depth+1,n,0),self.goals) # 欧式距离 self.open_.append(score_t) # 将open表依据节点中的score排序 self.open_ = sorted(self.open_) # 初始化状态 initial_state=[2,8,3,1,6,4,7,0,5] goal_state=[1,2,3,8,0,4,7,6,5] #初始化类 start_time = time.time() # 记录程序开始时间 a = A(initial_state,goal_state) a.solve() end_time = time.time() # 记录程序结束时间 print(f"程序的运行时间为:{(end_time-start_time)*1000} ms")

open表和close表的变化

内容过多,就不一一列举了,详情去代码运行输出吧
在这里插入图片描述
(省略余下)…

最优路径展示

在这里插入图片描述在这里插入图片描述
在这里插入图片描述

????总结????

从以上结果可以看出

  • DFS无限往下递归,直到找到目标节点才结束(作为无信息搜索,每一次扩展都像在“碰运气”,>如果不设置搜索的最大深度,搜索次数几乎可以接近无限),因此找到的不一定是最短的路线。
  • BFS每一次扩展的点,都是距离出发点最近、步骤最少的。如此这样递推,当扩展到目标点的时候,也是距离出发点最近的。这样的路径自然形成了最短的路线。
  • A*算法在盲目搜索的基础上,会对节点的open表进行一个排序,使用估价函数去计算启发函数得分score,这样目标明确,能够迅速找出一个尽可能最优的局部最优解。
  • 可以看到A算法效率远远高于DFS算法和BFS算法(遍历节点数少,运行时间短),但是A算法也有缺点,不能搜索到所有解,当需要搜索所有能到达终点的路径时,往往要使用DFS才能实现。

??时间复杂度、空间复杂度对比??

深度优先搜索DFS

  • 时间复杂度:在一般情况下为 O(b^m),其中 b 是分支因子,m 是搜索树最大深度。在最坏情况下,可能需要搜索整个状态空间,因此时间复杂度较高。
  • 空间复杂度:取决于搜索树的深度,为 O(bm),其中 b 是分支因子,m 是搜索树最大深度。

一致代价搜索UCS:

  • 时间复杂度: O(b^( C/ε)),其中 b 是分支因子,C 是最低成本解的代价,每一步代价至少为ε。
  • 空间复杂度:和时间复杂度相似

迭代加深的深度优先搜索算法 IDS

  • 时间复杂度: O(b^d),其中 b 是分支因子,d 是最浅的解的深度。迭代加深的主要特点是在每次搜索中限制深度,
  • 空间复杂度: O(bd),其中 b 是分支因子,d 是最浅的解的深度,取决于搜索树的深度,与深度优先搜索相似。
  • IDS综合了BFS和DFS的优点:时间复杂度只比BFS稍差一点,而空间复杂度与深搜相同,比广搜小很多

A*搜索算法

  • 时间复杂度:取决于启发式函数的质量。在最坏情况下,时间复杂度为指数级的 O(b^d),其中 b 是分支因子,d 是最浅的解的深度。但是在实际应用中,由于启发式函数的使用,A*搜索通常能够在较短的时间内找到最优解。
  • 空间复杂度:取决于许多因素,包括搜索树的宽度、深度和启发式函数的质量。在最坏情况下,空间复杂度为 O(b^d),但通常情况下能够比较好地控制空间占用。