人工智能(Educoder)-- 搜索技术 -- 盲目式搜索

第1关:盲目搜索之宽度优先搜索算法

任务描述

本关任务:给定迷宫地图以及在迷宫中的起始位置,利用宽度优先搜索算法求解走出迷宫的最短路径长度,走出迷宫意味着达到迷宫地图的边界(所有位置下标0开始)。

例如以下4×4地图中,0表示墙,1表示可行走的路,起始位置为(2,1),则走出迷宫的一条最短路径为(2,1)→(2,0),步长为1。

  1. 0 1 0 1
  2. 0 1 1 1
  3. 1 1 0 0
  4. 0 1 0 1

相关知识

为了完成本关任务,你需要掌握:1.宽度优先搜索,2.一致代价搜索,3.求解思路。

宽度优先搜索

宽度优先搜索 Breadth-First-Search 是一种简单的搜索策略,首先扩展根结点,接着扩展根结点的所有后继结点,然后再扩展它们的后继,以此类推。一般地,在下一层的任何结点扩展之前,搜索树上本层深度的所有节点都应该被扩展过。示例如下:

宽度优先搜索每次总是扩展深度最浅的结点,这可以通过先进先出队列 FIFO, First In First Out 来实现,也就是将新结点添加到队列尾部,这也意味着浅层的老结点会在深层结点之前被扩展。算法伪代码如下:

一致代价搜索

宽度优先搜索是每一步的行动代价一致的搜索策略,因为它总是扩展深度最浅的未扩展节点。当单步代价不一致时,宽度优先搜索则不是最优的搜索策略。一致代价搜索 Uniform-Cost-Search 扩展的是路径消耗g(n)最小的节点n,通过将边缘结点按g值排序的优先队列实现,因此可以很好的解决单步代价不一致的问题。算法伪代码如下:

求解思路

设迷宫地图中的起点为(x,y),并以该点为根结点,上下左右四个相连的点为后继结点,由此构建一棵4叉树,然后从根结点开始层次遍历,最先达到边界的合法路径的步长即为答案。

编程要求

本关的编程任务是补全右侧代码片段 solveMaze 中 Begin 至 End 中间的代码,具体要求如下:

  • 在 solveMaze 中,利用宽度优先搜索算法,求解走出迷宫的最短步数,并返回结果(无解返回 0 )。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入: 4 4 0 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 2 1

预期输出: 1

输入格式: 第 1 行:n 行 m 列,1<=n,m<=10 第 2~n+1 行:迷宫地图 第 n+2 行:起点(x,y),地图左上是(0,0),右下是(n-1,m-1) 输出格式: 最短步数(无解输出 0 )

代码
 

# -*- coding:utf-8 -*-

class Maze:
    def __init__(self, map, n, m, x, y):
        self.ans = 0            #最短步长结果
        self.map = map          #迷宫地图map[0,n-1][0,m-1](下标0开始)
        self.n = n              #迷宫地图行数n
        self.m = m              #迷宫地图列数m
        self.x = x              #起点,行坐标(下标0开始)
        self.y = y              #起点,列坐标(下标0开始)

class Solution:

    def solveMaze(self, maze):
        """求解迷宫问题
        :type: maze: class Maze #迷宫的数据结构类
        :rtype: maze.ans: int   #返回最短路径长度
        """

        minpath=[]  # 存储最短路径长度的列表
        dir=[[1,0],[-1,0],[0,-1],[0,1]]  # 上下左右四个方向
        row=maze.n  # 迷宫的行数
        clm=maze.m  # 迷宫的列数
        sx=maze.x  # 起点的行坐标
        sy=maze.y  # 起点的列坐标
        vis=[[False for i in range(clm+1)] for i in range(row+1)]  # 记录每个位置是否已经访问过
        queue=[(sx,sy,0)]  # 初始化队列,存储当前位置和步数
        vis[sx][sy]=True  # 标记起点已访问
        while  queue:  # 当队列不为空时循环
            t=queue.pop()  # 弹出队首元素
            tx=t[0]  # 当前位置的行坐标
            ty=t[1]  # 当前位置的列坐标
            ans=t[2]  # 当前步数
            for i in range(4):  # 遍历上下左右四个方向
                if 0<=tx+dir[i][0]<row and 0<=ty+dir[i][1]<clm:  # 如果新位置在迷宫内
                    dx,dy=tx+dir[i][0],ty+dir[i][1]  # 计算新位置的坐标
                    if not vis[dx][dy] and maze.map[dx][dy]:  # 如果新位置未访问且可通行
                        queue.append((dx,dy,ans+1))  # 将新位置和步数加入队列
                        vis[dx][dy]=True  # 标记新位置已访问
                        if dx==0 or dx==row-1 or dy==0 or dy==clm-1:  # 如果新位置在迷宫边界上
                            minpath.append(ans+1)  # 将当前步数加入最短路径列表
        if minpath:return min(minpath)  # 如果最短路径列表不为空,返回最小值
        else:  return 0  # 如果最短路径列表为空,返回0

