人工智能通识教程（理工版）课件 第5章 搜索与问题求解

人工智能通识（理工科）主要内容搜索算法的基本概念穷举搜索算法二分搜索算法广度优先搜索深度优先搜索5.1搜索算法的基本概念搜索算法的定义：按照一定策略从问题求解空间中寻找问题解的算法面向线性数据结构的搜索：穷举搜索面向有序数据结构的搜索：二分搜索面向树形与图结构数据的搜索广度优先搜索深度优先搜索5.2穷举搜索算法穷举法：也称枚举法，暴力求解方法，其运行效率低但简单有用。设有2n(n<=6)个球队进行单循环比赛，计划在2n–1天内完成全部比赛，每个队每天进行一场比赛。设计一个比赛的安排，使在2n–1天内每个队都与不同的对手比赛。白帽子和红帽子问题。厅内有5个人，他们都戴着白帽子或者红帽子。已知戴白帽子的人说真话，戴红帽子的人说假话，请从他们各自提供的线索辨别谁戴白帽子，谁戴红帽子。甲：我看见一个戴白帽子的。乙：我没有看见戴红帽子的。丙：我看见一个戴白帽子的，但不是甲。丁：我没有看见戴白帽子的。戊：我的帽子和丙一样。5.2穷举搜索算法穷举算法实现步骤(1)从问题解的表达形式出发，确定穷举对象。(2)逐一列举可能解，根据穷举的参数构造循环。(3)根据问题表达式逐一验证，满足条件采纳，否则抛弃。穷举算法的要点列举所有可能的解（不能遗漏，也不能重复）注意效率改进5.2.1数学问题中的穷举【例5-1】输出所有的水仙花数。水仙花数是指一个3位数，每个位置上的数字的3次幂之和等于它本身，如153是一个水仙花数，因为13+53+33=153。传统算法：将一个整数的个、十、百位分解出来foriin

range(100,1000):a=i/100b=i/10%10c=i%10

ifa**3+b**3+c**3==i:

print(i)5.2.1数学问题中的穷举【例5-1】输出所有的水仙花数。水仙花数是指一个3位数，每个位置上的数字的3次幂之和等于它本身，如153是一个水仙花数，因为13+53+33=153。方法二：枚举各位数字的方法foriin

range(1,10):

forjin

range(0,10):

forkin

range(0,10):

ifi*100+j*10+k==i**3+j**3+k**3:

print(i*100+j*10+k)5.2.1数学问题中的穷举【例5-2】百钱百鸡问题：鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、母、雏各几何？cock，hen，chick的取值范围：0<cock<20,

0<hen<33,

0<chick<99(1)确定穷举对象公鸡、母鸡、小鸡(2)列举可能解，组织循环(3)验证表达式cock+hen+chick==1005*cock+3*hen+chick/3==1005.2.1数学问题中的穷举【例5-2】百钱百鸡问题：鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、母、雏各几何？forcockin

range(1,20):

forhenin

range(1,33):

forchickin

range(3,99,3):

ifcock+hen+chick==100and5*cock+3*hen+chick//3==100:

print("cock=",cock,"hen=",hen,"chick=",chick)思考：共列举了多少组解？1932325.2.1数学问题中的穷举forcockin

range(1,20):

forhenin

range(1,33):

forchickin

range(3,99,3):

ifcock+hen+chick==100and5*cock+3*hen+chick//3==100:

print("cock=",cock,"hen=",hen,"chick=",chick)forcockin

range(1,20):

forhenin

range(1,33):

chick=100-cock-hen

if

chick%3==0and5*cock+3*hen+chick//3==100:

print("cock=",cock,"hen=",hen,"chick=",chick)优化，去掉一重循环5.2.2逻辑推理中的穷举【例5-3】有四位同学中的一位做了好事，未留名，表扬信来了之后，校长问这四位是谁做的好事。A说：不是我。B说：是C。C说：是D。D说：他胡说。已知有三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。5.2.2逻辑推理中的穷举穷举试探。我们现在并不知道是谁做了好事，但我们知道做好事的人是A,B,C,D四个人中的某一个。因此，我们可以一个一个地试探。ABCD(1)确定穷举对象做好事的人：thisman(2)列举可能解，组织循环"ABCD"['A','B','C','D']5.2.2逻辑推理中的穷举四个说话的人关系表达式A说：不是我。B说：是C。C说：是D。D说：他胡说。“已知三个人说的是真话，一个人说假话”。(thisman!="A")+(thisman=="C")+(thisman=="D")+(thisman!="D")==3

(3)验证表达式forthismanin

"ABCD":

