素数序列的回溯算法

Question

我在做回溯时遇到了困难，并且不确定我所做的是否是精确的回溯。

我的例子中有n个整数，它将是5,6,7,8。

从这些整数中，我需要找到一个素数序列是否存在，如果它确实显示它。

这个例子的素数序列是自7+6=13 6+5=11 5+8=13以来的7,6,5,8

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

从5:开始

• 5,67,8
• 5,6,78

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

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

• 5,8,6,7

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

从6:开始

• 6,57,8
• 6,5,87

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

• 6,75,8

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

因为6+8不是素数。你受够了。

从7:开始

• 7,65,8
• 7,6,58
• 7,6,5,8

既然你找到了质数序列。

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

Answer 1

在这种情况下，回溯的想法基本上是这样的:让我找到一个子序列(或前缀)的延续。如果我成功了，我会把这个延续还给我的来电者。如果我运气不好，我会让我的来电者尝试另一个前缀。

更确切地说：

// 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++中的直接实现将非常缓慢)，但不是该序列是什么，但修改起来非常简单。

无论如何，回溯中的“回退”发生在递归调用失败的最后一行:这将提示调用实例尝试另一个前缀，因此控制流有点颠倒。

Answer 2

您的函数(不管是否伪代码)不会做任何有意义的事情。实际上，我不知道它应该做什么。即。u = 0;紧跟在if(u == 4);之后，您的isPrime函数总是传递(Integers[0]+integers[0])。

我认为，您所指的回溯更恰当地称为递归函数(一个可以调用自己的函数)。回溯是某个特定行为的糟糕(模糊)名称，递归函数可以显示这个名称。

如果您想要这样的递归函数，您需要放弃它并重新开始。用通俗易懂的英语(或其他语言)写出这个函数应该做什么。然后，一旦您知道需要传递给它的内容，失败和成功之间的区别，以及失败或成功时应该返回什么(在失败时需要如何修改向量)，就可以编写代码。

超级提示:对于整数的小选择，如您所呈现的整数，请尝试stl < algorithm >中的< algorithm >，以快速遍历向量中ints的可能安排。