第2关:盲目搜索之深度优先搜索算法

任务描述

本关任务:利用深度优先搜索算法的核心思想,求解N皇后问题的方案总数,其中N∈[1,10]。

N皇后问题是国际象棋的扩展,在N×N的棋盘上放置N个皇后,使得每一个皇后都不会攻击到其余的任一皇后(皇后可以攻击和它在同一行、同一列或同一对角线上的任何棋子)。

相关知识

为了完成本关任务,你需要掌握:1.深度优先搜索算法,2.深度受限搜索,3.迭代加深的深度优先搜索,4.求解思路。

深度优先搜索算法

深度优先搜索 Depth-First-Search 总是扩展搜索树的当前边缘结点中最深的节点。搜索很快的推进到搜索树的最深处的结点,该结点称之为叶子结点,它没有后继,当这些结点扩展完之后,就从边缘结点中去掉,然后回溯到下一个未扩展后继的深度稍浅的结点,搜索过程如下图所示。

与宽度优先搜索使用 FIFO 队列不同,深度优先搜索使用 LIFO, Last In First Out 的队列结构,即最新生成的结点最早被选择扩展,因此,为了实现方便,深度优先搜索算法一般抛弃 LIFO 队列而采用递归式结构实现。

深度受限搜索

在无限状态空间里,深度优先搜索可能会陷入无解的分支里跳不出来。深度受限搜索 Depth-Limited-Search 通过设置一个深度界限l来避免此问题,即深度为l的结点被当做为没有后继的叶子结点。

虽然深度界限解决了无穷路径的问题,但是该算法是不完备的。假设正确解在深度为d的结点,若设置的l小于d,则目标结点的深度超过了深度限制,那么该算法无法得到目标解,若设置的l大于d,深度受限搜索则不是最优的。深度优先搜索可以看作是特殊的深度受限搜索,其受限深度l=∞。

迭代加深的深度优先搜索

迭代加深的深度优先搜索 Iterative-Deepening-Search 结合了深度受限搜索,它不断的增大深度限制,首先是l=0,接着为1,然后为2,以此类推,直到找到目标解,即当深度界限达到d时,最浅的目标结点被找到。迭代加深的深度优先搜索结合了深度优先搜索和宽度优先搜索的优点。

求解思路

N皇后问题是一个典型的有限的树搜索空间求解问题。用增量形式化方法描述为:

  • 状态:棋盘上 0-N 个皇后的任一摆放都是一个状态;
  • 初始状态:NxN 的棋盘上没有皇后;
  • 行动:在棋盘上的任一空格摆放一个皇后;
  • 转移模型:将增加了一个皇后的棋盘返回;
  • 目标测试:N 个皇后都在棋盘上,并且无法互相攻击。

以 8 皇后为例,这种形式化方法需要验证64×63×⋯×57个棋盘状态序列,即使在行动中增加皇后摆放的限制,棋盘状态序列的数量仍然是巨大的。

设棋盘某一位置为(i,j),将第i+1行的N个空格位置都作为(i,j)的后继结点,那么N×N的棋盘则可以通过一个根结点连接为一棵N叉搜索树,棋盘第i行对应搜索树深度为i的结点层,树的根结点到叶子节点的路径序列就是一个棋盘的状态序列,应用深度优先搜索算法可以非常方便的求解。