if(thisman!="A")+(thisman=="C")+(thisman=="D")\

+(thisman!="D")==3:

print("做好事的人是:",thisman)thisman!='A'thisman=='C'thisman=='D'thisman!='D'5.2.2逻辑推理中的穷举【例5-4】四大湖问题。上地理课时，四个学生对我国四个淡水湖大小问题回答如下：A学生：洞庭湖最大，洪泽湖最小，鄱阳湖第3。B学生：洪泽湖最大，洞庭湖最小，鄱阳湖第2，太湖第3。C学生：洪泽湖最小，洞庭湖第3。D学生：鄱阳湖最大，太湖最小，洪泽湖第2，洞庭第3。已知对于湖的大小，每个学生仅答对一个，请编程判断四个湖的大小。a—洞庭湖，b—洪泽湖，c—鄱阳湖，d—太湖a，b，c，d：可能的取值为[1,2,3,4]变量的取值互不相同，1表示最大，4表示最小5.2.2逻辑推理中的穷举(3)验证表达式四个说话的人关系表达式洞庭湖最大，洪泽湖最小，鄱阳湖第3((a==1)+(b==4)+(c==3))==1洪泽湖最大，洞庭湖最小，鄱阳湖第2，太湖第3

((b==1)+(a==4)+(c==2)+(d==3))==1洪泽湖最小，洞庭湖第3

((b==4)+(a==3))==1鄱阳湖最大，太湖最小，洪泽湖第2，洞庭第3((c==1)+(d==4)+(b==2)+(a==3))==1a—洞庭湖，b—洪泽湖，c—鄱阳湖，d—太湖a，b，c，d：可能的取值为{1,2,3,4}变量的取值互不相同，1表示最大，4表示最小for

dth

in

range(1,5):#洞庭湖

for

hzh

in

range(1,5):#洪泽湖

if

dth!=hzh:#互斥

for

pyh

in

range(1,5):#鄱阳湖

if

pyh!=dth

and

pyh!=hzh:#互斥

for

th

in

range(1,5):#太湖

if

th!=dth

and

th!=hzh

and

th!=pyh:#互斥a=((dth==1)+(hzh==4)+(pyh==3))==1b=((hzh==1)+(dth==4)+(pyh==2)+(th==3))==1c=((hzh==4)+(dth==3))==1d=((pyh==1)+(th==4)+(hzh==2)+(dth==3))==1

ifaandbandccandd:

print("洞庭湖=",dth)

print("洪泽湖=",hzh)

print("鄱阳湖=",pyh)

print("太湖=",th)洞庭湖=2洪泽湖=4鄱阳湖=1太湖=3a—洞庭湖，b—洪泽湖，c—鄱阳湖，d—太湖a，b，c，d：可能的取值为{1,2,3,4}变量的取值互不相同，1表示最大，4表示最小5.3二分搜索算法二分搜索（BinarySearch）：折半搜索一种高效的搜索算法核心思想：将有序元素组成的列表分成两部分，每次比较中间元素与目标值的大小，根据比较结果确认是否找到目标，或在当前列表的左半部分列表继续搜索，或者再当前列表的右半部分列表继续搜索，从而缩小搜索范围，如此迭代进行。5.3二分搜索算法二分搜索算法的步骤确定搜索范围：初始时搜索整个列表，假设列表中元素是增序排列。计算中间位置：取当前搜索范围的中间索引。比较中间元素：若中间元素等于目标值，返回其索引。若中间元素大于目标值，将搜索范围缩小到左半部分。若中间元素小于目标值，将搜索范围缩小至右半部分。重复步骤（2）-（3），直到找到目标值或搜索范围为空。leftrightmid0

12345678910513192137566475808892找210

12345678910513192137566475808892leftrightmidleftmidright0

12345678910513195664758088922137查找成功leftrightmid找700

12345678910513192137566475808892leftmid0

12345678910right513192137566475808892right5131921375664758088920

12345678910leftmidleftmidright0

123456789105131921375664758088920

12345678910513192137566475808892leftright查找范围不成立，查找失败5.3二分搜索算法二分搜索算法的两个前提有序性要求：必须在已排序的列表中执行搜索分治策略：每次将当前搜索范围分为两部分，通过比较中间元素与目标值的大小，排除其中一半的元素5.3二分搜索算法

5.3二分搜索算法f(right)f(left)

leftrightryy=r2

步骤1：确定搜索区间[left,right]

