人工智能通识教程（理工版）课件 汪红兵 第5-11章 搜索与问题求解- 人工智能的伦理

人工智能通识（理工科）主要内容搜索算法的基本概念穷举搜索算法二分搜索算法广度优先搜索深度优先搜索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深度优先搜索-非递归形式defdfs_inter(grid):count=0n,m=len(grid),len(grid[0])directions=[(-1,0),(1,0),(0,-1),(0,1)]foriinrange(n):forjinrange(m):ifgrid[i][j]=='1':count+=1stack=[(i,j)]grid[i][j]='0'#标记为已访问

5.5深度优先搜索-非递归形式

whilestack:

#用栈模拟DFSx,y=stack.pop()

fordx,dyindirections:

#探索四个方向new_x=x+dxnew_y=y+dy#检查新坐标是否合法

if0<=new_x<nand0<=new_y<mandgrid[new_x][new_y]=='1':grid[new_x][new_y]='0'#标记为已访问

stack.append((new_x,new_y))#入栈

returncount5.5深度优先搜索-非递归形式使用深度优先搜索重写【例5-7】四皇后问题。defdfs():stack=[[]]#初始化

result=0whilestack:state=stack.pop()#出栈

current_row=len(state)

ifcurrent_row==4:

#找到合法解：已放置4个皇后result+=1continue

forcolinrange(4):

#尝试在当前行的每一列放置皇后ifis_valid(state,col):#检测新放置的皇后是否和之前的皇后产生冲突

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

stack.append(new_state)returnresult5.5深度优先搜索-非递归形式使用深度优先搜索求解四皇后问题，如下图所示。从搜索过程中可以看出，搜索从初始状态出发，首先搜索到了左侧的第三层，发现没有合法的下一步，且不满足终止条件后，回溯到了上一个未处理完的状态，继续搜索。深度优先搜索重复该过程，直到搜索完整个状态空间为止。5.5深度优先搜索递归与非递归DFS对比分析递归DFS通过函数调用系统栈实现回溯代码简洁、结构清晰，易于理解依赖系统栈，深度过大可能导致栈溢出不易灵活控制中间过程非递归DFS（显式栈）使用显式栈手动维护搜索路径代码相对复杂，但更直观展示栈的工作原理不受系统栈限制，适合深度很大的图/树更灵活，可在遍历过程中方便地加入自定义操作本章重要知识点搜索算法与按照解空间数据结构的分类穷举算法的核心思想和典型应用二分搜索的核心思想和典型应用广度优先搜索的核心思想和典型应用深度优先搜索的核心思想和典型应用人工智能通识（理工科）北京科技大学主要内容数据和信息及知识知识表示方法基于规则的推理知识图谱与嵌入数据、信息与知识关系数据信息知识加工处理提炼、总结知识表示方法知识表示是将知识转化为计算机可处理形式命题逻辑谓词逻辑产生式表示法语义网络表示法命题逻辑命题联结词表示形式意义与(and)或(or)非(not)条件(conditional)双向条件(bi-conditional)谓词逻辑谓词逻辑：刻画主体（个体和群体）之间逻辑关系的方法

描述命题的形式：P(x1,x2,┈,xn)例1：“小张是一个学生”和“小李是一个学生”，谓词逻辑表示为：is_a(小张,学生)和is_a(小李,学生)例2：“雪花是白色的”和“棉花是白色的”谓词逻辑表示为：color(雪花,白色)和color(棉花,白色)

产生式表示法产生式表示法用来表示确定性规则、不确定性规则以及事实性知识。形式：IFPTHENQ例1：IF动物AND会飞AND卵生THEN该动物是鸟例2：IF动物AND会飞AND卵生THEN该动物是鸟（0.9）语义网络表示法语义网络是一种用实体及其语义关系来表达知识的有向图三元组表示形式：（结点1，弧，结点2）例：产生式系统产生式系统采用"条件-动作"（IF-THEN）规则形式实现知识表示，由规则库、推理机和事实库组成知识图谱构构建自上而下方式自下而上方式知识图谱是一种结构化的语义知识表示知识图谱与大语言模型协同利用检索增强生成技术提升大语言模型系统问答时的准确性、相关性和时效性本章重要知识点知识表示的经典方式知识图谱的构建方式图检索增强技术在大模型系统应用人工智能通识（理工科）北京科技大学主要内容机器学习概述机器学习的分类机器学习的训练过程机器学习的模型评测机器学习案例7.1机器学习概述