考虑到皇后的属性,可以增加一些限制条件来加快深度优先搜索的过程,剪掉一些无解的搜索路径。对问题具体分析如下:

  • 每一行只能放置一个皇后,那么对这一行其余的结点就不需要放置皇后了,也就是上面的建树过程,只以下一行棋盘空格作为后继结点,忽略本行其余空格;

  • 每一列只能放置一个皇后,下次搜索时就不要搜索已经放置过皇后的列了;

  • 每一斜对角线只能放置一个皇后。

棋盘的行可以用树的深度来表达,因此每一行只有一个皇后,她们不会同行。棋盘的列可以用一个长度为N的一维数组来记录是否放置过皇后。观察棋盘的行和列的特点,可以发现如下规律:

  1. 列的索引减去行的索引: 列的索引加上行的索引:
  2. 0 1 2 3 4 ... 0 1 2 3 4 ...
  3. -1 0 1 2 3 ... 1 2 3 4 5 ...
  4. -2 -1 0 1 2 ... 2 3 4 5 6 ...
  5. -3 -2 -1 0 1 ... 3 4 5 6 7 ...
  6. -4 -3 -2 -1 0 ... 4 5 6 7 8 ...
  7. ... ... ... ... ... ... ... ... ...

棋盘的左斜线\可以用一个数字表达,因此所有的左斜线可以用一个长度为2N−1的一维数组来记录是否放置过皇后,同理,右斜线/也可以用一个长度为2N−1的一维数组来记录是否放置过皇后。

编程要求

本关的编程任务是补全右侧代码片段 solveNQueens 和 DFS 中 Begin 至 End 中间的代码,具体要求如下:

  • 在 solveNQueens 中,利用 DFS 函数实现N皇后问题求解,并返回方案总数;

  • 在 DFS 中,利用深度优先搜索算法的思想,递归求解N皇后问题。

测试说明

平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

以下是平台的测试样例:

测试输入:1

预期输出:1

输入格式:整数,表示皇后数量。

输出格式:整数,表示N皇后放置方案总数。

代码

# -*- coding:utf-8 -*-

class Solution:

    def __init__(self, n=0):
        self.vis = [[]]             #用于标记是否存在皇后的二维列表(初始值全为0)
        self.ans = 0                #用于存储答案(N皇后方案数,初始值0)
        self.n = n                  #用于存储皇后数量n

    def solveNQueens(self):
        """求解N皇后问题(调用self.DFS函数)
        :rtype: self.ans: int    #返回N皇后放置方案数
        """

        #请在这里补充代码,完成本关任务
        #********** Begin **********#
         # 产生一个3行50列的数组,第一行代表左斜线,第二行代表所在的列,第三行代表有索引,初始值都为0
        self.vis = [[0 for j in range(50)] for i in range(3)]
        self.DFS(1,self.n)  # 递归
        return self.ans
        #********** End **********#

    def DFS(self, row, n):
        """深度优先搜索N皇后问题的解空间
        :type: row: int      #NxN棋盘的第row行
        :type: n: int        #皇后数量n
        :rtype: None         #无返回值
        """

        #请在这里补充代码,完成本关任务
        #********** Begin **********#
        if row == n+1:   # 行数大于皇后的个数,说明这个方案可行,方案数加1,递归结束(递归结束条件),
            self.ans += 1
            return
        for i in range(1,n+1,1):
            # vis[0][row-i+n] == 0 row-i即行的索引减去列的索引,左斜线等于0,左斜线没有放置皇后,+n是为了防止产生负数
            # vis[1][i] == 0 第i列为0
            # vis[2][row+i] == 0  即所在的右斜线上并没有存放皇后,row+i即行索引加上列索引,同一右斜线的行索引加列索引所得的值相等。
            if self.vis[0][row-i+n] == 0 and self.vis[1][i] == 0 and self.vis[2][row+i] == 0: # 第row行第i列可以存放皇后
                self.vis[0][row-i+n] = self.vis[1][i] = self.vis[2][row+i] = 1  # 将对应的列,左斜线、右斜线都置为1
                self.DFS(row+1,n)  # 存放下一个皇后
                # 如果下一个皇后的位置无法正确放置,则调整当前皇后的放置位置
                self.vis[0][row-i+n] = self.vis[1][i] = self.vis[2][row+i] = 0
                # 继续本次循环,知道找到本行的列中有合适的存放位置为止,如果本行无合适位置,则继续返回上一层

        #********** End **********#

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

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

