0

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?

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++ での単純な実装は非常に遅くなります)、そのシーケンスが何であるかは通知しないことに注意してください。ただし、変更するのは簡単です。

とにかく、バックトラッキングの「バック」は、再帰呼び出しがうまくいかない最後の行で発生します。これにより、呼び出し元のインスタンスが別のプレフィックスを試すように促されるため、制御フローが少し逆になります。

于 2012-04-11T01:29:49.887 に答える
1

あなたの関数（擬似コードであろうとなかろうと）は何も生産的ではありません。私は実際にそれが何をすべきかわからない。すなわち。u = 0;直後に続くif(u == 4);と、isPrime関数は常に渡され(Integers[0]+integers[0])ます。

あなたがバックトラッキングと呼んでいるものは、より適切には再帰関数（それ自体を呼び出すことができる関数）と呼ばれていると思います。バックトラッキングは、再帰関数が示す可能性のある特定の動作の貧弱な（あいまいな）名前です。

このような再帰関数が必要な場合は、これを破棄して最初からやり直す必要があります。関数が何をすべきかを平易な英語（または他の言語）で書きなさい。次に、何を渡す必要があるか、失敗と成功の違い、失敗または成功時に何を返すか（失敗時にベクトルをどのように変更する必要があるか）がわかったら、それをコーディングします。

スーパーヒント：あなたが提示するような整数の小さな選択についてnext_permutation()は、stlで試して< algorithm >、ベクトル内のintの可能な配置をすばやく調べてください。

于 2012-04-11T01:55:05.163 に答える