通俗来说，机器学习就是从数据中发现规律或模式，并将其用于预测或决策任务。米切尔（TomMitchell）给出了机器学习的形式化定义：对于任务T（Task）和性能度量P（Performance），如果一个计算机程序在任务T上的性能P随着经验E（Experience）的提高而改善，则称该程序从经验E中学习。MessureImproveProcess机器学习概述

案例一：猫狗图像分类。假设所有图像中仅有一只猫或一只狗：任务T：识别出图像中是猫还是狗性能P：识别的准确率经验E：数据。一些已经收集的多样化的猫狗图像并给出分类标记（文件夹名隐含标签，将猫和狗图像分成两个文件夹保存）。MessureImproveProcess机器学习概述

MessureImproveProcess机器学习的发展历程机器学习（MachineLearning）的发展总体可以分为三个阶段：早期理论奠基、统计学习时代、深度学习时代。早期理论奠基（1940s–1960s）：探索机器如何从数据中学习规律1943年：McCulloch&Pitts提出人工神经元模型。1957年：Rosenblatt发明感知机（Perceptron），成为首个可训练的神经网络模型。局限：算力不足，理论未成熟，感知机无法解决非线性问题。线性可分线性不可分统计学习时代（1970s–2000s）：基于概率与统计的模型成为主流，依赖特征工程1980s：决策树（ID3算法）等学习方法出现。1990s：支持向量机（SVM）在分类任务中表现优异。1990s~2000s：集成学习（如AdaBoost、随机森林）提升模型鲁棒性。深度学习革命（2010s–至今）：大数据、GPU算力提升、算法突破1986年：辛顿团队验证并推广了反向传播算法，证明多层感知机可以解决非线性问题。2012年：AlexNet在ImageNet竞赛中夺冠（CNN的里程碑）。2014年：生成对抗网络（GAN）提出，推动生成式AI技术的发展（生成器+判别器）。2016年：强化学习崭露头角，AlphaGo击败人类围棋冠军。2017年，Transformer架构出现，奠定大语言模型的基础。当前趋势：大语言模型推动通用人工智能（AGI）探索，多模态学习（文本、图像、视频联合建模）机器学习的分类当前，机器学习是人工智能最重要、最具有热度的研究分支。机器学习的研究范畴很广，从发展过程来看，既包含以统计学习为基础的传统算法（如线性回归、决策树、支持向量机、聚类、主成分分析等），也涵盖以深度学习和强化学习为核心的现代方法（如卷积神经网络、深度强化学习）。学习范式：有监督学习：有标签无监督学习：无标签强化学习：环境交互获取奖励信号人工智能机器学习深度学习强化学习深度强化学习线性回归决策树支持向量机聚类LLM7.2机器学习算法概述线性回归决策树支持向量机聚类K近邻人工神经网络深度学习强化学习（1）线性回归假设因变量和自变量之间是线性关系，其目标是找到最优的系数和截距，使得线性模型的预测值和实际值之间的差值最小。例：若已有关于收入和上学年限的训练数据集，使用一元线性回归建模收入与上学年限之间的线性关系。使用一元线性回归，训练集中的每个样本数据对应着二维空间中的一个点。线性回归的目的是在众多可能的直线中找到一条最优直线：使得这条直线到所有数据点的垂直距离（即残差）的平方和最小==》最小二乘法。y=wx+b

（2）决策树决策树是一种常用的基于概率的分类方法，在已知各种情况发生概率的基础上，通过构成决策树来求进行分类决策。例：要判断是否去打篮球，可以根据“天气”

“温度”

“湿度”

