素序列的回溯算法 [英] Backtracking algorithm for prime sequence

问题描述

我在进行回溯时遇到问题，不知道我在做什么是回溯。

我有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

从找到素数序列后开始。

这个回溯的想法基本上是这样的：让我找到一个子序列的延续（或前缀）的东西工作。如果我成功，我会返回该延续到我的调用者。

更精确地说：

如果我运气不好，我会要求我的呼叫者尝试不同的前缀。

  //最初调用Backtrack（epsilon，所有数字）
 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 ++中的直接实现将会非常缓慢），但不是那个序列是什么，但这很容易修改。

无论如何，back回溯发生在递归调用不是运气的最后一行：这将提示调用实例尝试另一个前缀，因此控制流是有点反转的。

I'm having trouble doing backtracking and not sure if what I'm doing is backtracking exactly.

I have n amount of integers for my example it will be [5,6,7,8].

From those integers I need to find if a prime sequence exists and if it does display it.

The prime sequence for this example is 7,6,5,8 since 7+6=13 6+5=11 5+8=13

To get the answer I can go through each n and then try to see if its a prime sequence.

Starting at 5:

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

Since 7+8 isn't prime. Go onto next integer.

Since 5+7 isn't prime. Go onto next integer.

• 5,8,[6,7]

Since 8+6 or 8+7 isn't prime. You're done with 5.

Starting at 6:

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

Since 7+8 isn't prime. Go onto next integer.

• 6,7[5,8]

Since 7+5 or 7+8 isn't prime. Go onto next integer.

Since 6+8 isn't prime. You're done with 6.

Starting at 7:

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

End since you found the prime sequence.

So how can I do this problem with backtracking?

解决方案

The idea of backtracking in this context is basically this: Let me find a continuation of a subsequence (or a prefix) of the total thing that works. If I'm successful I'll return that continuation to my caller. If I'm out of luck, I'll ask my caller to try a different prefix.

More precisely:

// 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;
}

Note that this algorithm will only tell you whether a sequence exists (and its straightforward implementation in C++ would be horribly slow) but not what that sequence is, but that's trivial to modify.

Anyway the "back" in backtracking happens at the very last line where the recursive call is out of luck: this will prompt the calling instance to try another prefix, so the control flow is a bit reversed.

这篇关于素序列的回溯算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！