0

我在回溯时遇到了麻烦，并且不确定我正在做的事情是否准确地回溯。

在我的示例中，我有 n 个整数，它将是 [5,6,7,8]。

从这些整数中，我需要找出素数序列是否存在以及是否显示它。

这个例子的素数序列是 7,6,5,8 因为 7+6=13 6+5=11 5+8=13

为了得到答案，我可以遍历每个 n，然后尝试查看它是否是素数序列。

5点开始：

  • 5,6[7,8]
  • 5,6,7[8]

因为 7+8 不是素数。进入下一个整数。

因为 5+7 不是素数。进入下一个整数。

  • 5,8,[6,7]

因为 8+6 或 8+7 不是素数。你已经完成了 5 个。

6点开始：

  • 6,5[7,8]
  • 6,5,8[7]

因为 7+8 不是素数。进入下一个整数。

  • 6,7[5,8]

因为 7+5 或 7+8 不是素数。进入下一个整数。

因为 6+8 不是素数。你已经完成了 6 个。

7点开始：

  • 7,6[5,8]
  • 7,6,5[8]
  • 7,6,5,8

自从你找到素数序列后结束。

那么如何通过回溯来解决这个问题呢？

4

2 回答 2

3

在这种情况下，回溯的想法基本上是这样的：让我找到所有有效事物的子序列（或前缀）的延续。如果我成功了，我会将继续返回给我的调用者。如果我运气不好，我会要求我的来电者尝试不同的前缀。

更确切地说：

// call initially as Backtrack(epsilon, all numbers)
Backtrack(Sequence fixedPrefix, Set unbound) {
  if (unbound is empty) {
    return check(fixedPrefix);
  }
  for all (element in unbound) {
    if (Backtrack(concat(fixedPrefix,element), setminus(unbound,element))
      return true;
  }
  return false;
}

请注意，此算法只会告诉您序列是否存在（并且它在 C++ 中的直接实现会非常慢），但不会告诉您该序列是什么，但这很容易修改。

无论如何，回溯中的“返回”发生在递归调用不走运的最后一行：这将提示调用实例尝试另一个 prefix，因此控制流有点颠倒。

于 2012-04-11T01:29:49.887 回答
1

您的函数（无论是否为伪代码）都没有做任何有效的事情。我实际上不确定它应该做什么。IE。u = 0;紧随其后if(u == 4);，你的isPrime函数总是被传递(Integers[0]+integers[0])。

我相信您所说的回溯更恰当地称为递归函数（可以调用自身的函数）。回溯是递归函数可以表现出的特定行为的一个糟糕（模糊）的名称。

如果你想要一个这样的递归函数，你需要废弃它并重新开始。用简单的英语（或其他语言）写出函数应该做什么。然后，一旦您知道需要传递给它的内容、失败和成功之间的区别以及失败或成功时返回的内容（在失败时需要如何修改向量），然后对其进行编码。

超级提示：对于整数的小选择，例如您提出的，请尝试next_permutation()在 stl< algorithm >中快速浏览向量中可能的整数排列。

于 2012-04-11T01:55:05.163 回答