步骤2：计算中间值：mid=(left+right)/2步骤3：比较中间值的平方与x的大小若mid2与x的差值的绝对值小于eps，则mid即为所求的近似平方根若mid2>x，说明平方根r在左半部分，更新right=mid若mid2<x，说明平方根r在右半部分，更新left=mid重复步骤2~步骤3，直到满足终止条件本质：求r2=xxdefsqrt(x:float,eps:float=1e-5):

ifx<0:

raise

ValueError("Cannotcomputesquarerootofanegativenumber")

ifx==0:

return0.0

#确定初始搜索区间left,right=(x,1.0)ifx<1else(1.0,x)

whileleft<=right:mid=(left+right)/2square=mid*mid

#若误差小于阈值，直接返回

if

abs(square-x)<eps:

returnmid

#调整搜索区间

ifsquare>x:right=mid

else:left=midprint(sqrt(2))5.4广度优先搜索广度优先搜索（BFS，Breadth-FirstSearch）是一种逐层探索的搜索方法，常用于求解最短路径问题。采用广度优先搜索算法求解的基本步骤如下：构建问题的“搜索空间”，把每种可能的状态看成一个“点”，状态之间的转换看成“边”；明确问题的终止条件，例如，是否到达出口，或者找到满足某条件的状态；初始化所需数据结构，包括已访问标记与待访问队列，并对已搜索节点设置访问标记；逐层搜索，每次从待访问队列中取出一个点，检查它是否是目标，如果不是，就将其的“邻居”加入待访问队列；搜索终止，找到目标或搜索完所有可能解。5.4广度优先搜索具体实现时，广度优先搜索可以有递归和非递归两种实现方式：递归形式的广度优先搜索非递归形式的广度优先搜索5.4广度优先搜索-递归形式例【5-6】使用广度优先搜索寻找迷宫出口。给定一个N*M的迷宫，用二维矩阵表示。其中：0表示可以通过的空格，1表示不可通过的墙壁。迷宫起点为左上角(0,0)，终点为右下角(N-1,M-1)。求从起点到终点的最短路径长度，并假设只能向上下左右四个方向移动。如果没有从起点到迷宫出口的路径，即无法到达终点，返回-1。思路：首先明确广度优先搜索的目的，找到走出迷宫的最短路径长度。将搜索空间明确为题目中描述的二维迷宫，终止条件为到达右下角(N-1,M-1)。对于二维迷宫，其已访问标记visited也应为一个二维数组。在进行搜索时，需要对四个方向的合法位置进行判断，并加入到候选合法位置列表中，完成一层的搜索，同时注意终止条件与非法条件的判断：例如越界、无处可走等情况应即时返回。完成上一层的搜索后，对于每一个候选合法位置再进行广度优先搜索，直至找到右下角(N-1,M-1)，或无路可走为止。5.4广度优先搜索-递归形式defshortest_path_recursive(maze):n,m=len(maze),len(maze[0])visited=[[Falsefor_inrange(m)]for_inrange(n)]visited[0][0]=True#初始化起点已访问

#定义递归函数

defbfs_layer(current_nodes,steps):ifnotcurrent_nodes:return-1#没有新节点，无法到达

next_layer=[]forx,yincurrent_nodes:ifx==n-1andy==m-1:returnsteps#找到终点

#向上

new_x,new_y=x-1,y

5.4广度优先搜索-递归形式if0<=new_x<nand0<=new_y<m:ifnotvisited[new_x][new_y]andmaze[new_x][new_y]==0:visited[new_x][new_y]=Truenext_layer.append((new_x,new_y))

new_x,new_y=x+1,y

#向下if0<=new_x<nand0<=new_y<m:ifnotvisited[new_x][new_y]andmaze[new_x][new_y]==0:visited[new_x][new_y]=Truenext_layer.append((new_x,new_y))

new_x,new_y=x,y-1#向左if0<=new_x<nand0<=new_y<m:ifnotvisited[new_x][new_y]andmaze[new_x][new_y]==0:visited[new_x][new_y]=Truenext_layer.append((new_x,new_y))5.4广度优先搜索-递归形式

new_x,new_y=x,y+1

#向右if0<=new_x<nand0<=new_y<m:ifnotvisited[new_x][new_y]andmaze[new_x][new_y]==0:visited[new_x][new_y]=Truenext_layer.append((new_x,new_y))result=bfs_layer(next_layer,steps+1)

#递归处理下一层returnresultreturnbfs_layer([(0,0)],0)

