深度优先算法(DFS)的python实现及骑士周游问题解析_用python代码写深度优先遍历算法的时间复杂度

背景： 骑士周游问题

在棋盘格里，马走日，遍历所有网格点，找到每个网格都走过，且只有一次的路径。

算法实现：
用于解决骑士周游问题的图搜索算法是深度优先搜索（DFS），该算法是逐层建立搜索树，沿着树的单支尽量深入的向下搜索。连接尽量多的顶点，必要时可以进行分支。
深度优先搜索同样要用到顶点的“前驱”属性，来构建树或森林。另外需要设置“发现时间”和“结束时间”属性。
发现时间是在第几步访问到了这个顶点（设置灰色）；结束时间是在第几步完成了此顶点的探索（设置黑色）。

通用的深度优先搜索算法代码：

# BFS采用队列存储待访问顶点
# DFS通过递归调用，隐式使用了栈
from pythonds.graphs import Graph
class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0

    def dfs(self):
        for aVertex in self:
            aVertex.setColor('white')  # 颜色初始化
            aVertex.setPred(-1)
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsvisit(aVertex)  # 如果还有未包括的顶点，则建森林

    def dfsvisit(self,startVertex):
        startVertex.setColor('gray')
        self.time += 1  # 算法的步数
        startVertex.setDiscovery(self.time)
        for nextVertex in startVertex.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setPred(startVertex)
                self.dfsvisit(nextVertex)  # 深度优先递归访问
        startVertex.setColor('black')  # 节点探索完毕，设为黑色
        self.time += 1
        startVertex.setFinish(self.time)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

算法分析：
（1）DFS构建的树，其顶点的发现时间和结束时间属性，具有类似括号的性质。即一个顶点的发现时间总小于所有子顶点的发现时间，而结束时间则大于所有子顶点结束时间，比子顶点更早被发现，更晚被结束探索。
（2）DFS运行时间同样也包括了两方面：dfs函数中有两个循环，每个都是|V|次，所以是O(|V|)，而dfsvisit函数中的循环则是对当前顶点所连接的顶点进行，而且仅有在顶点为白色的情况下才进行递归调用，所以对每条边来说只会运行一步，所以是O(|E|)，加起来就是和BFS一样的O(|V|+|E|)。

骑士周游问题的算法实现：

def genLegalMoves(x,y,bdSize):
    newMoves = []
    moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1),  # 马走日8个格子
                   (1,-2),(1,2),(2,-1),(2,1)]
    for i in moveOffsets:
        newX = x + i[0]
        newY = y + i[1]
        if legalCoord(newX,bdSize) and legalCoord(newY,bdSize):
            newMoves.append((newX,newY))
    return newMoves

def legalCoord(x,bdSize):
    if x >= 0 and x < bdSize:  # 确认不会走出棋盘
        return True
    else:
        return False

def knightGraph(bdSize):
    ktGraph = Graph()
    for row in range(bdSize):  # 遍历每个格子
        for col in range(bdSize):
            nodeId = posToNodeId(row,col,bdSize)
            newPositions = genLegalMoves(row,col,bdSize)  # 单步合法走棋
            for e in newPositions:
                nid = posToNodeId(e[0],e[1],bdSize)
                ktGraph.addEdge(nodeId,nid)  # 添加边及顶点
        return ktGraph

def posToNodeId(row,col,bdSize):
    return row*bdSize + col

def knightTour(n,path,u,limit): # n层次，path路径，u当前顶点，limit搜索总深度
    u.setColor('gray')
    path.append(u)  # 当前顶点加入路径
    if n < limit:
        nbrList = list(u.getConnections())  # 对所有合法移动逐一深入
        i = 0
        done = False
        while i < len(nbrList) and not done:
            if nbrList[i].getColor() == 'white':  # 选择白色未经过的顶点深入
                done = knightTour(n+1,path,nbrList[i],limit) # 层次加1，递归深入
            i = i + 1
        if not done:  # 无法完成总深度，回溯，试本层下一个节点
            path.pop()
            u.setColor('white')
    else:
        done = True
    return done

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

算法分析：
其性能高度依赖于棋盘大小，目前实现的算法，其复杂度为O(k^n)，其中，n是棋盘格数目。这是一个指数时间复杂度的算法，其搜索过程表现为一个层次为n的树。

算法改进
修改遍历下一格的次序，将u的合法移动目标棋盘格排序为：具有最少合法移动目标的格子优先搜索。采用先验知识来改进算法性能的做法，称作为“启发式规则heuristic”。启发式规则经常用于人工智能领域；可以有效地减小搜索范围、更快达到目标等；
python代码实现：

# 骑士周游算法改进代码：
def orderByAvail(n):
    resList = []
    for v in n.getConnections():
        if v.getColor() == 'white':
            c = 0
            for w in v.getConnections():
                if w.getColor() == 'white':
                    c = c + 1
                resList.append((c,v))
    resList.sort(key=lambda x: x[0])
    return [y[1] for y in resList]
1
2
3
4
5
6
7
8
9
10
11
12

两者区别：
上述骑士周游问题的算法，其特点是每个顶点仅可访问一次；而通用深度优先算法是允许顶点被重复访问，更加符合寻优实际情形，可作为其它图算法的基础。