头歌——人工智能(搜索策略)
文章目录
- 第1关:搜索策略
- 第2关:盲目搜索
- 第3关:启发式搜索 - 扫地机器人最短路径搜索
- 第4关:搜索算法应用 - 四皇后问题
第1关:搜索策略
什么是搜索技术
人类的思维过程可以看作是一个搜索过程。从小学到现在,你一定遇到过很多智力游戏问题,如传教士和野人问题:有 3 个传教士和 3 个野人来到河边准备过河,河边有一条船,每次最多坐 2 人。但是任何时刻在河的两边以及船上的野人数量不能超过传教士的数量,不然传教士就会被吃掉。
如果让你来玩这个智力游戏,在每一次过河之后都会有几种过河方案供你选择,到底哪种方案才有利于在满足题目所规定的约束条件下顺利过河?这就是搜索问题。
经过反复努力和试探,你终于找到了一种解决办法。在高兴之余,你可能马上又会想到这个方案所用的步骤是否最少?也就是说它是最优的吗?如果不是,如何才能找到最优方案?在计算机上又如何实现这样的搜索?这些问题就是本关要介绍的搜索问题,而求解这类搜索问题的技术称之为搜索技术。
第2关:盲目搜索
编程要求
根据提示,在右侧编辑器补充代码,完成 PlayMazz 函数,实现在迷宫里从起点走到出口的功能。其中:
mazz :表示迷宫,类型为字典;
start :表示起点,类型为字符;
end :表示出口,类型为字符。
测试说明
您只需完成 PlayMazz 函数中的 Begin-End 段即可,平台会对你编写的代码进行测试。其中测试输入为字典的形式,其中 mazz 部分表示迷宫,start 部分表示迷宫起点,end 部分表示迷宫出口。
测试输入:{mazz:{A: [B, C],B: [D, E],C: [F],F: [G, H],D: [],E: [],G: [],H: []},start:A,end:D}
预期输出:ABCD
开始你的任务吧,祝你成功!
def PlayMazz(mazz, start, end):'''走迷宫,从start走到end:param mazz: 迷宫:param start: 迷宫的起点:param end: 迷宫的出口:vertex: 迷宫中正在进行广度优先搜索算法的当前位置'''# queue为队列,当队列为空或者当前地点为H时搜索结束visited, queue = set(), [start]while queue:# 从队列中出队,即当前所处的地点vertex = queue.pop(0)if vertex not in visited:visited.add(vertex)print(vertex, end='')#********* Begin *********## 当走到出口时结束算法if vertex == end:break#********* End *********##********* Begin *********## 将当前所处地点所能走到的地点放入队列for v in mazz[vertex]:if v not in visited:queue.append(v)#********* End *********#
第3关:启发式搜索 - 扫地机器人最短路径搜索
编程要求
在右侧编辑器补充代码,完成 A_star 函数,实现从 start 走到 end 的自动寻路功能。其中:
map :表示地图。
start :表示出发地,类型为列表,如 [1,2] 表示出发地为地图中的第 1 行第 2 列的方块。
end :表示目的地,类型为列表,如 [1,2] 表示目的地为地图中的第 1 行第 2 列的方块。
测试说明
您只需完成 A_star 函数中的 Begin-End 段即可,平台会对你编写的代码进行测试,并将您寻找到的路径打印出来。其中测试输入为字典的形式,其中 map_size 部分表示地图的长和宽, start 部分表示出发地的坐标, end 部分表示目的地的坐标, obstacleList 部分表示障碍物坐标的列表。
测试输入:
{‘map_size’:[10, 10], ‘start’:[1, 2], ‘end’:[6, 7], ‘obstacleList’:[[1, 1], [2, 1], [3, 1], [4, 3], [1, 3], [2, 3], [3, 3], [0, 1], [5, 1], [5, 3]]}
预期输出:
start->(1,4)->(2,5)->(3,6)->(4,7)->(5,8)->(6,8)->end
开始你的任务吧,祝你成功!
from a_star_utils import Nodedef A_star(map, mapSize, start, end):'''A*算法,从start走到end:param map:地图:param mapSize:地图大小,例如[10,10]表示地图长10宽10:param start:表示出发地,类型为列表,如[1,2]表示出发地为地图中的第1行第2列的方块:param end:表示目的地,类型为列表,如[1,2]表示目的地为地图中的第1行第2列的方块:return:从出发地到目的地的路径'''openedList = []closedList = []#********* Begin *********## 获得出发地方块的信息,并将信息保存为 node 变量startNode = map[start[0]][start[1]]startNode.distanceFromOri = 0startNode.allDistance = startNode.distanceFromOri + startNode.distanceFromDesstartNode.parent = Nonenode = startNode # 将当前方块保存为 node 变量#********* End *********##********* Begin *********## 将当前方块存到开启列表中openedList.append(node)node.added = True#********* End *********#while len(openedList) != 0:# 从开启列表中取出F值最小的节点node = openedList.pop(0)node.closed = True# 如果当前节点是终点,结束搜索并回溯路径if node.y == end[0] and node.x == end[1]:finalPath = []while node is not None:finalPath.append(node)node = node.parentfinalPath.reverse()return finalPath# 开始检查邻居节点neighboursList = []y, x = node.y, node.xparentDistanceFromOri = node.distanceFromOri# 寻找周围的邻居节点(上下左右斜向)for dy in (y + 1, y, y - 1):if dy < 0 or dy >= mapSize[0]:continuefor dx in (x + 1, x, x - 1):if dx < 0 or dx >= mapSize[1]:continueneedNode = map[dy][dx]# 跳过障碍物或已处理过的节点if needNode.unable or needNode.closed or needNode.added:continue# 计算距离代价if abs(dy - y) + abs(dx - x) == 1: # 直线代价distanceFromOri = parentDistanceFromOri + 1else: # 对角线代价distanceFromOri = parentDistanceFromOri + 1.4# 更新邻居节点的G值(距离起点的代价)if needNode in neighboursList:if distanceFromOri < needNode.distanceFromOri:needNode.distanceFromOri = distanceFromOrielse:needNode.distanceFromOri = distanceFromOrineighboursList.append(needNode)# 处理每个邻居节点,计算F值并加入开启列表for needNode in neighboursList:needNode.parent = node# 计算F值needNode.allDistance = needNode.distanceFromOri + needNode.distanceFromDesneedNode.added = TrueopenedList.append(needNode)# 将开启列表按照F值进行排序,F值小的优先处理openedList.sort(key=lambda x: x.allDistance)return None
第4关:搜索算法应用 - 四皇后问题
任务描述
本关任务:编写一个能求解四皇后问题的 Python 程序。
相关知识
为了完成本关任务,你需要掌握四皇后问题。
四皇后问题
在 n 行 n 列的国际象棋上摆放 n 个皇后,使其不能互相攻击(即任意两个皇后都不能处于同一行、同一列或同一斜线上)。请问有多少种摆法,以及如何摆放这些皇后。这就是经典的 n 皇后问题。如下图所示:
编程要求
根据提示,在右侧编辑器补充代码,完成 FourQueens 函数,实现找出所有可能的皇后摆法。其中:
mark :表示皇后的位置信息,例如 [0,1,3,2] 表示棋盘的第 1 行第 1 列,第 2 行第 2 列,第 3 行第 4 列,第 4 行第 3 列放置了皇后。例如 [1, None, None, None] 表示第 1 行第 2 列放置了皇后,其他行没有放置皇后。
cur :表示当前准备在第几行放置皇后,例如 cur=1 时,表示准备在第 2 行放置皇后。
result :表示存放皇后摆放结果的列表,类型为二维 list。
测试说明
您只需完成 FourQueens 函数中的 Begin-End 段即可,平台会对你编写的代码进行测试,并将所有皇后的摆放方式打印出来。
预期输出:
XQXX
XXXQ
QXXX
XXQX
XXQX
QXXX
XXXQ
XQXX
开始你的任务吧,祝你成功!
def make(mark):'''标记皇后的位置,例如mark[0] = 2, 表示第1行皇后放在第3列的位置:param mark: 皇后的位置信息:return: 拼接好的结果'''#初始化数组r = [['X' for _ in range(len(mark))] for _ in range(len(mark))]#将每一行中皇后的位置用‘Q’代替for i in range(len(mark)):r[i][mark[i]] = 'Q'#枚举,将原来散的元素连接成字符串for k, v in enumerate(r):r[k] = ''.join(v)return rdef FourQueens(mark, cur, ret):'''深度优先搜索的方式求解四皇后问题:param mark:表示皇后的位置信息,例如[0,1,3,2]表示棋盘的第1行第1列,第2行第2列,第3行第4列,第4行第3列放置了皇后。例如[1, None, None, None]表示第1行第2列放置了皇后,其他行没有放置皇后。初始值为[None,None,None,None]:param cur:表示当前准备在第几行放置皇后,例如`cur=1`时,表示准备在第`2`行放置皇后。初始值为0:param ret:表示存放皇后摆放结果的列表,类型为列表。初始值为[]:return:无'''if cur == len(mark):#********* Begin *********## 如果当前行是最后一行,记录一个解,并返回结束此次搜索ret.append(make(mark))return#********* End *********##试探处理,将当前行的皇后应该在的位置遍历每一列,如果满足条件,递归调用处理下一行for i in range(len(mark)):mark[cur], down = i, Truefor j in range(cur):# 当想在当前位置放皇后会与其他皇后冲突时不放置皇后if mark[j] == i or abs(i-mark[j]) == cur - j:down = Falsebreakif down:# 准备在下一行找能放置皇后的位置FourQueens(mark, cur+1, ret)
相关文章:

