Apr*_*ude 8 algorithm optimization ackermann
我读过 Grossman 和 Zeitman 发表的论文《阿克曼函数的本质迭代计算》，其中提出了一种优化阿克曼函数的算法。
\n我们知道阿克曼函数产生子序列 A(m,n) 的结果
\n\n\nm=0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,... \
\n
n m=1: 2, 3 , 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,...
\n m=2: 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33,...
\n m=3: 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093 , 8189, 16381, 32765, 65533,...
\n m=4: 13, 65533,...
据说该Next数组是为了跟踪我们在每个子序列中的位置，并且该Goal数组是为了在将刚刚计算的值传输到下一个子序列之前跟踪我们需要到达的位置。它所做的就是将值加 1：
\n\nRun Code Online (Sandbox Code Playgroud)\nAckermann(m, n)\n {next and goal are arrays indexed from 0 to m, initialized so that next[0] \n through next[m] are 0, goal[0] through goal[m - l] are 1, and goal[m] is -1} \n repeat\n value \xe2\x86\x90 next[0] + 1 \n transferring \xe2\x86\x90 true \n current \xe2\x86\x90 0 \n while transferring do begin\n if next[current] = goal[current] then goal[current] \xe2\x86\x90 value\n else transferring \xe2\x86\x90 false\n next[current] \xe2\x86\x90 next[current] + 1\n current \xe2\x86\x90 current + 1 \n end while\n until next[m] = n + 1 \n return value {the value of A(m, n)}\n end Ackermann\n
我发现很难理解这两个数组如何指示我们在哪里/要移动到哪里？当我们停在 时，我无法确定它到底意味着什么next[m] = n + 1，为什么具体是这个值？我尝试过追踪该算法，但仍然不知道它是如何工作的。这个算法算不算是自下而上的实现？
这是一个 java 代码，用于打印值、当前值和两个数组
\nimport java.util.Arrays;\n\npublic class Ack {\n static int arrayAck(int m, int n) {\n //Next array to keep track of where we are in each subsequence, \n //and Goal array to keep track of where we need to reach before transferring the value just calculated to the next subsequence.\n int[] next = new int[m+1];\n int[] goal = new int [m+1];\n Arrays.fill(next, 0);\n Arrays.fill(goal, 1);\n goal[m] = -1;\n \n int value = next[0] + 1;\n while(true) {\n value = next[0] + 1;\n boolean transferring = true;\n int current = 0;\n \n System.out.println("--");\n System.out.println("Next = " + Arrays.toString(next));\n System.out.println("Goal = " + Arrays.toString(goal));\n System.out.println("Current= " + current);\n System.out.println("Value = " + value);\n while(transferring) {\n if(next[current] == goal[current])\n goal[current] = value;\n else\n transferring = false;\n next[current]=next[current]+1;\n current += 1;\n System.out.println("Current= " + current);\n System.out.println("Next = " + Arrays.toString(next));\n System.out.println("Goal = " + Arrays.toString(goal));\n }\n \n if(next[m]==n+1)\n break;\n \n }\n \n return value;\n }\n \n public static void main(String[] args) {\n int m=2,n=2;\n System.out.println("Ackermann value for ("+m+","+n+") = " + arrayAck(m, n));\n }\n\n}\n我通读了这篇论文，了解他们提出的算法，当你掌握了它的窍门后，它实际上并没有那么糟糕。
基本思想如下。我们有一个阿克曼函数的双参数版本，定义如下：
作者提出的方法本质上是阿克曼函数的空间优化、自下而上的计算。我们不给出算法的最终版本，而是看看是否可以从上述规则中推导出来。我们想象填充一个二维表，其中每一行对应于不同的 i 值，每列对应于 n 值。按照论文中的约定，我们将 i = 0 的行放在顶部，如下所示：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0
i=1
i=2
i=3
我们的目标是填写这张表。现在，不用担心表的大小；只需考虑表的大小即可。我们可以稍后确定。
阿克曼函数的三种情况中的第一种表示
规则 1： A(0, n) = n + 1。
我们可以将其解释为
表的顶行是值序列 1, 2, 3, 4, 5, ...
我们现在可以填写它，但出于稍后会变得更清楚的原因，现在让我们暂缓这样做。
下一条规则是
规则 2： A(i, 0) = A(i - 1, 1)。
我们可以将其解释为
表的每个连续行中的第一个条目是其上方行的第二个（索引 1）条目。
记住这两条规则，让我们开始填写表条目。我们可以使用第一条规则填充 A(0, 0) 的槽：A(0, 0) = 0 + 1 = 1。
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1
i=1
i=2
i=3
现在，让我们填写 A(0, 1) = 1 + 1 = 2：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2
i=1
i=2
i=3
因为我们刚刚填充了这个表条目，所以我们可以使用下一个规则来填充 A(1, 0) 的槽，这将由 A(0, 1) = 2 给出：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2
i=1 2
i=2
i=3
为了在填充 i = 1 的行方面取得更多进展，我们需要提取阿克曼函数的第三种情况：
规则 3： A(i, n) = A(i - 1, A(i, n - 1))。
这个规则很密集，但它有一个非常好的直觉。要填充表槽 A(i, n)，请执行以下操作：
在我们的例子中，假设我们想要填充 A(1, 1)。使用上述过程，我们执行以下操作：
然而，查看我们的表格，我们可以看到我们还没有计算 A(0, 2)。那么让我们这样做吧。我们通过规则 1 计算 A(0, 2) = 3：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3
i=1 2
i=2
i=3
根据规则 3，这又意味着 A(1, 1) = 3：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3
i=1 2 3
i=2
i=3
现在发生了一些有趣的事情。我们刚刚填写了 A(1, 1)，根据规则 2，我们可以通过复制 A(1, 1) 来填写 A(2, 0)：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3
i=1 2 3
i=2 3
i=3
让我们回顾一下刚刚发生的事情。
换句话说，通过计算第 0 行中的另一个值，我们产生了向下传播的连锁反应，使我们能够计算第 1 行、第 2 行等中的更多条目。因此，这建议采取一种方法：在第 0 行中生成另一个值，使用规则 1 很容易做到，然后看看我们是否可以使用规则 2 和规则 3 “波动”表中更高的值。
要查看实际情况，让我们使用规则 1 填写 A(0, 3) = 3+1 = 4：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4
i=1 2 3
i=2 3
i=3
现在，看第 1 行。规则 3 规定，要填充 A(1, 3)，我们需要首先计算 A(1, 2)（完成 - 这是 3），然后取第 0 行的第 3 列。我们刚刚计算第 0 行的第 3 列，这意味着我们应该将 A(0, 3) 复制到 A(1, 2)：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4
i=1 2 3 4
i=2 3
i=3
现在，看看第 2 行。我们已经填写了 A(2, 0)，因此这里要计算的下一个是 A(2, 1)。为了计算 A(2, 1)，我们首先计算 A(2, 0)（完成 - 它是 3），因此我们需要从第 1 行的第 3 列获取条目。不过，我们还没有计算过，所以没有更多的事情发生。涟漪到这里就停止了。
让我们计算第 0 行的下一个条目：A(0, 4) = 4+1 = 5。如下所示：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5
i=1 2 3 4
i=2 3
i=3
查看第 1 行，为了填充 A(1, 3)，我们查看 A(1, 2)（即 4）并复制 A(0, 4)：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5
i=1 2 3 4 5
i=2 3
i=3
查看第 2 行，为了填充 A(2, 2)，我们查看 A(2, 1)（即 3）并复制 A(1, 3)：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5
i=1 2 3 4 5
i=2 3 5
i=3
现在，看第 3 行。规则 2 规定 A(3, 0) = A(2, 1)，因此我们将 A(2, 1) 复制到：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5
i=1 2 3 4 5
i=2 3 5
i=3 5
波纹是如何完成的，因为这是我们表的所有行。
为了看看这个系统是如何演变的，让我们一个接一个地运行更多的涟漪：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5 6
i=1 2 3 4 5 6
i=2 3 5
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5 6 7
i=1 2 3 4 5 6 7
i=2 3 5 7
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5 6 7 8
i=1 2 3 4 5 6 7 8
i=2 3 5 7
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5 6 7 8 9
i=1 2 3 4 5 6 7 8 9
i=2 3 5 7 9
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5 6 7 8 9 10
i=1 2 3 4 5 6 7 8 9 10
i=2 3 5 7 9
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5 6 7 8 9 10 11
i=1 2 3 4 5 6 7 8 9 10 11
i=2 3 5 7 9 11
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5 6 7 8 9 10 11 12
i=1 2 3 4 5 6 7 8 9 10 11 12
i=2 3 5 7 9 11
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1 2 3 4 5 6 7 8 9 10 11 12 13
i=1 2 3 4 5 6 7 8 9 10 11 12 13
i=2 3 5 7 9 11 13
i=3 5 13
您可以对照本文表中的图 1 检查这些值，您会发现这与所发生的情况（部分）匹配。
该算法执行过程中的一个重要细节是，在每个时间点，我们只关心每行中的最后一项。该项目告诉我们在复制下一个值之前需要在下面的行中填充什么索引。考虑到这一点，我们可以想象再次运行该算法，但只存储每行中的最后一项。这可能看起来像这样：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 1
i=1
i=2
i=3
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 2
i=1 2
i=2
i=3
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 3
i=1 3
i=2 3
i=3
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 4
i=1 4
i=2 3
i=3
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 5
i=1 5
i=2 5
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 6
i=1 6
i=2 5
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 7
i=1 7
i=2 7
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 8
i=1 8
i=2 7
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 9
i=1 9
i=2 9
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 10
i=1 10
i=2 9
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 11
i=1 11
i=2 11
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 12
i=1 12
i=2 11
i=3 5
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0 13
i=1 13
i=2 13
i=3 13
这节省了很大的空间，并且暴露了每一行的一些有趣的东西。对于每一行，我们只需要存储两个值：
这两个值有什么意义呢？第一个数字可以用两种方式解释。首先，它是阿克曼序列的实际值。其次，对于第一行上方的行，它是一个指示符，表示“我们需要在我下方的行中处于什么位置才能前进到行中的下一列？” 这是纸张存储在数组中的值goal。
这些数字中的第二个可以被认为是在说“我处于什么位置？”，然后可以使用哪些更高级别的行来确定何时推进其goal值。这是纸张存储在数组中的值next。
我不会遍历论文中的伪代码，而是从头开始重写算法，最终得到与论文相似但不完全相同的结果。基本思想是模拟上述过程。我们跟踪表的每一行中的哪一列（我称之为它是positions为了使其含义更清晰）以及表的每一行中存储的值（我称之为values）。
为了简化处理某些行有值而其他行没有值的情况的逻辑（例如，请参阅上面跟踪中的前几个步骤），并将规则 2 和规则 3 统一在一起，我采用了遵循策略。我们将扩展 Ackermann 函数，以便按以下方式定义 A(i, -1) 的值：
然后，我们假设每行从位置 -1 开始，意思是“就在第一列之前”。直觉是，第 1 行、第 2 行、第 3 行等都在等待一个项目出现在它们上方行的位置 1 中，而在第 0 行中，第一个之前的值应该为 0，这样序列第 0 行产生的值是系列 0, 1, 2, 3, ... 。
考虑到这一点，这是我的实现：
n=0 n=1 n=2 n=3 n=4 n=5 n=6 n=7 n=8 n=9 n=10 n=11 n=12
i=0
i=1
i=2
i=3
最后一个细节 - 我相信 Zeitman 和 Grossman 对 O(iA(i, n)) 的原始运行时分析是正确的，但并不严格。具体来说，这假设在算法的每一步中，我们将一个值从一层复制到下一层。然而，事实并非如此。每行中的值增长得如此之快，以至于在大多数步骤中我们不会将任何内容复制到表的任何高行。更具体地说，请注意表的第 2 行由每隔一个奇数组成，因此只有一半的增量步骤会复制其中的内容，并且上面的行肯定不会复制超过它们下面的层的一半值。这意味着，平均而言，每个波纹将有 100% 的机会复制到第 1 行，最多 50% 的机会复制到第 2 行，最多 25% 的机会复制到第 3 行，依此类推。对数字求和制作的副本数并使用这里（至少）几何衰减的事实意味着“平均”操作仅复制 O(1) 总行。这意味着我们正在执行 O(A(i, n)) 增量步骤，每个步骤（平均）仅复制到 O(1) 总行，因此完成的总工作是O(A(i, n))。这对于运行时限制来说并不是一个巨大的改进（A(i, n) 项是巨大的！），但它是一个稍微好一点的结果。