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

Question

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

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) 达到 return 15，它确实 return 了；然而，对于 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 的路径。但事实并非如此。路径不应该有重复的顶点。有两种方法可以解决这个问题：（我只提主要思想）

有一个具有布尔值（真或假）的全局访问数组。如果您有 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

``

您需要 "mark neighbor as unvisited" 的原因是您不想在特定分支中重复一个顶点；但是您希望在从递归调用返回后能够在另一条路径上使用它。

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

``

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

``

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

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

Problem counting screen locking patterns with backtracking

python

algorithm

backtracking

depth-first-search