相关文章

安卓工控一体机主板定制_联发科MTK平台解决方案

新移科技安卓工控一体机方案基于MT8766主芯片&#xff0c;采用四核 Cortex-A53 CPU&#xff0c;搭载Android 12.0系统&#xff0c;主频高达2.0GHz&#xff0c;具有低功耗和高性价比的优势。搭载ARM IMG GE8300 高性能GPU和4G全网通版本的RF&#xff0c;网络连接稳定快速。 可直…

Linux调试器-gdb

一、背景 程序的发布方式有两种&#xff0c;debug模式和release模式 debug模式&#xff1a;编译器形成可执行程序的时候会给可执行程序添加调试信息 程序员调试时使用debug模式&#xff0c;而release模式用于测试 而gcc/g默认编译&#xff0c;采用release模式 用gcc/g使用…

智能建筑:基于IT的集成和融合解决方案

智能建筑( Intelligent Building) 定义: 以建筑为平台,兼备建筑设备、办公自动化及通信网络系统,集结构、系统、服务、管理及它们之间的最优化组合,向人们提供一个安全、高效、舒适、便利的建筑环境。 智能建筑的发展历史: -产生:1984年世界上第一座智能大厦诞生于美国…

基于yolov8安全帽检测的系统

基于yolov8安全帽检测的系统 项目描述&#xff1a; 安全头盔检测&#xff08;计算机视觉&#xff09; 1.自训练数据集1538张数据图片&#xff0c;进行标注&#xff0c;并进行100轮的训练&#xff0c;准确率达0.966 2.使用 Flask 和 Ultralytics YOLOv8 模型开发了一个 Web 应…

【开发环境搭建篇】NodeJS的安装和配置

作者介绍&#xff1a;本人笔名姑苏老陈&#xff0c;从事JAVA开发工作十多年了&#xff0c;带过大学刚毕业的实习生&#xff0c;也带过技术团队。最近有个朋友的表弟&#xff0c;马上要大学毕业了&#xff0c;想从事JAVA开发工作&#xff0c;但不知道从何处入手。于是&#xff0…

C++ STL-string 类使用超详解

目录 0. 引言 1. string 类 1.1 string类的基本概念 1.2 string类与char*的区别 1.3 string类的作用 2. string 的接口使用 2.1 string 类对象的默认成员函数 2.1.1 构造函数 - 初始化 2.1.2 npos 含义 2.2 赋值重载 - 初始化 2.3 析构函数 2.2 string 类对象的访问和…

目前服务器2核4G支持多少人同时访问?性能如何?

腾讯云轻量应用服务器2核4G5M配置性能测评&#xff0c;腾讯云轻量2核4G5M带宽服务器支持多少人在线访问&#xff1f;并发数10&#xff0c;支持每天5000IP人数访问&#xff0c;腾讯云百科txybk.com整理2核4G服务器支持多少人同时在线&#xff1f;并发数测试、CPU性能、内存性能、…

Qt 窗口MainWindow(下)

对话框 对话框是 GUI 程序中不可或缺的组成部分。一些不适合在主窗口实现的功能组件可以设置在对话框中。对话框通常是一个顶层窗口&#xff0c;出现在程序最上层&#xff0c;用于实现短期任务或者简洁的用户交互。Qt 常用的内置对话框有: QFiledialog (文件对话框)、QColorDi…

36.基于SpringBoot + Vue实现的前后端分离-高校汉服租赁网站系统(项目 + 论文)

项目介绍 本站是一个B/S模式系统&#xff0c;采用SpringBoot Vue框架&#xff0c;MYSQL数据库设计开发&#xff0c;充分保证系统的稳定性。系统具有界面清晰、操作简单&#xff0c;功能齐全的特点&#xff0c;使得基于SpringBoot Vue技术的高校汉服租赁网站系统设计与实现管理…

【包远程安装运行】SpringBoot+Mysql实现的美食分享菜谱制作平台+演示视频+开发文档(论文模板)

