算法竞赛（Python）-AI的思维模式（搜索）
一 、深度优先搜索
深度优先搜索是最基本的搜索方法，在深度优先搜索的过程中，如果把所有的可行解看作一个空间，求解的过程就是在空间中游走的过程，当走到尽头，无路可走时，就会后退，进而寻找其它可行解。
在搜索中，可以通过灵活的“剪枝”操作，缩短可行解的范围。
1 零钱搭配
l烈日炎炎的夏天，小余在陪朋友逛街，当路过一家奶茶店时，想要买价格为s元的冰奶茶，但是，出门时小余忘记带手机了，钱包里只有n张纸币，面值分别为a0,a1,a2…an-1，小余要从这些纸币中挑选k张来支付，这k张纸币的面值之和恰好为s元，同时，为了避免麻烦，小余希望能够用最少的纸币来付钱，也就是让k最小。请你设计一个程序，计算出最小的k。
输入格式：
第一行为两个整数n，s，第2行为n个整数a0,a1，…an-1。
输出格式：
输出一个整数，最小的k。
样例输入：n=4,s=10;a=[9,1,6,3]
输出：2。
在本问题中，每一张纸币有“取”和"不取”两种情况，所有的n张纸币有2n ,所以可行解的数量为2n 。接下来考虑如何将2n 种可行解遍历一面，如果n是个定值，那么写n个for循环，层层嵌套。不过，在本问题中，n是一个变量，在输入具体数值前，并不知道要写几层for循环，所以需要借助函数的递归来实现。
import numpy as np
n=4;s=10;a=[9,1,6,3]
#搜索算法核心函数
def Solve(i,sum,num):
"""
i,sum,num 表示在第i张纸币前，已经抽取了num张纸币，这些纸币的面值之和为sum。在此基础上进行后续的操作
:param i: int
:param sum: int
:param num: int
:return:
"""
if i==n:#已经使用所有的纸币
if sum==s:
return num
else:
return np.inf
else:#递归的使用剩余的其它纸币
return min(Solve(i+1,sum+a[i],num+1),Solve(i+1,sum,num))
if __name__=="__main__":
print(Solve(0,0,0)) #解为2
讲解：
- Solve(i,sum,num)表示在第i张纸币前，已经抽取了num张纸币，这些纸币的面值之和为sum。在此基础上进行后续的操作。
- （1）如果此时i已经超过了最大的下标n,说明所有的纸币都已经使用过了，那么检验一下sum是否恰好等于s即可。
- （2）如果此时i 没有超过最大下标n，那么考虑是否要抽取ai。
- 1）如果抽取ai，那么sum增加ai，num增加1，调用Solve(i+1,sum+a[i],num+1)即可对后续操作进行求解。
- 2）如果不抽取ai，那么sum和num没有增加，调用Solve(i+1,sum,num)即考虑下一张纸币。
剪枝：如果当前已取的纸币面值之和已经超过s，那么后续的纸币无论怎么取，最终取到的结果都会大于s。在Solve函数稍加修改，就可以避免出现这种情况看。
import numpy as np
n=4;s=10;a=[9,1,6,3]
#搜索算法核心函数
def Solve(i,sum,num):
"""
i,sum,num 表示在第i张纸币前，已经抽取了num张纸币，这些纸币的面值之和为sum。在此基础上进行后续的操作
:param i: int
:param sum: int
:param num: int
:return:
"""
if i==n:#已经使用所有的纸币
if sum==s:
return num
else:
return np.inf
else:#递归的使用剩余的其它纸币
#在这里添加剪枝判断条件
if sum>s:
return np.inf
else:
return min(Solve(i+1,sum+a[i],num+1),Solve(i+1,sum,num))
if __name__=="__main__":
print(Solve(0,0,0))
、
2“油漆桶”与连通性
如果用过windows操作系统中的“画图”程序，那么你一定记得“油漆桶”这个工具，“油漆桶”可以把鼠标单击的色块涂上相同的颜色，计算机是如何计算哪些像素点是属于这个色块的？
例题：给定一张像素图，每个点的颜色用一个整数表示，在画图程序中，鼠标使用“油漆桶”工具单击了其中的一个像素点，求所有被涂色的像素点。
输入格式：第一行为两个整数n,m，表示图片的行数和列数；接下来的n行，每行有m个数字，第i行第j列的数字Cij表示对应位置的像素点颜色；最后一行为两个整数x,y，表示鼠标单击的位置，即第x行第y列（从0开始计数）。
输出格式：输出n行，每行m个字符，用空格隔开，如果一个像素点被涂色，对应位置输出"!",否则对应位置输出“.”。
样例：
输入n=4;m=6;
C=[[1,2,1,1,1,1],[1,2,2,1,1,1],[2,1,1,2,1,1],[1,1,1,2,1,1]]。x=0,y=4;
输出
. . ! ! ! ！
. . . ! ! !
. . . . ! !
. . . . ! !
油漆桶就是鼠标选择一个点然后倒油料，与鼠标单击点所有连通（即同像素点且相连）的点都会被染色。
n=4 #4行
m=6 #6列
vis=[[False for i in range(m)] for j in range(n)] #访问标记初始化False
C=[[1,2,1,1,1,1],[1,2,2,1,1,1],[2,1,1,2,1,1],[1,1,1,2,1,1]]
x=0
y=4
def drop_color(x,y,color):
"""
:param x: int x 第x行
:param y: int y 第y行
:param int color: 鼠标单击的位置xy 处的颜色
:return:
"""
# 越界
if (x < 0 or x >= n or y < 0 or y >= m):
return
#如果当前点已经被访问过，那么不必再次访问
if vis[x][y]==True:
return
#不同色
if C[x][y]!=color:
return
#更新访问标志
vis[x][y]=True
#递归地向四个方向延伸
drop_color(x-1,y,color)
drop_color(x+1, y, color)
drop_color(x, y-1, color)
drop_color(x, y+1, color)
if __name__=="__main__":
drop_color(x,y,C[0][4])
for i in range(n):
result=""
for j in range(m):
if vis[i][j]==False:
result+=". "
else:
result += "! "
print(result)
二 、记忆化
人类在思考问题时，会根据以往的经验作出决策，所谓“以往的经验”就是记忆。举个例子，在计算5X8时，脑海中会立刻出现一句话——“五八四十”即九九乘法口诀，小学时学过的九九乘法口诀已深深地印在每个人的脑海里，每次遇到十以内的乘法时，就会在记忆中取出这部分内容，直接得到结果。
对于计算机而言，也可以实现“记忆”的机制，简单地税，就是把计算机结果存到内存中，需要时直接读取，下面介绍一个简单的例子。
例题：求斐波那契数列的第n项。斐波那契数列是前两项为1，之后的每一项等于前面两项之和 的数列。数学公式表示为：
def F(n):
"""
:param n: int n
:return:
"""
if n==0 or n==1:
return 1
else:
return F(n-2)+F(n-1)
if __name__ =="__main__":
print(F(45))
运行该代码时，发现程序运行了很久。这是因为一些状态被重复计算了，例如，当计算F4时，需要计算F2和F3，当计算F3时，需要计算F1和F2，其中F2计算了两次。当n比较大时，这些重复的冗余计算就会拖垮程序，如果计算时间复杂度，你会发现它达到了惊人的O(2n)。
那么，如何避免重复计算，其实很简单，在首次计算完毕后，将结果存储下来，以后每次需要重复计算时，先检查是否计算过，如果计算过，那么直接把之前存下的计算结果拿来用即可。
F_memory=[0 for i in range(1000)] #1000>=n
def F(n):
"""
:param n: int n
:return:
"""
if n==0 or n==1:
return 1
#在记忆化数组中查找计算结果
elif F_memory[n]!=0:
return F_memory[n]
else:#将计算结果并存储到记忆化数组中
F_memory[n]= F(n-2)+F(n-1)
return F_memory[n]
if __name__ =="__main__":
print(F(45))
三、在游戏中制胜的AI
1 永远的平局——井字棋
例题：在一个3X3的网格中，两位玩家轮流在空位中落字，先手用“○”，后手用“×”，当一方的棋子形成3点一线时，该玩家获胜。现在输入一个棋盘残局，计算必胜的落子位置。
输入格式：首先输入一个整数P，P=1表示当前轮到先手玩家落子，P=2表示当前轮到后手玩家落子；接下来3行，每行3个字符，表示棋盘的状态，其中“.”表示当前没有棋子，“○”表示先手落子，“×”表示后手落子。
输出格式：输出3行，每行3个字符，用空格隔开，如果一个棋盘中一个位置在落子后是必胜的，对应位置输出"!“,否则对应位置输出”."。
样例输入:
1
. X O
. O .
X . .
样例输出：
. . .
. . !
. . !
考虑在对方采取最优策略的情况下本方能否胜出，每个残局都可以是确定是必胜状态、必败状态或是平局状态中的一种。
具体一点，在每一个棋盘下，有以下四种情况。
第1种情况：游戏已经结束，此时可以直接判断胜负。
第2种情况：从当前状态开始，枚举每一个可行的决策，如果能找到一个决策，让对方面临必败的状态，那么当前状态是必胜状态。
第3种情况：从当前状态开始，无论采取什么决策，都无法让对方面临必败状态，但可以领对方面临平局，那么当前状态也是平局状态。
第4种情况：从当前状态开始，无论采取什么决策，都只能让对方面临必胜，那么当前状态是必败状态。
还有一个问题，是否需要记忆化，这就需要思考会不会出现重复状态，实际上会的。
每个格子有3种状态，所有的9个格子，总共有39 =19863种状态，为了方便计算，将一个棋盘的状态当作一个三进制数，就可以将棋盘状态编码为整数，进而可以对该状态的结果进行记忆化处理。
#记忆化数组
memory=[0 for i in range(20000)] #20000>3^9
#棋盘状态
board=[[0 for i in range(3)] for j in range(3)]#3X3的棋盘 #初始化为全0
#编码函数，将棋盘状态编码为整数
def encode():
#编码为三进制数
ans=0
for i in range(3):
for j in range(3):
ans=ans*3+board[i][j]
return ans
#判断游戏是否结束
def game_end():
"""
-1 游戏还未结束
0游戏以平局结束
1先手已获胜
2后手已获胜
:return:
"""
for player in range(1,3):#玩家1,2
#查看该玩家是否存在三点一线
for i in range(3):
#横排三点一线
if (board[i][0]==player) and (board[i][1]==player) and (board[i][2]==player):
return player
# 竖排三点一线
if (board[0][i]==player) and (board[1][i]==player) and (board[2][i]==player):
return player
#正斜三点一线
if (board[0][0]==player) and (board[1][1]==player) and (board[2][2]==player):
return player
# 反斜三点一线
if (board[0][2] == player) and (board[1][1] == player) and (board[2][0] == player):
return player
#没有出现三点一线，检验是否还有空位
for i in range(3):
for j in range(3):
if board[i][j]==0:
return -1 #游戏还未结束
#没有出现三点一线，且没有空位，游戏以平局结束
return 0
#求解当前状态下的胜者
def solve(player):
"""
:param player: int
:return:
"""
#在记忆数组中查找计算结果
if memory[encode()]!=0:
return memory[encode()]
#检验游戏是否结束
if game_end()!=-1:
return game_end()
anther_player=3-player
result=anther_player
#枚举落子位置
for i in range(3):
for j in range(3):
if board[i][j]==0:
#在此处落子
board[i][j]=player
#递归地对另一玩家的状态进行求解
next_result=solve(anther_player)
if next_result==player:
#如果能够令对方面对必败状态，那么此时是必胜状态
result=player
elif next_result==0 and result==anther_player:
#如果不能令对方面对必败状态，那么尽可能争取平局
result=0
#撤回此处的落子，以便尝试在其它落子方式
board[i][j]=0
#将当前状态的计算结果存储到记忆化数组中
memory[encode()]=result
return result
#主函数
def main():
inputs=[[".","X","O"],[".","O","."],["X",".","."]] #残局
player=1#当前轮到先手棋手落子
another_player=3-player #另一个棋手
jieguo=[] #存储结果
for i in range(3):
for j in range(3):
if inputs[i][j]==".":
board[i][j]=0
elif inputs[i][j]=="O":
board[i][j] = 1
else:
board[i][j] = 2
#枚举落子位置，求解胜负状态并输出
for i in range(3):
for j in range(3):
result="." #初始化
if board[i][j]==0:
board[i][j]=player
if solve(another_player)==player:
result="!"
board[i][j] = 0 #赋值为0,进入for循环探索其它落子可能
jieguo.append(result)
#打印结果
for k in range(3):
print(jieguo[k*3+0],jieguo[k*3+1],jieguo[k*3+2])
if __name__ =="__main__":
main()
2 一起来解谜——数独
数独，在一个9X9的网格上，有若干个数字已经填好，玩家需要做的，是在每一个空余的网格中填入1-9中的一个数字，保证每一行，每一列，每一个图中的3X3的网格中不存在重复的数字。
输入格式：输入包含9行，每行9个数字，表示游戏开局的状态，其中0表示空余的网格，1-9表示已经填好的数字。输出填好的网格
inputshuju=[[8,0,0,0,0,0,0,0,0],
[0,0,3,6,0,0,0,0,0],
[0,7,0,0,9,0,2,0,0],
[0,5,0,0,0,7,0,0,0],
[0,0,0,0,4,5,7,0,0],
[0,0,0,1,0,0,0,3,0],
[0,0,1,0,0,0,0,6,8],
[0,0,8,5,0,0,0,1,0],
[0,9,0,0,0,0,4,0,0]]
数独问题与前面的井字棋是完全不同的游戏，在井字棋中，有两位玩家相互博弈，而在数独问题中，只有一位玩家。但这两个游戏的决策过程都可以是序列决策问题。
用搜索算法玩数独游戏时，尝试将每一个数字填到每一个空位中。以样例为例，共有60个空余的网格，可以认为有60个机器人在合力解决输电问题，第一个机器人负责填第1个空位，第2个机器人负责填第2个空位…最后一个机器人填最后一个空位。。
第n个机器人在填数字时，枚举每一个可以填入的数字，填好后交个第n+1个机器人，如果第n个机器人以及后续的其它机器人把剩余的网格填好了，说明已经解决了这个问题。
如果第n+1个机器人以及后续的其他机器人无法填好剩余的网格，说明这时第n个机器人填的数字是错误的，第n个机器人将尝试填入下一个数字。
如果第n个机器人尝试完所有数字后，后续的机器人仍然反馈无法填好剩余的网格，说明前n-1个机器人出错了，第n个机器人将信息反馈给第n-1个机器人即可。
在数独游戏中，不会出现重复的状态，因此不需要记忆化。
import sys
sys.setrecursionlimit(100000) #例如这里设置递归深度为十万
#数独a
a=[[8,0,0,0,0,0,0,0,0],
[0,0,3,6,0,0,0,0,0],
[0,7,0,0,9,0,2,0,0],
[0,5,0,0,0,7,0,0,0],
[0,0,0,0,4,5,7,0,0],
[0,0,0,1,0,0,0,3,0],
[0,0,1,0,0,0,0,6,8],
[0,0,8,5,0,0,0,1,0],
[0,9,0,0,0,0,4,0,0]]
#判断空位能否填数字
def canFill(x,y,n):
"""
:param x: int 横坐标
:param y: int 纵坐标
:param n: int 填写数字n
:return:
"""
#查验当前行是否有重复数字
for i in range(9):#
if a[x][i]==n:#a为数独列表
return False
# 查验当前列是否有重复数字
for i in range(9):
if a[i][y]==n:#a为数独列表
return False
#查验前3*3网格中是否有重复数字
px=0;py=0
if x<=2:#0,1,2
px=0
elif x<=5:#3,4,5
px=3
else:#6,7,8
px=6
if y<=2:#0,1,2
py=0
elif y<=5:#3,4,5
py=3
else:#6,7,8
py=6
for i in range(3):#0,1,2
for j in range(3):
if a[px+i][py+j]==n:
return False
#返回游戏规则，当前位置可以填写数字n
return True
#用深度优先搜索算法尝试填写数字
def dfs():
#枚举每一个网格位置
for i in range(9):
for j in range(9):
if a[i][j]!=0:#如果已经填写过数字，跳过
continue
#找到第1个空位，枚举1-9每一个数字，尝试填入
for n in range(1,10):#
#如果可以填写该数字
if canFill(i,j,n):
#填写该数字，更新网格状态
a[i][j]=n
#把网格交个后续的机器人，如果后续的机器人能填好，返回True
if dfs():
return True
#如果后续的机器人不能填好，撤回刚刚填写的数字n，尝试填入其他数字
a[i][j]=0
return False #表示填写1-9都不满足
return True
if __name__ =="__main__":
dfs()
for i in range(9):
print(a[i][:])
3 数字华容道
在一个3X3的网格中有8个拼图碎片（1,2,3,4,5,6,7,8）以及一个空余网格(0),每一步只能将与空余网格相邻的一个拼图碎片平移到空余网格中，请你计算至少要多少步才能将拼图复原。
样例输入：
3 0 2
4 1 7
6 8 5
样例输出7
如果按照深度优先搜索的方式进行求解，那么确实可以找到复原拼图的方法，但没办法保证是步数最少的方法，此时需要换一种搜索的方法——广度优先搜索。
如果是深度优先搜索，前几个状态的顺序如图：
如果改变搜索顺序，先遍历一步就能达到的状态，再遍历两步能够达到的状态，然后遍历三步能达到的状态…保证不重复走任何一个状态，那么就能保证达到每一个状态是经过最少步数到达的。
那么如何实现这个过程，暂时抛弃函数的递归，借助队列这一数据结构来实现，每当遇到一个新的状态，就把这个状态放进队列中，依次处理队列中的每一个状态，直到得到答案或队列清空。
最开始队列中只有一个状态，就是初始状态，是0步可以达到的状态。
然后把排在队首的状态取出，它能够达到三个状态，这三个状态是走1步可以达到的状态，把这三个状态放进队列的末尾，等待后续处理。如图4.24。
此时队列还未清空，再次取出排在队首的状态，它可以达到两个状态，但其中一个状态已经遍历过，将其跳过，把另一个没有遍历过的状态放进队列，如图4.25。
重复这个过程，每次取出队首的状态，把它后续状态中没有遍历过的放入队尾，直到出现拼图复原的状态。如果直到队列清空拼图都未复原，那么这个拼图游戏是无法复原的。
此外，在代码中，需要判断一个状态是否曾经被遍历过，以及记录每个状态被遍历时的最小步数，所以需要把每个状态编码成一个整数。总共的状态数就是9个元素的排列数，也就是9!=362880，所以把所有状态存下来是完全可行的。
import copy
#初始化拼图矩阵 1-8表示拼图碎片，0表示空余网格
Board=[[3,0,2],[4,1,7],[6,8,5]]
#将当前状态编码为一个整数
def encode(board):
"""
:param board: 拼图矩阵
:return:
"""
ans=0
for i in range(3):
for j in range(3):
ans=ans*9+board[i][j]
return ans
#判断当前的拼图是否已经复原
def win(board):
for i in range(3):
for j in range(3):
if board[i][j]!=i*3+j:
return False
return True
#===============广度优先搜索================
q=[] #初始化队列
step={} #一个空字典，用于判断一个状态是否曾被遍历过，以及记录每个状态被编码时的最小步骤
dx=[-1,0,1,0];dy=[0,-1,0,1] #四个移动方向（-1,0);(0,-1);(1,0);(0,1)
#广度优先搜索
def bfs(Board): #将Board添加进队尾):
#处理初始状态
q.append(Board) #将Board添加进队尾
step[encode(Board)]=0 #该状态未被遍历过，记录为0
#开始广度优先搜索
while len(q)>0:
#取出队首的状态
Board=q[0]
q.pop(0)
#如果拼图已经复原，直接结束搜索
if win(Board):
return step[encode(Board)]
#当前状态所需的最小步数
now_step=step[encode(Board)]
#找到空余网格的位置
for i in range(3):
for j in range(3):
if Board[i][j]==0:
#枚举空余网格的上下左右四个方向
for d in range(4):
x=i+dx[d]
y=j+dy[d]
if x<0 or x>2 or y<0 or y>2:
continue
#把对应方向的拼图碎片移动过来，得到后续状态
Board[i][j],Board[x][y]=Board[x][y],Board[i][j]
#如果后续状态没有被遍历过，放入队列中
if encode(Board) not in step.keys():
q.append(copy.deepcopy(Board)) #深复制，必须深复制，不然后面“复原状态”会修改q中的Board
step[encode(Board)]=now_step+1
#复原状态
Board[i][j], Board[x][y] = Board[x][y], Board[i][j]
#如果直到队列清空队列都未复原，那么这个游戏是无法复原的
return -1
if __name__=="__main__":
print(bfs(Board)) #将Board添加进队尾)) #结果为7
原文地址：https://blog.csdn.net/kobeyu652453/article/details/142727746
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！