人工智能原理实验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{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[p],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{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[p],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[p], 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[p], 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{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[p],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)，但通常情况下能够比较好地控制空间占用。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/337382.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

使用Scrapy 爬取“http://tuijian.hao123.com/”网页中左上角“娱乐”、“体育”、“财经”、“科技”、历史等名称和URL

使用Scrapy 爬取“http://tuijian.hao123.com/”网页中左上角“娱乐”、“体育”、“财经”、“科技”、历史等名称和URL

一、网页信息 二、检查网页&#xff0c;找出目标内容 三、根据网页格式写正常爬虫代码 from bs4 import BeautifulSoup import requestsheaders {User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/107.0.0.0 Safari/53…
阅读更多...
恢复因各种情况丢失的数据和文件的恢复软件汇集。

恢复因各种情况丢失的数据和文件的恢复软件汇集。

数据和文件恢复软件工具是直观的应用程序&#xff0c;可以从各种存储介质中恢复有价值且敏感的业务相关数据。这些宝贵的救生应用程序使企业能够恢复因不可预测的情况而丢失的数据。 存储介质解决方案可能会因网络攻击、病毒、数据泄露、硬盘故障等多种原因而丢失或损坏数据。…
阅读更多...
Dart安装(Winodws)

Dart安装(Winodws)

Dart官网&#xff1a; https://dart.dev/ 一、命令行安装 https://dart.dev/get-dart You can install the Dart SDK using Chocolatey. error Important: These commands require administrator rights. Here’s one way to open a Command Prompt window that has admin …
阅读更多...
ROS第 12 课 Launch 启动文件的使用方法

ROS第 12 课 Launch 启动文件的使用方法

文章目录 第 12 课 Launch 启动文件的使用方法1.本节前言2.Lanuch 文件基本语法2.2 参数设置2.3 重映射嵌套 3.实操练习 第 12 课 Launch 启动文件的使用方法 1.本节前言 我们在前面的教程里面通过命令行来尝试运行新的节点。但随着创建越来越复杂的机器人系统中&#xff0c;打…
阅读更多...
前后置、断言、提取变量、数据库操作功能

前后置、断言、提取变量、数据库操作功能

前置操作和后置操作都是 API 请求在发送和响应过程中执行的脚本&#xff0c;主要用于在发起 API 请求前和获得响应后完成验证或执行某些操作&#xff0c;目的是为了提高 API 调试和测试的效率&#xff0c;并确保接口的正确性。 前置操作​ 前置操作是在 API 请求之前执行的脚本…
阅读更多...
[计算机网络]基本概念

[计算机网络]基本概念

目录 1.ip地址和端口号 1.1IP地址 1.2端口号 2.认识协议 2.1概念&#xff1a; 2.2知名协议的默认端口 3.五元组 4.协议分层 4.1分层的作用 4.2OSI七层模型 4.3TCP/IP五层&#xff08;四层&#xff09;模型 ​编辑4.4网络设备对应的分层&#xff1a; ​编辑以下为跨…
阅读更多...
【51、32单片机】模块化编程（.c .h文件）

【51、32单片机】模块化编程（.c .h文件）

0、前言 USER&#xff1a;存放工程文件、主函数文件 main.c,以及其他包括system_stm32f10x.c等 CORE &#xff1a;用来存放核心文件和启动文件 OBJ &#xff1a;是用来存放编译过程文件以及hex 文件 STM32F10x_FWLib &#xff1a;用来存放 ST 官方提供的库函数源码文件 SY…
阅读更多...
【开源】基于JAVA的CRM客户管理系统

【开源】基于JAVA的CRM客户管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统设计3.1 用例设计3.2 E-R 图设计3.3 数据库设计3.3.1 客户表3.3.2 商品表3.3.3 客户跟踪表3.3.4 客户消费表3.3.5 系统角色表 四、系统展示五、核心代码5.1 查询客户5.2 新增客户跟踪记录5.3 新增客户消费订单5.4 查…
阅读更多...
让uniapp小程序支持多色图标icon：iconfont-tools-cli

让uniapp小程序支持多色图标icon：iconfont-tools-cli

前景&#xff1a; uniapp开发小程序项目时&#xff0c;对于iconfont多色图标无法直接支持&#xff1b;若将多色icon下载引入项目则必须关注包体&#xff0c;若将图标放在oss或者哪里管理&#xff0c;加载又是一个问题&#xff0c;因此大多采用iconfont-tools工具&#xff0c;但…
阅读更多...
设计模式-资源库模式

设计模式-资源库模式

设计模式专栏 模式介绍模式特点应用场景资源库模式与关系型数据库的区别代码示例Java实现资源库模式Python实现资源库模式 资源库模式在spring中的应用 模式介绍 资源库模式是一种架构模式&#xff0c;介于领域层与数据映射层&#xff08;数据访问层&#xff09;之间。它的存在…
阅读更多...
JVM工作原理与实战(二十一)：内存管理

JVM工作原理与实战(二十一)：内存管理

专栏导航 JVM工作原理与实战 RabbitMQ入门指南 从零开始了解大数据 目录 专栏导航 前言 一、不同语言的内存管理 1.C/C的内存管理 2.Java的内存管理 二、垃圾回收的对比 1.自动垃圾回收与手动垃圾回收的对比 2.优点与缺点 总结 前言 JVM作为Java程序的运行环境&#…
阅读更多...
Vue2：全局事件总线

Vue2：全局事件总线

一、场景描述 之前我们学习了&#xff0c;通过props实现父子组件之间的通信。通过自定义组件&#xff0c;实现了子给父传递数据。 那么&#xff0c;兄弟关系的组件&#xff0c;如何通信了&#xff1f;任意组件间如何通信了&#xff1f; 这个时候&#xff0c;就要学习全局事件总…
阅读更多...
5G_射频测试_发射机测量（四）

5G_射频测试_发射机测量（四）

6.2 Base station output power 用于测量载波发射功率的大小&#xff0c;功率越大小区半径越大但是杂散也会越大 载波功率&#xff08;用频谱仪测&#xff09;天线口功率&#xff08;用功率计测&#xff09;载波功率是以RBW为单位的filter测量的积分功率不同带宽的多载波测试时…
阅读更多...
Spring-AOP入门案例

Spring-AOP入门案例

文章目录 Spring-AOP入门案例概念:通知(Advice)切入点(Pointcut )切面&#xff08;Aspect&#xff09; 目标对象(target)代理对象(Proxy)顾问&#xff08;Advisor)连接点(JoinPoint) 简单需求&#xff1a;在接口执行前输出当前系统时间Demo原始未添加aop前1 项目包结构2 创建相…
阅读更多...
在Java中调企微机器人发送消息到群里

在Java中调企微机器人发送消息到群里

目录 如何使用群机器人 消息类型及数据格式 文本类型 markdown类型 图片类型 图文类型 文件类型 模版卡片类型 文本通知模版卡片 图文展示模版卡片 消息发送频率限制 文件上传接口 Java 执行语句 String url "webhook的Url"; String result HttpReque…
阅读更多...
pxe高效批量网络装机 以及安装教程

pxe高效批量网络装机 以及安装教程

系统装机的三种引导模式 1.pe 2光驱 3.网卡 打开本机桌面 可以看见背景图片 查看配置文件内容 文件时引导选项的功能 pxe原理&#xff1a; 先根据dhcp找到IP地址、和引导程序的地址&#xff0c;还提供客户机tftp地址&#xff0c;因为tftp是小文件&#xff0c;容量小&#…
阅读更多...
如何用H5+CSS+JS写一个简单的招聘网站

如何用H5+CSS+JS写一个简单的招聘网站

大家好&#xff0c;我是猿码叔叔&#xff0c;一个 Java 语言开发者。应网友要求&#xff0c;写一个简单的招聘页面。由于技术原因&#xff0c;页面相对简单&#xff0c;朋友们可以选择性的阅读&#xff0c;如果对您有帮助&#xff0c;也可直接拿去使用&#xff0c;因为接下来除…
阅读更多...
[足式机器人]Part2 Dr. CAN学习笔记- 最优控制Optimal Control Ch07-2 动态规划 Dynamic Programming

[足式机器人]Part2 Dr. CAN学习笔记- 最优控制Optimal Control Ch07-2 动态规划 Dynamic Programming

本文仅供学习使用 本文参考&#xff1a; B站&#xff1a;DR_CAN Dr. CAN学习笔记 - 最优控制Optimal Control Ch07-2 动态规划 Dynamic Programming 1. 基本概念2. 代码详解3. 简单一维案例 1. 基本概念 Richoard Bell man 最优化理论&#xff1a; An optimal policy has the …
阅读更多...
宏景-zp_options-get_org_tree-SQL注入漏洞-未公开Day漏洞复现

宏景-zp_options-get_org_tree-SQL注入漏洞-未公开Day漏洞复现

0x01阅读须知 技术文章仅供参考&#xff0c;此文所提供的信息只为网络安全人员对自己所负责的网站、服务器等&#xff08;包括但不限于&#xff09;进行检测或维护参考&#xff0c;未经授权请勿利用文章中的技术资料对任何计算机系统进行入侵操作。利用此文所提供的信息而造成的…
阅读更多...
电脑分区是使用MRB还是GPT呢？看了这篇文章，心理就有底了

电脑分区是使用MRB还是GPT呢？看了这篇文章，心理就有底了

在Windows 10或Windows 11上设置一个新磁盘&#xff0c;系统会询问你是要使用MBR&#xff08;主引导记录&#xff09;还是GPT&#xff08;GUID分区表&#xff09;。今天&#xff0c;我们将解释GPT和MBR之间的区别&#xff0c;并帮助你为PC或Mac选择合适的。 GPT带来了许多优点…
阅读更多...
最新文章

Copyright @ 2022~2023