威海住房和城乡建设厅网站,沧州贴吧,安装wordpress错误,网站备案专员文章目录 一 、深度优先搜索1 零钱搭配2“油漆桶”与连通性 二 、记忆化三、在游戏中制胜的AI1 永远的平局——井字棋2 一起来解谜——数独3 数字华容道 一 、深度优先搜索 深度优先搜索是最基本的搜索方法#xff0c;在深度优先搜索的过程中#xff0c;如果把所有的可行解看… 文章目录 一 、深度优先搜索1 零钱搭配2“油漆桶”与连通性 二 、记忆化三、在游戏中制胜的AI1 永远的平局——井字棋2 一起来解谜——数独3 数字华容道 一 、深度优先搜索 深度优先搜索是最基本的搜索方法在深度优先搜索的过程中如果把所有的可行解看作一个空间求解的过程就是在空间中游走的过程当走到尽头无路可走时就会后退进而寻找其它可行解。 在搜索中可以通过灵活的“剪枝”操作缩短可行解的范围。
1 零钱搭配 l烈日炎炎的夏天小余在陪朋友逛街当路过一家奶茶店时想要买价格为s元的冰奶茶但是出门时小余忘记带手机了钱包里只有n张纸币面值分别为a0,a1,a2…an-1小余要从这些纸币中挑选k张来支付这k张纸币的面值之和恰好为s元同时为了避免麻烦小余希望能够用最少的纸币来付钱也就是让k最小。请你设计一个程序计算出最小的k。 输入格式 第一行为两个整数ns第2行为n个整数a0,a1…an-1。 输出格式 输出一个整数最小的k。 样例输入n4,s10;a[9,1,6,3] 输出2。 在本问题中每一张纸币有“取”和不取”两种情况所有的n张纸币有2n ,所以可行解的数量为2n 。接下来考虑如何将2n 种可行解遍历一面如果n是个定值那么写n个for循环层层嵌套。不过在本问题中n是一个变量在输入具体数值前并不知道要写几层for循环所以需要借助函数的递归来实现。
import numpy as np
n4;s10;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 in:#已经使用所有的纸币if sums:return numelse:return np.infelse:#递归的使用剩余的其它纸币return min(Solve(i1,suma[i],num1),Solve(i1,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增加ainum增加1调用Solve(i1,suma[i],num1)即可对后续操作进行求解。2如果不抽取ai那么sum和num没有增加调用Solve(i1,sum,num)即考虑下一张纸币。 剪枝如果当前已取的纸币面值之和已经超过s那么后续的纸币无论怎么取最终取到的结果都会大于s。在Solve函数稍加修改就可以避免出现这种情况看。
import numpy as np
n4;s10;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 in:#已经使用所有的纸币if sums:return numelse:return np.infelse:#递归的使用剩余的其它纸币#在这里添加剪枝判断条件if sums:return np.infelse:return min(Solve(i1,suma[i],num1),Solve(i1,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个字符用空格隔开如果一个像素点被涂色对应位置输出!,否则对应位置输出“.”。 样例 输入n4;m6; 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]]。x0,y4; 输出 . . ! ! ! . . . ! ! ! . . . . ! ! . . . . ! ! 油漆桶就是鼠标选择一个点然后倒油料与鼠标单击点所有连通即同像素点且相连的点都会被染色。
n4 #4行
m6 #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]]
x0
y4
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(x1, y, color)drop_color(x, y-1, color)drop_color(x, y1, color)if __name____main__:drop_color(x,y,C[0][4])for i in range(n):resultfor 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 n0 or n1:return 1else: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)] #1000n
def F(n)::param n: int n:return:if n0 or n1: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点一线时该玩家获胜。现在输入一个棋盘残局计算必胜的落子位置。 输入格式首先输入一个整数PP1表示当前轮到先手玩家落子P2表示当前轮到后手玩家落子接下来3行每行3个字符表示棋盘的状态其中“.”表示当前没有棋子“○”表示先手落子“×”表示后手落子。 输出格式输出3行每行3个字符用空格隔开如果一个棋盘中一个位置在落子后是必胜的对应位置输出!“,否则对应位置输出”.。 样例输入: 1 . X O . O . X . . 样例输出 . . . . . ! . . ! 考虑在对方采取最优策略的情况下本方能否胜出每个残局都可以是确定是必胜状态、必败状态或是平局状态中的一种。 具体一点在每一个棋盘下有以下四种情况。 第1种情况游戏已经结束此时可以直接判断胜负。 第2种情况从当前状态开始枚举每一个可行的决策如果能找到一个决策让对方面临必败的状态那么当前状态是必胜状态。 第3种情况从当前状态开始无论采取什么决策都无法让对方面临必败状态但可以领对方面临平局那么当前状态也是平局状态。 第4种情况从当前状态开始无论采取什么决策都只能让对方面临必胜那么当前状态是必败状态。 还有一个问题是否需要记忆化这就需要思考会不会出现重复状态实际上会的。 每个格子有3种状态所有的9个格子总共有39 19863种状态为了方便计算将一个棋盘的状态当作一个三进制数就可以将棋盘状态编码为整数进而可以对该状态的结果进行记忆化处理。 #记忆化数组
memory[0 for i in range(20000)] #200003^9
#棋盘状态
board[[0 for i in range(3)] for j in range(3)]#3X3的棋盘 #初始化为全0
#编码函数将棋盘状态编码为整数
def encode():#编码为三进制数ans0for i in range(3):for j in range(3):ansans*3board[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_player3-playerresultanther_player#枚举落子位置for i in range(3):for j in range(3):if board[i][j]0:#在此处落子board[i][j]player#递归地对另一玩家的状态进行求解next_resultsolve(anther_player)if next_resultplayer:#如果能够令对方面对必败状态那么此时是必胜状态resultplayerelif next_result0 and resultanther_player:#如果不能令对方面对必败状态那么尽可能争取平局result0#撤回此处的落子以便尝试在其它落子方式board[i][j]0#将当前状态的计算结果存储到记忆化数组中memory[encode()]resultreturn result#主函数def main():inputs[[.,X,O],[.,O,.],[X,.,.]] #残局player1#当前轮到先手棋手落子another_player3-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*30],jieguo[k*31],jieguo[k*32])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个机器人在填数字时枚举每一个可以填入的数字填好后交个第n1个机器人如果第n个机器人以及后续的其它机器人把剩余的网格填好了说明已经解决了这个问题。 如果第n1个机器人以及后续的其他机器人无法填好剩余的网格说明这时第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网格中是否有重复数字px0;py0if x2:#0,1,2px0elif x5:#3,4,5px3else:#6,7,8px6if y2:#0,1,2py0elif y5:#3,4,5py3else:#6,7,8py6for i in range(3):#0,1,2for j in range(3):if a[pxi][pyj]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:ans0for i in range(3):for j in range(3):ansans*9board[i][j]return ans#判断当前的拼图是否已经复原
def win(board):for i in range(3):for j in range(3):if board[i][j]!i*3j: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:#取出队首的状态Boardq[0]q.pop(0)#如果拼图已经复原直接结束搜索if win(Board):return step[encode(Board)]#当前状态所需的最小步数now_stepstep[encode(Board)]#找到空余网格的位置for i in range(3):for j in range(3):if Board[i][j]0:#枚举空余网格的上下左右四个方向for d in range(4):xidx[d]yjdy[d]if x0 or x2 or y0 or y2: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_step1#复原状态Board[i][j], Board[x][y] Board[x][y], Board[i][j]#如果直到队列清空队列都未复原那么这个游戏是无法复原的return -1if __name____main__:print(bfs(Board)) #将Board添加进队尾)) #结果为7
