人工智能-A*算法-八数码问题

一,A*算法设计思想

A*算法(A-star)是一种寻路算法,主要用于游戏、机器人等领域。

它的设计思想是将最短路径搜索问题转化为一个优化问题,通过计算每个节点的评分(f(n) = g(n) + h(n))来寻找最优路径。

以下是 A*算法的设计思想:

1. 引入启发式函数(h(n)):

A*算法使用一个启发式函数来估计从当前节点到目标节点的距离。

启发式函数越好,搜索速度越快。

通常情况下,启发式函数为曼哈顿距离(曼哈顿距离是指两点在网格上沿着网格线走的距离之和)。

2. 优先级队列

A*算法使用一个优先级队列(开启列表)来存储待处理的节点。

队列中的节点按照评分(f(n))从高到低排列。

这样,每次迭代都可以优先处理评分最高的节点,从而保证搜索的速度和效率。

3. 扩展节点

A*算法从当前节点开始,遍历其所有相邻节点。

对于每个相邻节点,检查它是否在关闭列表中(表示已经访问过),如果不在关闭列表中,则将其加入开启列表,并更新其父节点和评分。

4. 关闭列表

A*算法使用一个关闭列表来记录已访问过的节点。

每次扩展节点时,都需要检查新节点是否在关闭列表中。

如果在,则忽略该节点,继续处理其他相邻节点。

5. 停止条件

A*算法在找到目标节点或开启列表为空时停止搜索。

找到目标节点时,意味着找到了一条从起始节点到目标节点的最短路径。

6. 回溯法

当开启列表为空时,搜索失败。

此时,可以使用回溯法(如 Dijkstra 算法)从起始节点开始,重新寻找一条路径。

这种情况下,A*算法退化为 Dijkstra 算法。

二,题目需求

应用启发式搜索算法A 解决以下八数码问题:

初始状态:

目标状态:

 

三,代码实现

完整代码,需要下载pygame库,直接使用,运行可以查看动画演示效果。

import heapq
from copy import deepcopy
import time
import pygame


# 定义启发式函数,使用当前状态与目标状态,棋子的错位数作为估价值
def heuristic(move_state, goal_state):
    err_num = 0
    for i in range(3):
        for j in range(3):
            if move_state[i][j] != goal_state[i][j]:
                err_num += 1
    return err_num


# 根据当前状态,获取可移动方向
def get_moves(state, g):
    # 获取空缺位(或0值)坐标
    x, y = None, None
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                x, y = i, j
                break
    moves = []
    if x > 0:
        new_state = deepcopy(state)
        # 空位与它左侧1位交换,左侧数字右移
        new_state[x][y], new_state[x - 1][y] = new_state[x - 1][y], new_state[x][y]
        moves.append((new_state, g + 1))
    if x < 2:
        new_state = deepcopy(state)
        # 空位与它右侧1位交换,右侧数字左移
        new_state[x][y], new_state[x + 1][y] = new_state[x + 1][y], new_state[x][y]
        moves.append((new_state, g + 1))
    if y > 0:
        new_state = deepcopy(state)
        # 空位与它下面1位交换,下面数字上移
        new_state[x][y], new_state[x][y - 1] = new_state[x][y - 1], new_state[x][y]
        moves.append((new_state, g + 1))
    if y < 2:
        new_state = deepcopy(state)
        # 空位与它上面1位交换,上面数字下移
        new_state[x][y], new_state[x][y + 1] = new_state[x][y + 1], new_state[x][y]
        moves.append((new_state, g + 1))
    return moves