“刮风”几个条件判断，最后得到结果：去、不去。算法关键：如何选择最优特征和分割点（用最少的分裂、最大化数据纯度）日期天气温度(华氏度)湿度起风打球否1晴8585FNo2晴8090TNo3阴8378FYes4雨7096FYes5雨6880FYes6雨6570TNo7阴6465TYes8晴7295FNo9晴6970FYes10雨7580FYes11晴7570TYes12阴7290TYes13阴8175FYes14雨7180TNo天气温度晴打雨刮风打<=75不>75打否不是（2）决策树决策树的构建有许多经典的算法：ID3、C4.5、CART等。信息熵：信息越混乱，信息熵越大信息增益：按属性分支后，信息熵下降最多的（3）支持向量机（SupportVectorMachines）2000年代至2010年代初，SVM在许多任务（小样本、高维数据分类）上表现优异，被认为是传统机器学习时代的“标杆算法”之一。支持向量机是一种对数据进行二元分类的广义线性分类器，其基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。（3）支持向量机寻找一个最优超平面（在特征空间中的决策边界）最大化不同类别数据之间的间隔，如果以后有了新的数据，这个超平面也能做出很好的分类（泛化能力强）（3）支持向量机可解释性：决策边界计算得到，能够可视化泛化能力强：通过最大化分类间隔，提升泛化能力强大的非线性处理能力：通过核函数实现特征到高维空间的非线性映射核函数无需显式计算高维映射，计算效率高常见的核函数有多项式核函数、高斯核函数等。（4）聚类（Clustering）聚类是传统机器学习领域实现无监督分类的经典方法按照一定的方式度量样本之间的相似度，将一个数据集分割成不同的簇，使得同一个簇内的数据对象的相似性尽可能大，不在同一个簇中的数据对象的差异性也尽可能大。通过这样的划分，每个簇对应于一个潜在的类别，实现分类。应用举例：电商平台根据用户的购买行为、浏览历史将客户分为不同群体（如高消费群体、折扣敏感群体），制定差异化营销策略。（4）聚类（Clustering）类别边界聚类中心（5）K近邻KNN是有监督学习算法找到当前样本的K个最近邻样本，然后通过投票实现分类或通过平均实现回归使用距离来衡量各个样本之间的相似性（6）人工神经网络—神经元人脑神经元是大脑中互相连接的、参与化学和电信号处理和传输的神经细胞。多个信号到达树突后整合到细胞体累加起来，当累积信号量超过一定的阈值时，神经元被激活、产生输出信号，并通过轴突传送出去。人脑中有数百亿个神经元，这些神经元之间互相连接，以动态的方式相互通信，使人体能够正常运作。（6）人工神经网络—神经元人工神经元由人脑神经元进行简化、抽象得到，神经元接收n个其他神经元传递过来的输入信号；每个输入信号有对应的连接权重权值，表示相互连接的两个人工神经元间相互作用的强弱；神经元接收到的总输入值与神经元的阈值θ进行比较，然后通过激活函数f处理以产生神经元的输出。（6）人工神经网络—神经元θ为神经元的阈值，

时，利用激活函数产生输出。

…

偏置b

权重………激活函数

（6）人工神经网络人工神经网络：将许多个人工神经元按照一定的层次结构连接起来

每个神经元都有自己的权重和偏置参数全连接神经网络（多层感知机）输入层隐藏层输出层特点：每个神经元都与前一层和后一层的所有神经元相连（6）人工神经网络优点：结构简单、理论上可以逼近任意连续函数，拟合复杂非线性关系缺点：参数多，计算量大、训练耗时久；可解释性差（6）人工神经网络传统神经网络方法的特点：对于原始的输入信号只经过较少层次的线性或者非线性处理来达到信号与信息处理的目的优点：结构简单、易于学习，在数学上有比较完善的算法缺点：对于复杂的信号，浅层结构模型的表达能力具有一定的局限性，并不能充分地学习到信号中复杂的结构信息。（6）人工神经网络—深度神经网络深度神经网络：通过多个隐藏层（通常≥2层）对输入数据进行层级化特征提取，从而自动学习复杂的非线性关系。模型层数结构错误率AlexNet(2012)8层16.4%VGGNet(2014)19层7.3%GoogLeNet(2014)22层6.7%ResNet(2015)152层3.57%ImageNet大规模视觉识别挑战赛层数增加模块创新结构优化（7）深度学习复杂神经网络模型(8)强化学习模拟人类的学习过程7.3机器学习的训练过程机器学习过程，特别是有监督学习，可以通过误差损失来观察模型训练情况，即模型在训练数据上的表现。为了保证模型更好的训练效果和泛化能力，需要将数据集划分为训练集、验证集和测试集。机器学习过程代表性的学习算法是梯度下降法和反向传播算法。机器学习经常要面对的任务有两大类：分类和回归。分类问题的输出为有限个离散值。回归问题的输出为无限个连续值。对于分类和回归损失函数，深度学习中经常使用交叉熵损失和均方误差损失来进行描述。数据算法评测机器学习的训练过程-损失函数1）均方误差损失：当模型的输出有M个类别，设这M个输出为，分别是每个类别的预测输出概率。例如，当识别的字符是0~9的10个字符的其中一个字符时，如果=，则在输出概率中，字符“1”对应的概率0.8为最大值，输出的分类结果为字符“1”，即识别出来的字符为“1”。这里，假设对于字符分类任务。对于识别字符0～9的其中一个字符问题，如果真实的字符为“1”，则均方误差损失（MSE）：如果真实标签为类别p，,则均方误差损失为：可以看出，预测类别p的均方误差损失，不仅与类别p的预测概率有关，还有其他类别的预测概率有关。均方误差损失是一种主要用于回归任务的损失函数，具有非负、放大误差特性等。

