图--深度优先搜索

解决骑士周游问题来学习深度优先搜索

1. 先生成图
2. 再用图 深度优先搜索

创建图

棋盘格上每个合理走法都代表一条边，由此建立图。

算法：
初始化一个图
对每一格进行循环
计算每一格可以连接的其他格子
为它们添加边
返回图

深度优先算法(DFS)解决骑士周游问题

knghtTour()这个递归函数的代码看了挺久的才看懂…
感觉对于递归还是理解地不够深入。

def knightTour(n, path, u, limit):
    # 访问过u
    u.setColor('gray')
    path.append(u)
    # 要递归的情况
    if n < limit:
        nbr_list = list(u.getConnections())
        i = 0
        done = False
        while i < len(nbr_list) and not done:
            if nbr_list[i].getColor() == 'white':
                # 递归
                done = knightTour(n + 1, path, nbr_list[i], limit)
                i += 1
            # 如果当前节点没有白色的邻接节点，就不会执行上面的递归。
            # 但是此时n < limit，整张图中一定还是有白色节点的，我们遇到了死路，需要回溯
        if not done:
            path.pop()
            u.setColor('white')
    # base case:n == limit
    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

理解：

1. 只要n
2. 递归函数第一次return True，就是n==limit的情况，即base case。此时开始递归返回。
3. path列表是用来当作栈的，为了回溯而准备。
4. done是用来标记是否已经到达了base case。因为while循环结束会有两种情况：1.过了一遍所有的邻接点，都没有白色的，但是n

跟着书上的一下例子走一遍，会理解的好一些：

骑士周游的性能/复杂度

骑士周游是复杂度O(k^N)的算法，N是棋盘上的格子数。

启发式技术Warnsdorff 算法：
就是记录了当前节点的相邻顶点们的可移动格子数，然后将可移动格子数少的相邻点排在前面。这样探索的次数会少一点。

代码：

def orderedByAvail(n):
    """获取邻接点可以到达的格子数"""
    resList = []
    for v in n.getConnections():
        c = 0
        for w in v.getConnections():
            if w.getColor() == 'white':
                c += 1
            resList.append((c, v))
    # 可访问格子数少的点排前面
    resList = sorted(resList, key=lambda x: x[0])
    return [y[1] for y in resList]
1
2
3
4
5
6
7
8
9
10
11
12

通用深度优先搜索技术

几个需要注意的点：

1. 将实现深度优先搜索的代码 作为 Graph的一个子类实现。因为想要记录搜索的时间，还可以记录第一次访问节点/第二次访问接节点(递归返回时)的时间。
2. 子类多了time属性，dfs方法，dfsvisit方法。dfsvisit方法才是真正的深度递归搜索函数。dfs函数只是为了保证每一个点都能被访问到，因为只从一个点开始访问，到访问结束，不一定能保证所有的顶点都被访问到。
3. 注：这里深度优先搜索没有像骑士周游一样设置标识done，是因为不需要回溯。 回溯要把当前节点设置为白，等于没访问过。普通dfs不许要。
4. 通过前驱连接来构建树。树根节点的前驱是-1.
   
   从上图也可以看出，每个顶点被访问两次，第一次访问过边灰，第二次访问过变黑。
   ★图中，虚线表示被检查过的边，但是其一端的顶点已经被添加到深度优先搜索树中。在代码中，这是通过检查另一端的顶点是否不为白色来完成的。这也是需要dfs遍历过所有顶点的意义。

代码：

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0

    def dfs(self):
        """对图中的每一个顶点dfsvisit，而不是从任意一个起始点开始搜索，是为了保证所有顶点都被搜索过"""
        for vertex in self:
            vertex.setColor('white')  # 先将图中每个点颜色初始化为白
            vertex.setPred(-1)  # pred初始化为-1
        for avertex in self:
            if avertex.geteColor() == 'white':
                self.dfsvisit(avertex)

    def dfsvisit(self, start_vertex):
        self.time += 1  # 每碰到一个点一次，次数+1
        start_vertex.setDiscovery(self.time)  # 设置第一次访问该点的时间
        """深度优先搜索"""
        start_vertex.setColor('gray')  # 正在访问此顶点
        for v in start_vertex.getConnections():
            if v.getColor() == 'white':
                self.dfsvisit(v)
        # 深度搜素完，返回到初始点，将初始点设置为黑。
        start_vertex.setColor('black')
        self.time += 1  # 此时+1是因为递归返回
        start_vertex.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