# A星算法搜索
def a_star_search(initial_state, goal_state):
    f, g, h = 0, 0, 0
    open_set = [(f, initial_state)]
    close_set = set()
    # 从哪里来字典,记录节点来源,当成父节点
    come_from = {}
    while open_set:
        f, current_state = heapq.heappop(open_set)
        if current_state == goal_state:
            data = []
            current_state = tuple(map(tuple, current_state))
            # 从目标点向起点遍历路径
            while current_state in come_from:
                # 将当前点的位置加入路径
                data.append(current_state)
                # 将当前点设为从哪里来的节点,继续向上遍历
                current_state = come_from[current_state]
            # 将起始点的位置也加入路径
            data.append(tuple(map(tuple, initial_state)))
            # 将路径反转,因为我们是从目标向起点遍历的,所以需要反转得到真正的路径
            return data[::-1]

        close_set.add(tuple(map(tuple, current_state)))
        for move, g in get_moves(current_state, g):
            if tuple(map(tuple, move)) not in close_set:
                come_from[tuple(map(tuple, move))] = tuple(map(tuple, current_state))
                h = heuristic(move, goal_state)
                f = g + h
                heapq.heappush(open_set, (f, move))
    return None


# 打印网格地图
def grid_print(grid):
    for line in grid:
        print(line)


# 定义网格矩阵长宽
map_size = (3, 3)
# 定义屏幕一个格子大小
CELL_SIZE = 200
# 定义屏幕宽高大小
WIDTH, HEIGHT = map_size[0] * CELL_SIZE, map_size[1] * CELL_SIZE

# 定义颜色
WHITE = (255, 255, 255)
RED = (255, 0, 0)
BLUE = (0, 0, 255)
BLACK = (0, 0, 0)


# 绘制主地图,棋盘数字
def draw_grid(pygame, screen, num_states):
    # 填充屏幕背景为白色
    screen.fill(WHITE)
    for i in range(0, WIDTH, CELL_SIZE):
        pygame.draw.line(screen, BLACK, (i, 0), (i, HEIGHT))
    for i in range(0, HEIGHT, CELL_SIZE):
        pygame.draw.line(screen, BLACK, (0, i), (WIDTH, i))
    # 字体
    font = pygame.font.Font(None, 48)
    for i in range(3):
        for j in range(3):
            # 数字值
            num_text = str(num_states[j][i])
            if num_text == '0':
                # 写数字
                text = font.render(num_text, True, RED)
            else:
                # 写数字
                text = font.render(num_text, True, BLUE)
            screen.blit(text, (i * CELL_SIZE + CELL_SIZE / 2, j * CELL_SIZE + CELL_SIZE / 2))


# 绘制A*算法找到的路径,动画演示
def draw_a_star_path(initial_state, goal_state):
    # 执行A*算法,寻找最优路径
    path_states = a_star_search(initial_state, goal_state)
    print("绘制网格地图和最优路径:")
    # 返回搜索路径和Open、Close表的内容
    i = 0
    for path in path_states:
        grid_print(path)
        print(f"======={i}=======")
        i += 1

    print("绘制A*算法找到的路径地图:")
    # 初始化 Pygame
    pygame.init()

    # 创建一个窗口(屏幕)对象
    screen = pygame.display.set_mode((WIDTH, HEIGHT))
    # 窗口描述
    pygame.display.set_caption("A星算法-8数码问题-动画演示")
    # 循环刷新地图,显示最优路径
    for num_states in path_states:
        # 绘制主地图,棋盘数字
        draw_grid(pygame, screen, num_states)
        # 更新显示屏幕
        pygame.display.flip()
        time.sleep(1)
    # 退出 Pygame
    pygame.quit()


if __name__ == "__main__":
    # 八数码初始状态
    initial_state = [
        [2, 8, 3],
        [1, 6, 0],
        [7, 5, 4]
    ]

    # 八数码最终状态
    goal_state = [
        [1, 2, 3],
        [8, 0, 4],
        [7, 6, 5]
    ]
    # 绘制A*算法找到的路径,动画演示
    draw_a_star_path(initial_state, goal_state)

四,运行动画效果

 ==========结束==========

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

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

相关文章

YOLOv8-Seg改进:简单高效的模块-现代反向残差移动模块 (iRMB) | | ICCV2023 EMO