机器学习的训练过程-损失函数2）交叉熵损失（CE）:如果真实标签为类别p，,则交叉熵损失为：可以看出，预测类别p的交叉熵损失，只与类别p的预测概率有关，与其他类别的预测概率无关。大多数情况下，深度学习选择交叉熵作为分类损失函数。深度学习的训练过程就是多次反复输入、特征提取、计算损失和调整参数的过程，目标是降低损失函数的值，以获得高精度或误差较小的模型。为了保证机器学习模型更好的训练效果和泛化能力，通常需要将数据集划分为训练集、验证集和测试集训练集是模型学习的主要数据源，模型通过遍历训练集中的数据，不断调整内部参数，以最小化损失函数，从而学习到数据的潜在规律和特征验证集主要用于在训练过程中评估模型的性能，以便进行模型选择、参数调整等测试集用于在模型训练完成后，评估模型的最终性能机器学习的训练过程-数据集划分1）留出法留出法直接将数据集划分为两个互斥的集合，其中一个作为训练集，一个作为测试集。留出法对训练集和测试集进行比例分配时，如果训练集过大会导致模型更倾向于训练集，评估结果不够准确；如果测试集过大则评估的结果差异较大，降低了评估的真实性，所以通常的做法是将2/3~4/5的样本用于训练，剩余样本用于测试。留出法仅适用于数据集样本量较大的情况。当训练样本量较小时，机器学习算法缺少充分的训练样本，可能导致训练不充分，模型欠拟合。机器学习的训练过程-数据集划分2）K折交叉验证法K折交叉验证首先将数据集随机近似等分为不相交的K份，称为K折；其后，令其中的K-1份作为训练集，剩余的一份作为测试集。与留出法相似，为了减小因为样本划分不同而引入的差别，K折交叉验证通常要随机重复K次，获得K组训练集和测试集，进行K次训练和测试，最终计算K个测试结果的平均。实际应用中一般采取10次10折交叉验证。机器学习的训练过程-数据集划分损失函数提供了预测值与实际值之间的差异，但是这个差异如何指导模型参数的更新呢？训练的目标是找到最小的误差值，从而得到与实际值误差最小的预测值。1）梯度下降的原理梯度下降的基本思想是：沿着损失函数关于模型参数的梯度的反方向移动，可找到损失函数的最小值。梯度是一个向量，指向损失函数增长最快的方向。对于多元损失函数来说，梯度的每个分量是损失函数对每个参数的偏导数。当损失函数是一元函数时，可认为梯度就是斜率，即函数的导数。机器学习的训练过程-梯度下降梯度下降的示例机器学习的训练过程-梯度下降

机器学习的训练过程-梯度下降

机器学习的训练过程-梯度下降算法工作过程：梯度更新代码：机器学习的训练过程-梯度下降我们来看一个具体的通过梯度下降来训练线性模型的案例。可以看出：从一开始误差很大的绿色拟合线，不断在梯度下降的过程优化参数并缩小误差损失，红色的拟合线表现了缩小误差的运动过程前馈神经网络的参数优化过程主要分为两个阶段：正向计算和反向传播。正向计算指的是输入数据从输入层依次经过隐藏层的各层神经元进行逐层计算，通过输出层进行输出，实现神经网络的预测。反向传播指的是根据神经网络的预测值以及实际值（标签）计算损失函数值，将损失函数值对于神经网络的连接权重（参数）的梯度沿着正向计算路径进行反向传递，并对各个神经元之间的连接权重按照梯度进行调整和优化。经过多次正向计算预测值和反向传播误差值，优化神经网络的连接权重（参数），最终实现误差尽可能最小，拟合复杂的输入数据和输出数据之间的映射关系。机器学习的训练过程-反向传播算法1）