头歌——人工智能(搜索策略)
文章目录 第1关:搜索策略第2关:盲目搜索第3关:启发式搜索 - 扫地机器人最短路径搜索第4关:搜索算法应用 - 四皇后问题 第1关:搜索策略 什么是搜索技术 人类的思维过程可以看作是一个搜索过程。从小学到现在࿰…...

gorm.io/sharding改造:赋能单表,灵活支持多分表策略(下)
背景 分表组件改造的背景,我在这篇文章《gorm.io/sharding改造:赋能单表,灵活支持多分表策略(上)》中已经做了详细的介绍——这个组件不支持单表多个分表策略,为了突破这个限制做的改造。 在上一篇文章中&…...

域渗透AD渗透攻击利用 MS14-068漏洞利用过程 以及域渗透中票据是什么 如何利用
目录 wmi协议远程执行 ptt票据传递使用 命令传递方式 明文口令传递 hash口令传递 票据分类 kerberos认证的简述流程 PTT攻击的过程 MS14-068 漏洞 执行过程 wmi协议远程执行 wmi服务是比smb服务高级一些的,在日志中是找不到痕迹的,但是这个主…...

C++进阶-->继承(inheritance)
1. 继承的概念及定义 1.1 继承的概念 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要手段,他允许我们在保证原有类的特性基础上还进行扩展,通过继承产生的类叫做派生类(子类),被继承的类叫做基类&a…...

