我读了这篇文章，它与我遇到的问题非常接近，但无法概括它。我正在尝试通过使用多个 CPU 搜索所有路径来解决旅行销售人员问题。我需要的是一种将路径前缀编码为整数并将其分配给每个 CPU 的方法，以便它知道应该扫描哪些路径。例如，如果城市数量是 10，一个可能的 3 前缀（假设前缀长度是固定的并且已知）是 4-10-3（有 10*9*8 个前缀），因此接收它的 CPU 将搜索所有以 4-10-3 开头的路径。由于城市数量很大，我无法计算n！因此我不能使用上面的帖子。
问问题
155 次
2 回答
2
排列为数字的标准表示使用阶乘数字系统中表示的Lehmer 代码。这个想法是n个元素的每个排列都可以映射到n个数字的序列，其中第一个在0到（n - 1）的范围内，第二个在0到（n - 2）的范围内等。然后，这个数字序列可以表示为阶乘数字系统中的单个整数。
我相信应该可以调整这个技巧来处理排列的前缀而不是整个排列。假设您有 n 个元素，并且想要选择其中 k 个的排列。为此，首先计算部分排列的 Lehmer 码。您将得到一个由 k 个数字组成的序列，而不是得到一个由 n 个数字组成的序列。例如，给定c a d从 中提取的部分排列a b c d e f g，您的 Lehmer 代码将如下所示：
c是的第二个（零索引）元素a b c d e f ga是第零个（零索引）元素a b d e f gd是第一个（零索引）元素b d e f g
所以 Lehmer 代码将是(2, 0, 1).
一旦你有了这个 Lehmer 代码，你就可以尝试将它编码为一个整数。为此，您可以使用修改后的阶乘数字系统编码。具体来说，您可以尝试执行以下操作。如果你有 n 个元素并且想要其中 k 个的排列，那么最后一个元素总共会有 (n - k + 1) 个可能的选择。倒数第二个元素总共有 (n - k + 2) 个可能的选择，倒数第三个元素有 (n - k + 3) 个可能的选择，等等。因此，您可以使用 Lehmer代码并执行以下操作：
- 保持最后一位不变。
- 将倒数第二个元素乘以 (n - k + 1)。
- 将倒数第三个元素乘以 (n - k + 1)(n - k + 2) 4 ...
- 将第一个元素乘以 (n - k + 1)(n - k + 2)...(n - 1)
- 总结这些价值观。
这会为排列生成一个唯一的整数代码。
例如，我们的 Lehmer 码是(2, 0, 1)，n = 7 和 k = 3。因此，我们将计算
1 + 0 × (7 - 3 + 1) + 2 × (7 - 3 + 2)(7 - 3 + 3)
= 1 + 2 × (5 × 6)
= 5 + 2 × 30
= 61
要反转此过程，您可以获取整数并通过此过程向后运行它以恢复部分 Lehmer 代码。为此，首先取数字并除以 (n - k + 1)(n - k + 2)...(n - 1) 以取回 Lehmer 码的第一个数字。然后，将数字修改为 (n - k + 1)(n - k + 2)...(n - 1) 以去掉第一位。然后，将数字除以 (n - k + 1)(n - k + 2)...(n - 2) 得到 Lehmer 码的第二个数字，然后除以 (n - k + 1)( n - k + 2)...(n - 2) 去掉第二个数字。重复此操作，直到 Lehmer 代码的所有数字都被重建。
例如，给定前缀 61、n = 7 和 k = 3，我们将从 61 除以 7 × 6 = 30 开始。这样得到 2，余数为 1。因此 Lehmer 码的第一个数字是 2。 30，我们得到数字 1。接下来，我们除以 6。得到 0，余数为 1。因此第二个数字是 0。最后，我们读出剩余的数字，即 Lehmer 码的最后一个数字，1 . 我们已经恢复了我们的 Lehmer 代码(2, 0, 1)，从中我们可以很容易地重建排列。
希望这可以帮助！
于 2013-01-05T19:36:43.373 回答
1
这里最简单的方法是映射前缀而不将其视为排列的一部分。不要把前缀映射到[0,10*9*8-1]，而是映射到[0,10*10*10-1]，所以前缀0,4,5会映射到数字45，前缀 4,1,9 将映射到数字 419（当然，假设总共有 10 个城市）。
于 2013-01-05T19:37:05.560 回答