正向计算下面以一个含两个输入、三个神经元组成的隐藏层和两个输出的简单前馈神经网络为例，详细说明BP反向传播算法的工作过程。对于隐藏层的神经元h1，输入来自于x1和x2，输出给O1和O2。输入和输出分别如下列公式所示。

神经元h1的输入输出示意，如图所示。机器学习的训练过程-反向传播算法隐藏层的神经元h2，输入同样来自于X1和X2，输出给O1和O2。输入和输出分别如下：隐藏层的神经元h3，输入同样来自于X1和X2，输出给O1和O2。输入和输出分别如下：输出层神经元O1，输入来自于h1、h2和h3，输出即为模型的一个输出。输入和输出分别如下：

神经元O1的输入输出，如图所示。1）

正向计算机器学习的训练过程-反向传播算法输出层神经元O2，输入同样来自于h1、h2和h3，输出即为模型的另一个输出。输入和输出分别为：为计算简单，损失函数采用均方误差损失MSE，

，其中，yi为真实输出（标签数据），Oi为神经网络的预测输出。设输入X1和X2分别为0.5和0.3，相应的真实输出为0.23和-0.07。当各个神经元之间的连接权重确定之后，即可进行正向计算。一般来说，神经元之间的连接权重可初始化为(0,1)之间的小数，大多使用随机函数生成。1）

正向计算机器学习的训练过程-反向传播算法1）

正向计算隐藏层神经元和输出层神经元的输出分别如下：则均方误差损失MSE计算如下，真实输出为0.23和-0.07，预测输出为0.50和0.58。机器学习的训练过程-反向传播算法2)反向传播反向传播指的是将损失函数所表达的误差按原来正向计算的路径进行反向传递。反向传播是根据微积分中的链式法则，沿着从输出层经过隐藏层到输入层的反向顺序，依次计算损失函数对权重参数的梯度，并据此进行调整。计算MSE损失函数对w7的梯度，计算公式如下：

其中：

误差损失在权重w8~w12上的计算，与

的计算类似。机器学习的训练过程-反向传播算法2)反向传播对于输入层与隐藏层之间的权重，以权重w1为例，计算损失函数对w1的梯度，公式如下：其中，误差损失在权重w2~w6上的计算，与

的计算类似。

前馈神经网络的反向传播2)反向传播根据上述公式，分别计算误差损失在各个权重上的梯度，如下：

机器学习的训练过程-反向传播算法2)反向传播

机器学习的训练过程-反向传播算法2)反向传播根据MSE损失函数值对各个连接权重的梯度，对权重进行调整，这里，

是新的权重，wi是原有权重，

是MSE误差在神经元连接权重上的梯度，

是学习率，控制对梯度的学习程度。设=1，调整后的权重，如图所示再次进行一次正向计算，误差损失MSE=0.22，与调整前的误差损失0.25比较，误差损失得到了降低，说明模型通过学习提高了预测或拟合精度。

机器学习的训练过程-反向传播算法7.4机器学习的模型评测当模型训练完成之后，可以通过验证或测试数据来评估模型的表现。对于分类问题，可以通过混淆矩阵计算查准率、查全率等指标，而对于回归问题，则可以通过均方误差（MSE）、均方根误差（RMSE）等指标来评估。欠拟合和过拟合目标：模型具有良好的泛化能力训练误差：在训练集上的误差泛化误差：在“未来”样本上的误差，将测试集上的测试误差近似看作泛化误差训练数据未知测试数据训练应用欠拟合和过拟合欠拟合：当模型在训练数据上误差一直较大，无法找到合适的模型表达来描述数据集，称为模型欠拟合。欠拟合的可能原因是训练不充分、训练数据太少、训练数据中噪声过多、超参数设置不合理等。过拟合：当模型在训练数据上获得了较小的误