🚀🚀🚀本文改进:设计了一种面向移动端应用的简单而高效的现代反向残差移动模块 (Inverted Residual Mobile Block, iRMB),它吸收了类似 CNN 的效率来模拟短距离依赖和类似 Transformer 的动态建模能力来学习长距离交互,引入YOLOV8 🚀🚀🚀YOLOv8-seg创新专栏:h…

【华为OD题库-064】最小传输时延I-java

题目 某通信网络中有N个网络结点&#xff0c;用1到N进行标识。网络通过一个有向无环图.表示,其中图的边的值表示结点之间的消息传递时延。 现给定相连节点之间的时延列表times[]{u&#xff0c;v&#xff0c; w)&#xff0c;其中u表示源结点&#xff0c;v表示目的结点&#xff0…

小程序长按识别二维码

小程序开发中要实现长按识别二维码的功能很简单&#xff0c;只需要在image标签里添加如下属性即可&#xff1a; 小程序版本&#xff1a; show-menu-by-longpress"{{true}}" uniapp版本&#xff1a; :show-menu-by-longpress"true" 举例&#xff1a; …

金融银行业更适合申请哪种SSL证书?

在当今数字化时代&#xff0c;金融行业的重要性日益增加。越来越多的金融交易和敏感信息在线进行&#xff0c;金融银行机构必须采取必要的措施来保护客户数据的安全。SSL证书作为一种重要的安全技术工具&#xff0c;可以帮助金融银行机构加密数据传输&#xff0c;验证网站身份&…

网页文章采集工具-人工智能AI功能

简数采集器是一款支持人工智能AI功能的网页文章采集工具&#xff0c;它可以调用百度的文心一言AI对采集的数据进行分析&#xff0c;处理&#xff0c;内容创作等等&#xff0c;根据你的需求进行更加灵活的数据采集和处理。 文心一言人工智能AI功能使用方法&#xff1a; 1. 填写…

什么是Overlay网络?Overlay网络与Underlay网络有什么区别?

你们好&#xff0c;我的网工朋友。 在传统历史阶段&#xff0c;数据中心的网络是以三层架构&#xff08;核心、汇聚、接入&#xff09;为基本标准。 但是随着技术的发展&#xff0c;不同的厂家有不同的组建方式&#xff0c;比如说在核心层、汇聚层和接入层增加虚拟化技术。 …

MySQL笔记-第05章_排序与分页

视频链接&#xff1a;【MySQL数据库入门到大牛&#xff0c;mysql安装到优化&#xff0c;百科全书级&#xff0c;全网天花板】 文章目录 第05章_排序与分页1. 排序数据1.1 排序规则1.2 单列排序1.3 多列排序 2. 分页2.1 背景2.2 实现规则2.3 拓展 第05章_排序与分页 讲师&#…

Allegro无法模块复用的解决办法

Allegro无法模块复用的解决办法 在用Allegro做PCB设计的时候,模块复用是使用的比较频繁的功能,对于有相同模块的单板,可以节省大量的时间。 模块复用的功能不细说,具体参考以前的文章。 有时会遇到模块复用的时候出现如下报错 无法匹配,有时如果因为Device而无法复用,就…

学习pytorch16 现有网络模型的使用和修改