可视化项目 gis 资源复用思路(cesium)
文章目录 可视化项目 gis 资源复用思路底图、模型替换思路具体操作 可视化项目 gis 资源复用思路 背景: A项目的底图、模型 是现在在做的 B项目所需要的,现在要把 B项目的底图之类的替换成 A系统的 底图、模型替换思路 观察可访问系统的 gis 相关网络请…...

SQL实战测试
SQL实战测试 (请写下 SQL 查询语句,不需要展示结果) 表 a DateSalesCustomerRevenue2019/1/1张三A102019/1/5张三A18 1. **用一条 ** SQL 语句写出每个月,每个销售有多少个客户收入多少 输出结果表头为“月”,“销…...
Java 基础教学:基础语法-变量与常量
变量 变量是程序设计中的基本概念,它用于存储信息,这些信息可以在程序执行过程中被读取和修改。 变量的声明 在Java中,声明变量需要指定变量的数据类型以及变量的名称。数据类型定义了变量可以存储的数据种类(例如整数、浮点数…...

vue3使用element-plus手动更改url后is-active和菜单的focus颜色不同步问题
在实习,给了个需求做个新的ui界面,遇到了一个非常烦人的问题 如下,手动修改url时,is-active和focus颜色不同步 虽然可以直接让el-menu-item:focus为白色能解决这个问题,但是我就是想要有颜色哈哈哈,有些执…...
每天五分钟深度学习框架pytorch:从底层实现一元线性回归模型
本文重点 本节课程我们继续搭建一元线性回归模型,不同的是这里我们不使用pytorch框架已经封装好的一些东西,我们做这个目的是为了更加清楚的看到pytorch搭建模型的本质,为了更好的理解,当然实际中我们还是使用pytorch封装好的一些东西,不要重复造轮子。 模型搭建 #定义…...
编辑器加载与AB包加载组合
解释: 这个 ABResMgr 类是一个资源加载管理器,它用于整合 AB包(Asset Bundle)资源加载和 编辑器模式资源加载。通过这个管理器,可以根据开发环境选择资源加载方式,既支持 运行时使用Asset Bundle加载&…...
【c++】vector中的back()函数
nums.back() 是 C 中 std::vector 类的一个成员函数,用于获取数组(向量)中的最后一个元素。以下是一些关于 nums.back() 的详细解释和示例使用: 1. 功能 nums.back() 返回数组 nums 中的最后一个元素。如果数组为空,…...

[分享] SQL在线编辑工具(好用)
在线SQL编写工具(无广告) - 在线SQL编写工具 - Web SQL - SQL在线编辑格式化 - WGCLOUD...
element-ui隐藏表单必填星号
// 必填星号在前显示 去掉 .el-form-item.is-required:not(.is-no-asterisk) > .el-form-item__label:before { content: !important; margin-right: 0px!important; } // 必填星号在结尾显示 .el-form-item.is-required:not(.is-no-asterisk) > .el-form-item__labe…...

自动驾驶系列—激光雷达点云数据在自动驾驶场景中的深度应用
🌟🌟 欢迎来到我的技术小筑,一个专为技术探索者打造的交流空间。在这里,我们不仅分享代码的智慧,还探讨技术的深度与广度。无论您是资深开发者还是技术新手,这里都有一片属于您的天空。让我们在知识的海洋中…...
C#删除dataGridView 选中行
关键在于:从最后一行开始删除。 从前往后删只能删除其中一半,我理解是再remove行的时候dataGridView内部行序列发生了变化,包含在选中行中的特定行会被忽略,从后往前删就可避免这个问题,最后一行的行号影响不到前面的…...

K8S调度不平衡问题分析过程和解决方案
不平衡问题排查 问题描述: 1、业务部署大量pod(据反馈,基本为任务型进程)过程中,k8s node内存使用率表现不均衡,范围从80%到百分之几; 2、单个node内存使用率超过95%,仍未发生pod驱逐,存在node…...

Python中类、继承和方法重写的使用
😀前言 本篇博文将介绍如何定义类、创建类的实例、访问类的成员、使用属性、实现继承及方法重写,希望你能够喜欢 🏠个人主页:晨犀主页 🧑个人简介:大家好,我是晨犀,希望我的文章可以…...

【Neo4j】- 轻松入门图数据库
文章目录 前言-场景一、Neo4j概述二、软件安装部署1.软件下载2.软件部署3.软件使用4.语法学习 总结 前言-场景 这里用大家都了解的关系数据与图数据据库对比着说,更加方便大家理解图数据库的作用 图形数据库和关系数据库均存储信息并表示数据之间的关系。但是,关系…...
LeetCode 206 - 反转链表
解题思路 我们可以使用迭代的方法来实现链表的反转,这里我们先介绍迭代的方法。迭代的思路是:从头节点开始,依次将节点的next指针进行反转,使得当前节点的next指向其前一个节点,然后依次向后移动指针,直至…...

AI生成大片,Movie Gen 可以生成长视频并配上完美的音效,带给观众更好的观看体验。
之前的文章中已经给大家介绍了一些关于长视频生成相关的技术,AI生成大片已经越来越近了。感兴趣的小伙伴可以点击下面链接阅读~ Movie Gen 的工作原理可以简单理解为两个主要部分:一个是生成视频的模型,另一个是生成音频的模型。首先&#x…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...