7.13. 实现骑士巡游¶
7.13. Implementing Knight’s Tour
我们将使用的搜索算法来解决骑士巡游问题叫做 深度优先搜索 (DFS)。与广度优先搜索算法逐层构建搜索树不同，深度优先搜索通过尽可能深地探索树的一个分支来创建搜索树。在这一部分，我们将查看两个实现深度优先搜索的算法。第一个算法专门通过明确禁止一个节点被访问多次来解决骑士巡游问题。第二个实现更为通用，但允许在构建树时节点被访问多次。第二个版本将在后续部分用于开发额外的图算法。
深度优先遍历图正是我们需要的，以找到一个经过64个顶点（每个方格一个）和63条边的路径。我们将看到，当深度优先搜索算法遇到死胡同时（图中没有更多的合法移动），它会回溯到下一个允许合法移动的最深顶点。
Listing 3 中显示的 knight_tour 函数有四个参数：n，当前在搜索树中的深度；path，到目前为止访问过的顶点列表；u，我们希望探索的图中的顶点；以及 limit，路径中的节点数量。knight_tour 函数是递归的。当 knight_tour 函数被调用时，它首先检查基准条件。如果路径中包含64个顶点，我们从 knight_tour 函数返回 True，表示我们找到了一条成功的巡游路径。如果路径不够长，我们继续深入探索一个新的顶点，并对该顶点递归调用 knight_tour。
from pythonds3.graphs import Graph
def knight_tour(n, path, u, limit):
u.color = "gray"
path.append(u)
if n < limit:
neighbors = sorted(list(u.get_neighbors()))
i = 0
done = False
while i < len(neighbors) and not done:
if neighbors[i].color == "white":
done = knight_tour(n + 1, path, neighbors[i], limit)
i = i + 1
if not done: # 准备回溯
path.pop()
u.color = "white"
else:
done = True
return done
DFS 也使用颜色来跟踪图中哪些顶点已被访问。未访问的顶点被标记为白色，已访问的顶点被标记为灰色。如果某个顶点的所有邻居都已被探索，并且我们还未达到目标长度64个顶点，则我们遇到死胡同，必须回溯。回溯发生在我们从 knight_tour 函数返回 False 时。在广度优先搜索中，我们使用队列来跟踪下一个要访问的顶点。由于深度优先搜索是递归的，我们隐式地使用栈来帮助回溯。当我们从 knight_tour 函数返回 False 时，我们仍停留在 while 循环中，查看 neighbors 中的下一个顶点。
让我们看一个简单的 knight_tour (Listing 3) 的实际示例。您可以参考下面的图形来跟踪搜索步骤。对于这个示例，我们将假设在第6行上调用 get_neighbors 方法时，节点按字母顺序排列。我们开始时调用 knight_tour(0, path, A, 6)。
knight_tour 从 图3 中的节点 A 开始。A 的邻居是 B 和 D。由于 B 在字母表中位于 D 之前，DFS 选择 B 进行扩展，如 图4 所示。探索 B 发生在递归调用 knight_tour 时。B 的邻居是 C 和 D，因此 knight_tour 选择下一个探索 C。然而，如 图5 所示，节点 C 是死胡同，没有邻接的白色节点。此时我们将节点 C 的颜色恢复为白色。对 knight_tour 的调用返回 False。从递归调用的返回实际上将搜索回溯到顶点 B（见 图6）。列表中下一个要探索的顶点是 D，因此 knight_tour 递归调用移动到节点 D（见 图7）。从顶点 D 开始，knight_tour 可以继续进行递归调用，直到再次到达节点 C（见 图8、图9 和 图10）。但是，这次当我们到达节点 C 时，测试 n < limit 失败，因此我们知道图中的所有节点都已被耗尽。此时我们可以返回 True，表示我们成功完成了图的巡游。当我们返回列表时，path 包含值 [A, B, D, E, F, C]，这是我们需要遍历图的顺序，以确保每个节点只访问一次。
图11 显示了一个完整的 \(8 \times 8\) 棋盘上的巡游图样。有许多可能的巡游路径，有些是对称的。通过一些修改，您可以创建以相同方格开始和结束的圆形巡游。
knight_tour 找到的棋盘完整巡游路径
The search algorithm we will use to solve the knight’s tour problem is called depth-first search (DFS). Whereas the breadth-first search algorithm builds a search tree one level at a time, a depth-first search creates a search tree by exploring one branch of the tree as deeply as possible. In this section we will look at two algorithms that implement a depth-first search. The first algorithm we will look at specifically solves the knight’s tour problem by explicitly forbidding a node to be visited more than once. The second implementation is more general, but allows nodes to be visited more than once as the tree is constructed. The second version is used in subsequent sections to develop additional graph algorithms.
The depth-first exploration of the graph is exactly what we need in order to find a path through 64 vertices (one for each square on the chessboard) and 63 edges. We will see that when the depth-first search algorithm finds a dead end (a place in the graph where there are no more moves possible) it backs up the tree to the next deepest vertex that allows it to make a legal move.
The knight_tour function shown in Listing 3 takes four parameters: n, the current depth in the search tree; path, a list of vertices visited up to this point; u, the vertex in the graph we wish to explore; and limit, the number of nodes in the path. The knight_tour function is recursive. When the knight_tour function is called, it first checks the base case condition. If we have a path that contains 64 vertices, we return from knight_tour with a status of True, indicating that we have found a successful tour. If the path is not long enough, we continue to explore one level deeper by choosing a new vertex to explore and calling knight_tour recursively for that vertex.
from pythonds3.graphs import Graph
def knight_tour(n, path, u, limit):
u.color = "gray"
path.append(u)
if n < limit:
neighbors = sorted(list(u.get_neighbors()))
i = 0
done = False
while i < len(neighbors) and not done:
if neighbors[i].color == "white":
done = knight_tour(n + 1, path, neighbors[i], limit)
i = i + 1
if not done: # prepare to backtrack
path.pop()
u.color = "white"
else:
done = True
return done
DFS also uses colors to keep track of which vertices in the graph have been visited. Unvisited vertices are colored white, and visited vertices are colored gray. If all neighbors of a particular vertex have been explored and we have not yet reached our goal length of 64 vertices, we have reached a dead end and must backtrack. Backtracking happens when we return from knight_tour with a status of False. In the breadth-first search we used a queue to keep track of which vertex to visit next. Since depth-first search is recursive, we are implicitly using a stack to help us with our backtracking. When we return from a call to knight_tour with a status of False, in line 11, we remain inside the while loop and look at the next vertex in neighbors.
Let's look at a simple example of knight_tour (Listing 3) in action. You can refer to the figures below to follow the steps of the search. For this example we will assume that the call to the get_neighbors method on line 6 orders the nodes in alphabetical order. We begin by calling knight_tour(0, path, A, 6).
knight_tour starts with node A in Figure 3. The nodes adjacent to A are B and D. Since B is before D alphabetically, DFS selects B to expand next as shown in Figure 4. Exploring B happens when knight_tour is called recursively. B is adjacent to C and D, so knight_tour elects to explore C next. However, as you can see in Figure 5 node C is a dead end with no adjacent white nodes. At this point we change the color of node C back to white. The call to knight_tour returns a value of False. The return from the recursive call effectively backtracks the search to vertex B (see Figure 6). The next vertex on the list to explore is vertex D, so knight_tour makes a recursive call moving to node D (see Figure 7). From vertex D on, knight_tour can continue to make recursive calls until we get to node C again (see Figure 8, Figure 9, and Figure 10). However, this time when we get to node C the test n < limit fails so we know that we have exhausted all the nodes in the graph. At this point we can return True to indicate that we have made a successful tour of the graph. When we return the list, path has the values [A, B, D, E, F, C], which is the order we need to traverse the graph to visit each node exactly once.
Figure 11 shows you what a complete tour around an \(8 \times 8\) board looks like. There are many possible tours; some are symmetric. With some modification you can make circular tours that start and end at the same square.
knight_tour
创建日期: 2024年9月9日