现有网络模型的使用和修改 官网 [https://pytorch.org/](https://pytorch.org/)torchvison 相关model1. 图像常用vgg16模型 【vgg19也常用】2. ImageNet数据集太大 无法代码下载 kaggle网址下载3. 代码4. 执行结果 官网 https://pytorch.org/ torchvison 相关model 1. 图像常用…

Android wifi 框架以及Enable流程

Android P相比于Android O的变化 多了WifiStateMachinePrime&#xff08;状态机的前处理机制&#xff09;&#xff0c;wifiService的相关cmd 不再是直接send 给WifiStateMachine&#xff0c;而是被送到WifiStateMachinePrime先进行处理后&#xff0c;再送往WifiStateMachine也…

Linux Namespace技术

对应到容器技术&#xff0c;为了隔离不同类型的资源&#xff0c;Linux 内核里面实现了以下几种不同类型的 namespace。 UTS&#xff0c;对应的宏为 CLONE_NEWUTS&#xff0c;表示不同的 namespace 可以配置不同的 hostname。User&#xff0c;对应的宏为 CLONE_NEWUSER&#xf…

Redis Hash数据类型

Redis Hash数据类型 几乎所有的主流编程语言都提供了哈希(hash)类型&#xff0c;它们的叫法可能是哈希、字典、关联数组、映射。在 Redis 中&#xff0c;哈希类型是指值本身又是一个键值对结构&#xff0c;形如key “key”&#xff0c;value {ffield1, value1 }, … {fieldN…

HTTP 缓存机制

一、强制缓存 只要浏览器判断缓存没有过期&#xff0c;则直接使用浏览器的本地缓存而无需再请求服务器。 强制缓存是利用下面这两个 HTTP 响应头部&#xff08;Response Header&#xff09;字段实现的&#xff0c;它们都用来表示资源在客户端缓存的有效期&#xff1a; Cache…

对抗神经网络 CGAN实战详解 完整数据代码可直接运行

代码视频讲解: 中文核心项目:对抗神经网络 CGAN实战详解 完整代码数据可直接运行_哔哩哔哩_bilibili 运行图: 完整代码: from keras.layers import Input, Dense, Reshape, Flatten, Dropout, multiply from keras.layers import BatchNormalization, Activation, Embedd…

单片机系统

我们来看单片机 的例子&#xff0c;读者可能会担心单片机&#xff08;又称MCU&#xff0c;或微控制器&#xff09; 过于专业而无法理解。完全没必要&#xff01;在这里我们仅借它谈论一下有关时间的话题&#xff0c;顺带提一下单片机系统的概念。 单片机顾名思义是集成到一个芯…

Java开发中一些重要软件安装配置

Java技术栈中重要过程 1、JavaWeb1、开发工具VsCode的安装和使用2、Tomcat服务器3、nodejs的简介和安装4、Vite创建Vue3工程化项目ViteVue3项目的创建、启动、停止ViteVue3项目的目录结构 5、Maven安装和配置 1、JavaWeb 1、开发工具VsCode的安装和使用 1 安装过程 安装过程比…

IDEA插件:Apipost-Helper

Apipost-Helper是由Apipost推出的IDEA插件&#xff0c;写完接口可以进行快速调试&#xff0c;且支持搜索接口、根据method跳转接口&#xff0c;还支持生成标准的API文档&#xff0c;注意&#xff1a;这些操作都可以在代码编辑器内独立完成&#xff0c;非常好用&#xff01;这里…

RocketMQ Copilot 一款面向 Apache RocketMQ 的智能辅助运维系统

一、RocketMQ简介 ocketMQ是阿里巴巴研发的一款分布式消息中间件&#xff0c;后开源给Apache基金会&#xff0c;成为apache的顶级开源项目。它具有高性能、高可靠、高实时和分布式的特点。RocketMQ主要应用于解决应用耦合&#xff0c;消息分发&#xff0c;流量削锋等问题。 R…

Python神器:快速删除文本文件中指定行的方法

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com 1. 简介 文件操作是编程中的重要方面。Python作为强大的编程语言&#xff0c;提供了处理文件的能力。删除特定行是文件处理中常见的需求。 2. 打开文件和读取内容 当打开文件并读取其内容时&#xff0c;open(…

全球与中国仿制药市场:增长趋势、竞争格局与前景展望

仿制药是指在剂型、功效、给药方法、品质、性能特征、用途等方面与原厂药相似并已获得原厂药上市许可的药品。仿制药的价格低于品牌药。糖尿病、癌症和心血管疾病等慢性疾病的快速成长推动了仿制药市场的成长。此外&#xff0c;仿制药的实惠价格以及最新产品的批准和推出也有助…