使用回溯计算屏幕锁定模式时出现问题

Question

问题是计算给定长度为 n 的路径数 图表中的顶点，例如用于解锁Android设备的顶点。我正在尝试使用回溯来解决它，但我没有正确，我仍在学习如何使用它。所以这是我一直在尝试的一些代码

G = {
'a': set('bed'),
'b': set('cfeda'),
'c': set('feb'),
'd': set('abehg'),
'e': set('bcfihgda'),
'f': set('ciheb'),
'g': set('deh'),
'h': set('efigd'),
'i': set('fhe')
}
result = 0

def count_patterns(node, length):
if length == 1:
return len(G[node])
global result
for neighbor in G[node]:
result += count_patterns(neighbor, length - 1) - 1
return result

我希望 count_patterns('a'，2( 返回 15 并且它确实返回它;但是，对于 n>2 到目前为止，所有的结果都是错误的。我认为一定是我实际上没有跟踪访问的节点，例如，如果采用此路线 n = 3 a -> b -> c 当它回溯到 a -> b 时，它可以采用 -> b -> a 这是错误的，因此它不能将节点的父节点作为邻居，我知道问题，但是 我不知道如何解决它。

Answer 1

首先，你不需要最后一个 -1。所以

结果 += count_patterns(相邻，长度 - 1(- 1

应该成为

结果 += count_patterns(相邻，长度 - 1(

代码的主要问题是，例如，如果您从 a->b 然后从 b->a 开始，则将其计为长度为 2 的路径。但事实并非如此。路径不应具有重复的顶点。有两种方法可以解决这个问题：(我只会提到主要思想(

1. 具有具有布尔值(真或假(的全局访问数组。如果您有 n 个节点，则此阵列的容量应与节点数一样多。然后，按如下方式更改代码：(伪代码(

''

def count_patterns(node, length):
if length == 1:
return len(G[node])
global result
for neighbor in G[node]:
if neighbor is not visited
mark neighbor as visited
result += count_patterns(neighbor, length - 1)
mark neighbor as unvisited //This is very important
return result

''

您需要"将邻居标记为未访问"的原因是，您不想在特定分支中重复顶点;但您希望在从递归调用返回后能够在另一条路径上使用它。

2. 你可以将第三个参数传递给你的函数，它是你到目前为止选择的顶点的列表;然后，如果你不在列表中，你只选择一个新顶点。并且您还更新列表：

''

def count_patterns(node, length, list):
if length == 1:
return len(G[node])
global result
for neighbor in G[node]:
if neighbor is not in list
result += count_patterns(neighbor, length - 1, list.append(neighbor))
return result

''

我个人更喜欢第一种方法，因为它会更快、更简单。