昨天和朋友出去吃饭，吃完饭朋友打开小程序玩...游戏看起来是这样的：从猫在地图上的位置开始，穿过所有的格子。游戏还是挺有意思的，经过我的不断努力，终于过了30级。而且随着游戏关卡的增加，游戏的难度也越来越难，通关需要非常长的时间。最近刚好在研究算法，于是决定看看能不能写一个通用的算法，求出每张图的解。柯尼斯堡的《七桥问题》这款游戏的玩法有点类似于柯尼斯堡的《七桥问题》。柯尼斯堡的“七桥问题”：18世纪著名的经典数学问题之一。在K?nigsberg的一个公园里，七座桥梁将Pregel河中的两个岛屿和岛屿连接到河岸（如下图）。是否可以从这四块土地中的任何一块开始，通过每座桥恰好一次，然后返回起点？当时人们想到的证明方法是把七座桥都列出来，一一检验，利用排列组合的知识很容易得出，大概有7座！=5040种移动所有七座桥的方法。如果真的一一尝试，工作量会很大。但数学家欧拉并不这样认为。欧拉将两个岛屿和河岸抽象为顶点，将七座桥抽象为连接每个顶点的七条边。那么这个问题可以抽象成下图：假设每座桥正好通过一次，那么对于A、B、C、D四个顶点中的每一个，都需要从某条边进入，从另一条边离开同时，并且进入和离开该顶点的次数相同，即每个顶点的入边数与出边数一样多。也就是说：与每个顶点相连的边都是成对出现的，即每个顶点的相连边数必须是偶数。显然，上图中A、C、D三个顶点相连的边有3条，与顶点B相连的边有5条，都是奇数。因此，该图不能从一个顶点开始并恰好通过每座桥一次。由此证明，人们又得到了欧拉路关系。要使一个图形可以一笔画出，必须满足以下两个条件：图形必须是连通的，不能有孤立的点。连通边数为奇数的图中的顶点必须为0或2。对于连通图，从某个节点画出的路线通常称为欧拉路。那么这个博弈是否能让我们找到一条欧拉路呢？抽象游戏根据上面证明七桥问题的方法，我们可以抽象出游戏的地图如下：顶点14是起点。顶点和边的关系在程序中可以描述为一个二维表。graph=[[1,6],#0[0,2],#1[1,7,3],#2...[24,19]#25]graphlist的第一层代表每个顶点，第二层是与当前顶点有边的顶点。把这个博弈图抽象出来之后，很明显这个博弈并不能让我们找到一条欧拉路。因为要找到一条欧拉路，需要经过每一座桥，而且只有一次，也就是说每个顶点都可以经过多次。而且这个游戏需要遍历每一个顶点，而不是每一座桥，而且顶点只能通过一次。研究了七桥问题，发现解决不了这种问题，就开始向队里的表哥请教。一位表哥跟我说，这种问题叫做哈密顿图（感谢团队的**@xq17**表哥）。这里所说的哈密顿图实际上是哈密顿路径的一种特例，指的是：从指定的起点开始，途中经过所有其他顶点且只经过一次，最后回到起点，称为汉密尔顿赛道。如果给定图G具有哈密顿环，则称其为哈密顿图。所以既然目标明确了，这个博弈的解法就是找到给定图的哈密顿路径。但是问题来了！！！哈密??顿路径问题，在20世纪70年代初期，被证明是一个NP-hard问题：如果一个复杂的问题可以在多项式时间内解决，它就被称为P型问题。如果一个复杂问题不能在多项式时间内确定地解决，则称它为NP。这意味着什么？以质因数分解为例：P型问题：23x37=?NP型问题：给定axb=740914799，并且a和b都是质数，求a和b的值我们来看看这个问题有多复杂：因为axb=740914799，而且a和b都是质数，设P={x|2<=x<740914799/2,x是质数}，很容易得到(a,b)∈PxP，即P和它自己的笛卡尔积我们用到一个叫做sieve的算法求P集中元素个数的方法：#!/usr/bin/envpython#-*-coding:utf-8-*-#CodingwithlovebyNaiquan.importmathimporttimestart=time.clock()number=int(740914799/2)marks_list=[True]*(number+1)marks_list[0]=marks_list[1]=Falseforiinrange(2,int(math.sqrt(number))+1):j=it=j#去掉multiplewhilej*t<=number:marks_list[j*t]=Falset+=1elapsed=str(time.clock()-start)printmarks_list.count(True)print"Timeused:"+elapsed一共有19841519个质数，我猜大概有14个分钟。PxP一共有19841519^2个元素。要一一验证它们是否等于740914799，无疑是一项大工程。这是一个典型的NP问题。NP型问题虽然困难，但可以快速验证给定的答案是否正确。比如上面的问题，我告诉你答案a=22229，b=33331，你可以快速验证答案是否正确。NP-hard问题就是比NP问题更难的问题，比如：围棋。也就是说，找不到友好的算法来解决哈密顿路径问题。算法设计虽然求一个图的哈密顿路径是NP难的，但好在博弈中的顶点不多，可以用更暴力的方法来实现，例如：深度优先遍历法（DFS）的图是递归和回溯的思想。算法流程：①将当前顶点压入访问栈和路径栈。②列出与当前顶点相连的顶点。③随机选取一个连通顶点，判断该顶点是否在访问栈中：在访问栈中，取另一个连通顶点。如果不是，则使用这个连接的顶点作为当前顶点。如果所有连通的顶点都在访问栈中，则判断路径栈是否包含所有顶点。路径栈包含所有的顶点，路径栈就是当前图的哈密顿路径。如果不包含所有顶点，则返回父顶点并将其从访问栈和路径栈中删除。④重复步骤1~3。算法实现上面提到，图的顶点和边的关系可以用一个二维列表来描述：graph=[[1,6],#0[0,2],#1[1,7,3],#2...[24,19]#25]但是手动输入这些顶点和边的关系太麻烦了。仔细一想，如果每个顶点的上下左右都有顶点，那它必然有与上下左右顶点的边。那么这个二维列表可以简化为graph=[[1,1,1,1,1,1],[1,0,1,1,0,1],[1,1,1,1,1,1],[1,0,1,1,0,1],[1,1,1,1,1,1],[0,0,0,0,0,0]#每个1代表一个顶点1有边有1，上下左右，没有长宽等于0的。代码方便]也可以简化成一维列表：graph=['111111','101101','111111','101101','111111','000000']和我一样机智！所以我写了一个函数来转换一维列表：defget_index(i,j,G):num=0forrainxrange(i):num+=G[a].count('0')forbinxrange(j):ifG[i][b]=='0':num+=1returni*len(G)+j-numdefget_graph(G):G=[list(x)forxinG]EG=[]foriinxrange(len(G)):forjinrange(len(G[i])):ifG[i][j]=='0':continueside_list=[]ifj+1<=len(G[i])-1:ifG[i][j+1]=='1':index=get_index(i,j+1,G)side_list.append(index)ifj-1>=0:ifG[i][j-1]=='1':index=get_index(i,j-1,G)side_list.append(index)ifi+1<=len(G)-1:ifG[i+1][j]=='1':index=get_index(i+1,j,G)side_list.append(index)ifi-1>=0:ifG[i-1][j]=='1':index=get_index(i-1,j,G)side_list.append(index)EG。append(side_list)returnEG和图的邻接矩阵实现算法比较方便，所以我写了一个函数将上面的两位list转为邻接矩阵的形式：defget_matrix(graph):result=[[0]*len(graph)for_inxrange(len(graph))]#initializationforiinxrange(len(graph)):forjingraph[i]:result[i][j]=1#如果有边则为1returnresult主要的DFS算法如下：#graph是使用的图的邻接矩阵是visitedstackpath是stackstep遍历的路径顶点个数defdfs(graph,path,used,step):ifstep==len(graph):#判断顶点是否遍历printpathreturnTrueelse:foriinxrange(len(graph)):ifnotused[i]andgraph[path[step-1]][i]==1:used[i]=Truepath[step]=iifdfs(graph,path,used,step+1):returnTrueelse:used[i]=False#回溯返回父节点path[step]=-1returnFalsedefmain(graph,v):used=[]#visitedstackpath=[]#pathstackforiinxrange(len(graph)):used.append(False)#initialized所有的顶点都没有遍历过path.append(-1)#初始化未选择的起点，到达任何使用的顶点[v]=True#表示从起点开始遍历path[0]=v#表示第一个顶点哈密??顿路径是起点dfs(graph,path,used,1)Thecomple代码如下：#!/usr/bin/envpython#-*-coding:utf-8-*-#CodingwithlovebyNaiquan.defdfs(graph,path,used,step):ifstep==len(graph):printpathreturn否则为真：foriinxrange(len(graph)):ifnotused[i]andgraph[path[step-1]][i]==1:used[i]=Truepath[step]=iifdfs(graph,path,used,step+1):returnTrueelse:used[i]=Falsepath[step]=-1returnFalsedefmain(graph,v):used=[]path=[]foriinxrange(len(graph)):used.append(False)path.append(-1)used[v]=Truepath[0]=vdfs(graph,path,used,1)defget_index(i,j,G):num=0forainxrange(i):num+=G[a.count('0')forbinxrange(j):ifG[i][b]=='0':num+=1returni*len(G)+j-numdefget_graph(G):G=[list(x)forxinG]EG=[]foriinxrange(len(G)):forjinrange(len(G[i])):ifG[i][j]=='0':continueside_list=[]ifj+1<=len(G[i])-1:ifG[i][j+1]=='1':index=get_index(i,j+1,G)side_list.append(index)ifj-1>=0:ifG[i][j-1]=='1':index=get_index(i,j-1,G)side_list.append(index)ifi+1<=len(G)-1:ifG[i+1][j]=='1':index=get_index(i+1,j,G)side_list.append(index)ifi-1>=0:ifG[i-1][j]=='1':index=get_index(i-1,j,G)side_list.append(索引)EG.append(side_list)returnEGdefget_matrix(graph):result=[[0]*len(graph)for_inxrange(len(graph))]foriinxrange(len(graph)):forjingraph[i]:result[i][j]=1returnresultif__name__=='__main__':map_list=['111111','101101','111111','101101','111111','000000']G=get_graph(map_list)map_matrix=get_matrix(G)#printmap_matrixSP=14main(map_matrix,SP)结果实现了AfterIwasable,Isuccessfullypassedalmostahundredlevelswiththisprogram,andthenIgottiredofplaying,haha??hahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahahaBridgeproblem/2580504?fr=aladdinHamiltondiagram_BaiduEncyclopediahttps://baike.baidu.com/item/Hamiltondiagram/2587317?fr=aladdin这道数学题我会做，但世界毁灭别怪我https://www.bilibili.com/video/av19009866基于回溯法求哈密顿回路http:///www.cnblogs.com/cielosun/p/5654577.html
