在图中找到需要访问最少节点数的路径

Question

我正在寻找一种算法来找到非圆形图中的最短路线。但是，最短路径不是定义为权重最小的路径，而是到达目的地之前要访问的节点数最少的路径。

让我举个例子：假设您在 phone 上使用了错误的计时器应用程序，该应用程序的计时器限制为半小时。一共有三个按钮：

加 10 分钟
加 1 分钟
减一分钟

初始值为零。输入范围是 0 到 30 分钟。我们现在要设置一个计时器，比方说 29 分钟。完成此操作的最短路径是点击 add 10 min 三次和 subtract 1 min 一次。

我们在图表中表示按钮按下的每个排列（其中每个节点表示对三个按钮之一的点击）。我们现在正在寻找一种从开始到特定数字的方法，它的按钮按下次数最少。

Answer 1

问题可以使用breadth first search (BFS) 来解决。给定问题的开始时间（我们将其视为图的起始节点）和目标时间（我们将其视为目标节点）。在每一步中，我们都可以对当前时间执行以下任一操作：

加 10 分钟
加 1 分钟
减去 1 分钟

现在，图表的节点将是我们可以使用上述任一步骤达到的时间。例如，从时间 0（将其视为 node-id 0）开始，我们可以一步到达枯萎 10、1 或 -1（即节点）。因此，在一步中我们发现了图中的三个不同节点，其中没有一个是我们的目标节点。

有了这三个新发现的节点，我们可以做类似的移动，到达一些距离源节点2步的新节点（即时间0）。这是我们在第二步中可以发现的节点列表：

从 10 到：20、11、9
从 1 到：11、2、0
从 -1 到：9、0、-2

从这里我们可以注意到几件事：

如果我们发现一个以前从未发现过的节点，那么它需要发现的步数就是最短距离。例如，我们可以从源节点0走2步到达节点9（这里可以看到，9可以从节点10和-1), 显然它是节点 9.
图形可以是圆形的。例如，有一条边从节点0到节点-1，从节点-1到节点0。你需要处理它。

所以，现在我们把这个问题转化为一个标准的 BFS 问题就很清楚了。现在，我们可以通过下面的伪代码来解决：

Shortest-Path(initial-time, target-time):
    Queue<time> Q
    Map<time, step> M     // this map will help tracking whether we discover a node before or not
    
    Q.insert(initial-time)
    M[initial-time] = 0
    while(!Q.empty):
        current-time = Q.front()
        Q.pop()

        if current-time is equal to target-time:
            return M[current-time]

        if (current-time + 10) is not in the M:
            Q.push(current-time + 10)
            M[(current-time + 10)] = M[current-time] + 1

        if (current-time + 1) is not in the M:
            Q.push(current-time + 1)
            M[(current-time + 1)] = M[current-time] + 1

        if (current-time - 1) is not in the M:
            Q.push(current-time - 1)
            M[(current-time - 1)] = M[current-time] + 1

Answer 2

不要将问题视为图遍历问题，您可以通过对以单个根节点开始并随时间增长的树执行 BFS 来简单地解决它：

#!/usr/bin/python3
DESIRED_SUM = 29
SET = [-1, 1, 10]
QUEUE = [(0, [])] # For BFS
ANSWER = {} # For Dynamic Programming

while True:
    (cur_sum, elements) = QUEUE.pop(0)

    if cur_sum not in ANSWER:
        ANSWER[cur_sum] = elements

    if cur_sum == DESIRED_SUM:
        break

    for num in SET:
        new_sum = cur_sum + num
        if new_sum not in ANSWER:
            new_elements = elements.copy()
            new_elements.append(num)
            QUEUE.append((new_sum, new_elements))

for key, item in ANSWER.items():
    print("{0}: {1}".format(key, item))

每次附加到 QUEUE 时，实际上是在添加叶节点。如果你只是执行 BFS 而不存储结果（即动态规划），那么你将达到指数时间。上述代码复制和携带 elements 列表的方式非常低效。例如，您可以改为存储 ANSWER[28] = ANSWER[29] - 1，这样当您实际想要检索给定总和的完整元素列表时，您可以递归地按照 ANSWER 来检索它。

请注意，如果无法从给定的元素列表中导出 DESIRED_SUM，则上述程序将永远不会终止。

在图中找到需要访问最少节点数的路径

Find the path in a graph, that requires the least amount of nodes to visit

algorithm

graph

breadth-first-search

shortest-path