#初始调用：起点是（0，0）位置，步数为0if__name__=='__main__':maze=[[0,1,0,0],[0,0,0,1],[1,1,0,0],[0,0,0,0]]print(shortest_path_recursive(maze))5.4广度优先搜索-递归形式在上述示例中，发现向迷宫四个方向行走的代码重复度高，因此考虑将四个代码片段压缩为一个，以提高可读性、可维护性。定义一个方向数组，该数组控制new_x，new_y相较于x与y的偏移量：directions=[(-1,0),(1,0),(0,-1),(0,1)]#上下左右现在，只需要使用for循环遍历每一个方向即可。defshortest_path_recursive(maze):n,m=len(maze),len(maze[0])directions=[(-1,0),(1,0),(0,-1),(0,1)]#上下左右

visited=[[Falsefor_inrange(m)]for_inrange(n)]visited[0][0]=True#初始化起点已访问

5.4广度优先搜索-递归形式defbfs_layer(current_nodes,steps):ifnotcurrent_nodes:return-1#没有新节点，无法到达

next_layer=[]forx,yincurrent_nodes:ifx==n-1andy==m-1:returnsteps#找到终点

fordx,dyindirections:new_x,new_y=x+dx,y+dyif0<=new_x<nand0<=new_y<m:ifnotvisited[new_x][new_y]andmaze[new_x][new_y]==0:visited[new_x][new_y]=Truenext_layer.append((new_x,new_y))#递归处理下一层

result=bfs_layer(next_layer,steps+1)returnresult#初始调用：起点是（0，0）位置，步数为0returnbfs_layer([(0,0)],0)5.4广度优先搜索-非递归形式对于递归形式的广度优先搜索，当输入规模较大时可能会因递归层数过深导致栈溢出。下面将介绍将递归形式的广度优先搜索转为非递归形式，提高算法执行效率。思路：例5-6中广度优先的递归形式代码中，首先将可能的合法位置加入到候选列表中，在将该层的候选位置全部判断完毕后，对每一个候选列表中的位置再进行广度优先搜索，直至满足终止条件或无解为止。向一个列表中添加元素，并在添加完成后从最开始添加的元素依次取出，这是队列的特性：先进先出（FIFO，Firstinfirstout）。因此，考虑在添加完毕后，不再调用广度优先搜索函数自身，而是从这个队列中取出元素，继续搜索，完成非递归化。5.4广度优先搜索-非递归形式defshortest_path_bfs(maze):n,m=len(maze),len(maze[0])directions=[(-1,0),(1,0),(0,-1),(0,1)]#上下左右

visited=[[Falsefor_inrange(m)]for_inrange(n)]visited[0][0]=True#初始化用于替代递归的队列

queue=deque()queue.append((0,0,0))whilequeue:#从队列中取出一个元素

x,y,steps=queue.popleft()5.4广度优先搜索-非递归形式#到达终点

ifx==n-1andy==m-1:returnsteps#向四个方向探索

fordx,dyindirections:new_x=x+dxnew_y=y+dy#添加所有合法侯选位置

if0<=new_x<nand0<=new_y<m:ifnotvisited[new_x][new_y]andmaze[new_x][new_y]==0:visited[new_x][new_y]=Truequeue.append((new_x,new_y,steps+1))return-1#无法到达终点5.4广度优先搜索-非递归形式【例5-7】四皇后问题：在4×4的国际象棋棋盘上放置4个皇后，使得任意两个皇后都不能互相攻击（即不在同一行、同一列或同一对角线上）。输出所有合法的皇后摆放方案数。思路：对于四皇后问题，4个皇后的排列位置构成了一个搜索空间。使用一个列表state表示四皇后的位置：state[i]=j表示第i行的皇后在第j列。对于初始条件来说，应为空棋盘。因此，有初始化代码：queue=deque([[]])#初始化result=0可以发现，当state的长度为4时，代表已经放置了4个皇后（假设放置时只可以向不能互相攻击的位置放置皇后），因此len(state)==4为终止条件。5.4广度优先搜索-非递归形式接下来，需要定义检查皇后放置位置是否合法的函数。首先，新放置的皇后不可以与已有皇后的列相同（行相同已经通过state的定义规避）：ifstate[row]==new_col:returnFalse其次，需要保证新放置的皇后位置不可以在已放置皇后的对角线上：ifabs(state[row]-new_col)==current_row-row:returnFalse这样，就可以得到所需函数：defis_valid(state,new_col):current_row=len(state)forrowinrange(current_row):#检查列冲突和对角线冲突

ifstate[row]==new_colorabs(state[row]-new_col)==current_row-row:returnFalsereturnTrue保证新放置的皇后位置new_col不与已有皇后列的位置相同5.4广度优先搜索-非递归形式defbfs():queue=dequeue([i])result=0whilequeue:state=queue.popleft()#出队

current_row=len(state)#找到合法解：已放置4个皇后，且互相不能攻击

