algorithm - 给定一个整数 N 和一组操作，以最少的步骤将 N 减少到 1

Question

对于给定的整数 N，我们可以使用以下操作:

1. 如果N可以被3整除:除以3。
2. 如果N可以被2除:除以2。
3. 减去 1。

如何找到以最少的步数达到 1 的策略？

Answer 1

正如 mbeckish 提到的，您可以将其视为 BFS 遍历，它的时间和空间复杂度明显优于自下而上的 DP 方法。您还可以在遍历中应用分支定界 (B&B) 启发式算法，这样您就可以在我们之前已经看到标记值的节点处修剪树的分支。与实际的 B&B 启发式不同，这不会删除最优解，因为它不涉及对最优解可能在哪里的任何有根据的猜测。我将给出一个直观的例子，并将算法减少到 0 以更好地说明。

这是一个完整的操作树，将 10 减少到 0:

   --------10---------
   5         -----9----
---4---     -3-      ------8------  
2    -3-    1 2    --4--         7        
1    1 2    0 1    2  -3-   -----6------   
0    0 1      0    1  1 2   2   -3-    5   
       0           0  0 1   1   1 2  --4-- 
                        0   0   0 1  2  -3-
                                  0  1  1 2
                                     0  0 1
                                          0 

因为我们在做 BFS，我们实际上会像下面这样在第一个零处停止，而不是构建树的更深部分:

   --------10------
   5         -----9--------
---4---     -3-     ------8------  
2    -3-    1 2     4           7        
1    1 2    0 

然而，我们可以通过 B&B 启发式进一步减少分支数量，使其看起来像这样(这对大量数据产生巨大影响):

   --------10------
   5         -----9--------
   4         3            8
   2         1            7
             0 

时间复杂度: O(log n) 空间复杂度: O(log n) ^(我认为)

下面是 python 3 代码，输入为 1 googol (10^100)，在我的计算机和大约 350 MB 的 RAM 上运行大约需要 8 秒。您也可以在 https://repl.it/B3Oq/76 在线运行它

from collections import deque

def number_of_steps(i):
    Q = deque()
    seen_before = set()
    steps = 0
    Q.append((i, steps))
    while True:
        j, steps = Q.popleft()
        if j == 1:
            return steps
        if j % 3 == 0:
            branch(Q, seen_before, steps, j // 3)
        if j % 2 == 0:
            branch(Q, seen_before, steps, j // 2)
        branch(Q, seen_before, steps,  j - 1)

def branch(Q, seen_before, steps, k):
    if k not in seen_before:
        seen_before.add(k)
        Q.append((k, steps + 1))

import time
n = 10**100
print('input:', n)
start = time.time()
steps = number_of_steps(n)
end = time.time()
print('runtime (seconds):', end - start)
print('number of steps:', steps)