黑客意志

Python系列——一笔画问题的算法研究

0x00 一笔画完游戏

昨天和朋友出去外面吃饭 吃完饭后朋友打开了一个小程序玩了起来

游戏长这样

大概玩法是 从地图中猫的位置开始出发 并且经过所有的格子就算过关 游戏还算挺有意思的 经过我的不断努力 终于过到了 30 来关的样子

并且随着游戏关卡的增加 游戏难度 也变得越来越大 过一关需要非常久的时间

最近也正好在研究算法 就打算看能不能写个 通用 的算法来找出每个地图的

0x01 哥尼斯堡的”七桥问题”

这个游戏的玩法和 哥尼斯堡的”七桥问题” 有点类似

18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?

当时人们想到的证明方法是把七座桥的走法都列出来 一个一个 试验

排列组合的知识很容易得到 七座桥所有的走法大概有 7!=5040 种 如果真的逐一试验 会是个很大的工作量

但数学家欧拉没有这样想 欧拉把 两座岛和河两岸 抽象成 顶点 七座桥 抽象成连接 每个顶点七条边 那么这个问题就能被抽象成下面的图

假设每座桥都恰好走过一次 那么对于A、B、C、D四个顶点中的每一个顶点 需要从某条边进入 同时从另一条边离开 进入和离开顶点的次数是相同的 即每个顶点有多少条进入的边 就有多少条出去的边 也就是说 每个顶点相连的边是成对出现的 即每个顶点的相连边的数量必须是偶数

很明显 上图中A、C、D三个顶点相连的边都有 3条 B顶点的相连边为 5条 都是 奇数 因此这个图无法从一个顶点出发 且恰好走过每座桥一次

由此次证明人们又得到了欧拉路关系 要使得一个图形可以一笔画完 必须满足如下两个条件 图形必须是连通的 不能有孤立的点 图中拥有奇数连接边的点 必须是0或2

对于一个连通图 通常把从某结点出发一笔画成所经过的路线叫做欧拉路

那么这个游戏是不是就是让我们找到一条欧拉路呢?

0x02 对游戏进行抽象

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

其中14号顶点为起点

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

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

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

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

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

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

0x03 哈密顿通路

在研究了七桥问题发现并不能解决这类问题后 我开始向团队的表哥们请教

其中一个表哥告诉我此类问题叫做哈密顿图 (这里感谢下团队的@xq17表哥)

这里说的哈密顿图实际上是哈密顿通路的一种特殊情况 这种特殊情况指的是

由指定的起点出发 途中经过所有其他顶点且只经过一次 最后返回起点 称之为哈密顿回路 如果给定的图G具有哈密顿回路 则称图G哈密顿图

那么现在目标明确了 这个游戏的解法就是找到某个给定图的哈密顿通路

但是!!!但是来了!!!

哈密顿通路问题 在上世纪七十年代初 被证明是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与它自身的笛卡尔积

我们用一种叫做筛法的算法来求一下P集合的元素个数

#! /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问题更难的问题 例如围棋

也就是说并不能找到一个友好的算法来解决哈密顿通路问题

0x04 算法设计

虽然找到一个图的哈密顿通路NP困难的 但是好在游戏中的顶点不算太多 还是可以使用暴力一点的方法实现的

例如 图的深度优先遍历法(dfs)递归和回溯法思想

算法流程 1. 将当前顶点压入已访问栈和路径栈中 - 将与当前顶点相通的顶点列出来 - 随机选取一个相通的顶点 并判断此顶点是否在已访问栈中 * 在已访问栈中则取另一个相通的顶点 * 不在则将这个相通的顶点作为当前顶点 * 若所有相通的顶点都在已访问栈中 则判断路径栈是否包含所有顶点 * 路径栈中包含所有顶点 则路径栈为当前图的哈密顿通路 * 不包含所有顶点则回到父顶点 并从已访问栈和路径栈中删除 - 反复执行1~3

0x05 算法实现

上面说过图的顶点和边的关系可以用一个二维列表来描述

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)

0x06 结束

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

0x07 本文参考资料

  1. 七桥问题_百度百科
  2. 哈密顿图_百度百科
  3. 这个数学题我做可以,但世界毁灭了别怪我
  4. 基于回溯法寻找哈密顿回路

本文作者 奶权@米斯特安全

赞(0)
分享到: 更多 (0)

黑客技术,黑客教程,黑客软件,黑客入门,黑客工具,黑客平台,黑客下单,渗透测试,CTF,菠菜,源码,暗网,安卓,物联网安全,网络安全周,国家安全,企业安全,盗QQ号,正规黑客,接单黑客,SRC测试,黑客修改,黑客交流,黑客追款,APP渗透,黑客系统

联系我们联系我们