ifcurrent_row==4:result+=1continue#尝试在当前行的每一列放置皇后

forcolinrange(4):ifis_valid(state,col):#检测新放置的皇后是否和之前的皇后产生冲突

new_state=state+[col]#生成新状态

queue.append(new_state)returnresult5.4广度优先搜索-非递归形式使用广度优先搜索求解四皇后问题的过程，如下图所示。广度优先搜索将会从初始状态出发，逐层进行搜索。直到第四层搜索时，程序找到了两种合法情况，同时由于其他状态均无合法的下一状态，算法终止，输出四皇后问题合法的2种解。5.4广度优先搜索递归与非递归BFS对比分析递归BFS理论上可以递归实现，但过程复杂，不直观代码可读性差，几乎不在实际开发中使用不利于展示层次遍历特性非递归BFS（队列实现）通过显式队列维护访问顺序（先进先出）代码结构清晰，直观展示逐层搜索不依赖系统栈，无递归深度限制实际应用和教学中几乎都采用这种方式5.5深度优先搜索深度优先搜索（DFS，Depth-FirstSearch）是一种系统地“向前走到底，再回头”的搜索方法。核心思想：从起点开始，优先沿着一条路径一直走到底，直到走不通了，再退回来更换另一条路继续探索。与广度优先搜索一样，都是在一定规则下“遍历所有可能”，但方式不同—广度优先是“分层推进”，而深度优先则是“深挖到底”。相比于简单的穷举法，深度优先更像是有选择的尝试，可以配合剪枝、记忆化等方式减少无效搜索，提升效率。5.5深度优先搜索深度优先搜索算法的特点在于空间复杂度较低，适合树状结构或存在明显分支特征的场景。在搜索时，可以排除不符合条件的情况，加速搜索。采用深度优先搜索算法解题的基本步骤如下：将问题中的状态抽象为节点，将转移条件抽象为边，构建树状或图状搜索空间；明确问题的终止条件；初始化访问标记与所需数据结构，将初始节点压入栈，设置已访问标记；进行深度优先遍历：沿当前路径持续访问未探索子节点，无法继续后回溯至最近分支；优化程序，通过应用记忆化搜索或剪枝策略，根据问题背景缩小搜索范围，提升搜索效率。5.5深度优先搜索具体实现时，深度优先搜索可以有递归和非递归两种实现方式：递归形式的深度优先搜索非递归形式的深度优先搜索5.5深度优先搜索-递归形式【例5-8】地毯数量问题。给定一个由1（地毯块）和0（地面）组成的二维网格，计算地毯的数量。地毯指由水平或垂直方向上相邻的地毯块连接形成，且四周均为地面。二维网格外部均为地面。。思路：此题需要使用深度优先搜索进行求解，找到地毯的个数。不难想到可以对每一个地毯块进行搜索，直到该地毯块相连的所有地毯块均被找到，标记这些地毯块为一块地毯。defdfs_recursive(grid):count=0n,m=len(grid),len(grid[0])directions=[(0,1),(0,-1),(1,0),(-1,0)]defdfs(x,y):

#具体定义见下页5.5深度优先搜索-递归形式defdfs(x,y):#递归终止条件

ifx<0orx>=nory<0ory>=morgrid[x][y]!='1':return#标记当前网格为已访问

grid[x][y]='0'#递归探索四个方向

fordx,dyindirections:dfs(x+dx,y+dy)foriinrange(n):forjinrange(m):ifgrid[i][j]=='1':dfs(i,j)count+=1#每次DFS完成，地毯数+1

returncount5.5深度优先搜索-递归形式if__name__=='__main__':grid=[['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]print(dfs_recursive(grid))程序运行结果为：3。对于采用深度优先搜索来求解“地毯数量”问题，程序通过对每一个未访问的'1'单元（表示地毯块）进行搜索，将其与所有四连通相邻的'1'相连接，形成一块完整的地毯，并将访问过的格子标记为'0'，以避免重复计算。5.5深度优先搜索-非递归形式思路：考虑例5-8中的递归形式深度优先搜索，在找到一个可行方向后，立刻便进行下一步搜索，直到满足终止条件，或下一步不合法为止。此时深度优先搜索会回溯到上一个没有搜索完的位置，继续向下搜索。也就是说，先将一层的所有合法下一步压入一个数据结构中，并从最后压入的元素开始处理。待没有合法的下一步后，再处理上一层倒数第二个合法的元素。这种后进先出（Lastinfirstout,LIFO）的特性与栈相同，可以使用栈来实现非递归形式的深度优先搜索。5.5深度优先搜索-非递归形式