今天发布的是由【猿来入此】的优秀学员独立做的一个基于springboot脚手架的美食分享菜谱制作平台系统&#xff0c;该系统分为前台和后台&#xff0c;多用户分享平台。主要实现了 除脚手架功能以外下面是系统的功能&#xff1a; 前台普通用户&#xff1a;注册、登录、首页、美食…

如何在软件测试行业走的更远?

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 时间往前推10年&#xff0c;IT业如日中天。 其中测试更是一个极具包容性的行业。那些希望在技术…

图像抠图DIS——自然图像中高精度二分图像抠图的方法(C++/python模型推理)

概述 DIS&#xff08;Dichotomous Image Segmentation&#xff09;是一种新的图像分割任务&#xff0c;旨在从自然图像中分割出高精度的物体。与传统的图像分割任务相比&#xff0c;DIS更侧重于具有单个或几个目标的图像&#xff0c;因此可以提供更丰富准确的细节。 为了研究…

Java只有中国人在搞了吗?

还是看你将来想干啥。想干应用架构&#xff0c;与Java狗谈笑风生&#xff0c;沆瀣一气&#xff0c;你就好好写Java&#xff0c;学DDD&#xff0c;看Clean Architecture。你想成为炼丹玄学工程师&#xff0c;年入百万&#xff0c;就选python&#xff0c;专精各种paper。你不在意…

如何修改SystemUI Clock的样式

开机的流程为&#xff1a; 在 CollapsedStatusBarFragment 的onCreateView 方法中 inflate R.layout.status_bar.xml&#xff0c; 里面定义有Clock。 CollapsedStatusBarFragment 的被调用流程为&#xff1a; 在StatusBar 的makeStatusBarView方法中显示出来。 所以可以在文…

Vue 若依框架 form-generator添加表格组件和动态表单组件

效果图&#xff1a; 在若依框架自带的流程表单配置基础上添加这两个组件 config.js // 表单属性【右面板】 export const formConf {formRef: elForm,formModel: formData,other: other,size: medium,labelPosition: right,labelWidth: 100,formRules: rules,gutter: 15,dis…

vue2 和 vue3 配置路由有什么区别

vue2 和 vue3 配置路由有什么区别 初始化路由器实例&#xff1a;注入到应用中&#xff1a;动态路由参数和捕获所有路由&#xff1a;编程式导航 API&#xff1a;异步加载组件&#xff1a; vue2 如何 使用路由 第一步&#xff1a;安装 vue-router第二步&#xff1a;创建路由组件第…

在面对API的安全风险,WAAP全站防护能做到哪些?

随着数字化转型的加速&#xff0c;API&#xff08;应用程序接口&#xff09;已经成为企业间和企业内部系统交互的核心组件。在应用程序开发过程中&#xff0c;API能够在不引起用户注意的情况下&#xff0c;无缝、流畅地完成各种任务。例如从一个应用程序中提取所需数据并传递给…

【MySQL】知识点 + 1

# &#xff08;1&#xff09;查询当前日期、当前时间以及到2022年1月1日还有多少天&#xff0c;然后通过mysql命令执行命令。 select curdate() AS 当前日期,curtime() AS 当前时间,datediff(2022-01-01, curdate()) AS 距离2022年1月1日还有天数;# &#xff08;2&#xff09;利…

【iOS ARKit】3D文字

首先&#xff0c;3D场景中渲染的任何虚拟元素都必须具有网格&#xff08;顶点及顶点间的拓扑关系&#xff09;&#xff0c;没有网格的元素无法利用GPU 进行渲染&#xff0c;因此&#xff0c;在3D 场景申渲染 3D文字时&#xff0c;文字也必须具有网格。在计算机系统中&#xff0…

发展新质生产力,亚信科技切中产业痛点

管理学大师拉姆查兰认为&#xff0c;经营性不确定性通常在预知范围之内&#xff0c;不会对原有格局产生根本性影响&#xff1b;而结构性不确定性则源于外部环境的根本性变化&#xff0c;将彻底改变产业格局&#xff0c;带来根本性影响。 毫无疑问&#xff0c;一个充满结构性不…