算法竞赛（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张纸币有2ⁿ ,所以可行解的数量为2ⁿ 。接下来考虑如何将2ⁿ 种可行解遍历一面，如果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 numelse:return np.infelse:#递归的使用剩余的其它纸币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 numelse:return np.infelse:#递归的使用剩余的其它纸币#在这里添加剪枝判断条件if sum>s:return np.infelse: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 1else:return F(n-2)+F(n-1)if __name__ =="__main__":print(F(45))

   运行该代码时，发现程序运行了很久。这是因为一些状态被重复计算了，例如，当计算F4时，需要计算F2和F3，当计算F3时，需要计算F1和F2，其中F2计算了两次。当n比较大时，这些重复的冗余计算就会拖垮程序，如果计算时间复杂度，你会发现它达到了惊人的O(2ⁿ)。

   那么，如何避免重复计算，其实很简单，在首次计算完毕后，将结果存储下来，以后每次需要重复计算时，先检查是否计算过，如果计算过，那么直接把之前存下的计算结果拿来用即可。

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个格子，总共有3⁹ =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=0for 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-playerresult=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=playerelif next_result==0 and result==anther_player:#如果不能令对方面对必败状态，那么尽可能争取平局result=0#撤回此处的落子，以便尝试在其它落子方式board[i][j]=0#将当前状态的计算结果存储到记忆化数组中memory[encode()]=resultreturn 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]=0elif inputs[i][j]=="O":board[i][j] = 1else:board[i][j] = 2#枚举落子位置，求解胜负状态并输出for i in range(3):for j in range(3):result="." #初始化if board[i][j]==0:board[i][j]=playerif 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=0if x<=2:#0,1,2px=0elif x<=5:#3,4,5px=3else:#6,7,8px=6if y<=2:#0,1,2py=0elif y<=5:#3,4,5py=3else:#6,7,8py=6for i in range(3):#0,1,2for j in range(3):if a[px+i][py+j]==n:return False#返回游戏规则，当前位置可以填写数字nreturn 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#把网格交个后续的机器人，如果后续的机器人能填好，返回Trueif dfs():return True#如果后续的机器人不能填好，撤回刚刚填写的数字n，尝试填入其他数字a[i][j]=0return False #表示填写1-9都不满足return Trueif __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=0for 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 Falsereturn 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中的Boardstep[encode(Board)]=now_step+1#复原状态Board[i][j], Board[x][y] = Board[x][y], Board[i][j]#如果直到队列清空队列都未复原，那么这个游戏是无法复原的return -1if __name__=="__main__":print(bfs(Board)) #将Board添加进队尾)) #结果为7