Py学习  »  Python

抖音超火游戏《一笔画完》!到处求教程?我用Python玩通关!

Python学习交流 • 5 年前 • 529 次点击  


私信小编01 02 03 04 05 06即可获取数数十套PDF哦!

游戏长这样










  • 图形必须是连通的不能有孤立的点。

  • 图中拥有奇数连接边的点必须是 0 或 2。

对于一个连通图,通常把从某结点出发一笔画成所经过的路线叫做欧拉路。那么这个游戏是不是就是让我们找到一条欧拉路呢?


对游戏进行抽象





按照上面证明七桥问题的方法,我们可以将游戏的地图抽象成这样:

  • 其中 14 号顶点为起点。

  • 顶点和边的关系在程序中可以刻画成一个二维列表。

graph = [
[1, 6], #0
[0, 2], #1
[1, 7, 3], #2
...
[24, 19] #25
]

graph 列表的第一层表示每一个顶点,第二层则是与当前顶点有边的顶点。


抽象完这张游戏地图后可以很清楚知道,这游戏并不是让我们找到一条欧拉路。

因为找到一条欧拉路,需要的是经过每一座桥,且只经过一次,也就是说每个顶点可以被多次经过。

而这个游戏需要的是经过每一个顶点,并不要求走完每一座桥,且顶点只能被经过一次。

哈密顿通路

在研究了七桥问题发现并不能解决这类问题后,我开始向团队的表哥们请教,其中一个表哥告诉我此类问题叫做哈密顿图 (这里感谢下团队的**@xq17**表哥)。





这里说的哈密顿图,实际上是哈密顿通路的一种特殊情况,指的是:由指定的起点出发,途中经过所有其他顶点且只经过一次 ,最后返回起点,称之为哈密顿回路。如果给定的图 G 具有哈密顿回路,则称图 G 为哈密顿图。



#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Coding with love by Naiquan.
import math
import time
start = time.clock()
number = int(740914799/2)
marks_list = [True] * (number + 1)
marks_list[0] = marks_list[1] = False
for i in range(2, int(math.sqrt(number)) + 1):
j = i
t = j
# 去掉倍数
while j * t <= number:
marks_list[j * t] = False
t += 1
elapsed = str(time.clock() - start)
print marks_list.count(True)
print "Time used:" + 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'
]


简直机智如我啊!于是我写了个函数对一维列表进行转换:

def get_index(i, j, G):
num = 0
for a in xrange(i):
num += G[a].count('0')
for b in xrange(j):
if G[i][b] == '0':
num += 1
return i * len(G) + j - num
def get_graph(G):
G = [list(x) for x in G]
EG = []
for i in xrange(len(G)):
for j in range(len(G[i])):
if G[i][j] == '0':
continue
side_list = []
if j+1 <= len(G[i]) - 1:
if G[i][j+1] == '1':
index = get_index(i, j+1, G)
side_list.append(index)
if j-1 >= 0:
if G[i][j-1] == '1':
index = get_index(i, j-1, G)
side_list.append(index)
if i+1 <= len(G) - 1:
if G[i+1][j] == '1':
index = get_index(i+1, j, G)
side_list.append(index)
if i-1 >= 0:
if G[i-1][j] == '1':
index = get_index(i-1, j, G)
side_list.append(index)
EG.append(side_list)
return EG




而算法的实现用图的邻接矩阵则更为方便,因此我写了一个将上列二位列表转换成邻接矩阵形式的函数:

def get_matrix(graph):
result = [[0]*len(graph) for _ in xrange(len(graph))] # 初始化
for i in xrange(len(graph)):
for j in graph[i]:
result[i][j] = 1 # 有边则为1
return result




主要的 DFS 算法如下:

# graph为图的邻接矩阵 used为已访问栈 path为路径栈 step为已经遍历的顶点的个数
def dfs(graph, path, used, step):
if step == len(graph): # 判断顶点是否被遍历完毕
print path
return True
else:
for i in xrange(len(graph)):
if not used[i] and graph[path[step-1]][i] == 1:
used[i] = True
path[step] = i
if dfs(graph, path, used, step+1):
return True
else:
used[i] = False # 回溯 返回父节点
path[step] = -1
return False
def main(graph, v):
used = [] # 已访问栈
path = [] # 路径栈
for i in xrange(len(graph)):
used.append(False) # 初始化 所有顶点均未被遍历
path.append(-1) # 初始化 未选中起点及到达任何顶点
used[v] = True # 表示从起点开始遍历
path[0] = v # 表示哈密顿通路的第一个顶点为起点
dfs(graph, path, used, 1)

完整代码如下:

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Coding with love by Naiquan.
def dfs(graph, path, used, step):
if step == len(graph):
print path
return True
else:
for i in xrange(len(graph)):
if not used[i] and graph[path[step-1]][i] == 1:
used[i] = True
path[step] = i
if dfs(graph, path, used, step+1):
return True
else:
used[i] = False
path[step] = -1
return False
def main(graph, v):
used = []
path = []
for i in xrange(len(graph)):
used.append(False)
path.append(-1)
used[v] = True
path[0] = v
dfs(graph, path, used, 1)
def get_index(i, j, G):
num = 0
for a in xrange(i):
num += G[a].count('0')
for b in xrange(j):
if G[i][b] == '0':
num += 1
return i * len(G) + j - num
def get_graph(G):
G = [list(x) for x in G]
EG = []
for i in xrange(len(G)):
for j in range(len(G[i])):
if G[i][j] == '0':
continue
side_list = []
if j+1 <= len(G[i]) - 1:
if G[i][j+1] == '1':
index = get_index(i, j+1, G)
side_list.append(index)
if j-1 >= 0:
if G[i][j-1] == '1':
index = get_index(i, j-1, G)
side_list.append(index)
if i+1 <= len(G) - 1:
if G[i+1][j] == '1':
index = get_index(i+1, j, G)
side_list.append(index)
if i-1 >= 0:
if G[i-1][j] == '1':
index = get_index(i-1, j, G)
side_list.append(index)
EG.append(side_list)
return EG
def get_matrix(graph):
result = [[0]*len(graph) for _ in xrange(len(graph))]
for i in xrange(len(graph)):
for j in graph[i]:
result[i][j] = 1
return result
if __name__ == '__main__':
map_list = [
'111111',
'101101',
'111111',
'101101',
'111111',
'000000'
]
G = get_graph(map_list)
map_matrix = get_matrix(G)
# print map_matrix
SP = 14
main(map_matrix, SP)





结束




在实现了功能后,我拿着这个程序成功过到了差不多一百关,然后就玩腻了,哈哈哈哈哈哈哈哈哈



今天看啥 - 高品质阅读平台
本文地址:http://www.jintiankansha.me/t/4RCwkRtq3y
Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/25505
 
529 次点击