python - 使用回溯计算屏幕锁定模式的问题

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 时它可以接受 a -> b -> a 这是错误的所以它不能将节点的父节点作为邻居，我知道这个问题但是我不知道如何修复它。

Answer 1

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

result += count_patterns(neighbor, length - 1) - 1

应该变成

result += count_patterns(neighbor, length - 1)

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

1. 有一个全局访问数组，它有 bool 值(true 或 false)。如果您有 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

``

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

1. 您可以将第三个参数传递给您的函数，它是到目前为止您选择的顶点的列表；那么你只选择一个新的顶点，如果你不在列表中。你也更新列表:

``

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

``

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