回溯算法的黃金序列

我無法做回溯和不知道我在做什麼恰好回溯。回溯算法的黃金序列

我有一個整數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

自從您找到主要序列後結束。

那麼我怎樣才能回溯這個問題呢？

來源

2012-04-11 Claud

我有點麻煩，告訴你真正的問題是什麼。你願意澄清一下嗎？ – bitmask 2012-04-11 01:17:30

如何用遞歸回溯來解決這個問題？什麼是回溯到這個問題？ – Claud 2012-04-11 01:21:31

優化算法的一種方法是忽略奇數，奇數（除了1,1）或偶數的情況，即使它總是偶數和唯一的偶數質數是2. – twain249 2012-04-11 01:24:37

在這種情況下回溯的想法基本上是這樣的：讓我找到一個工作總的東西的子序列（或前綴）的延續。如果我成功了，我會將這個延續返回給我的調用者。如果我運氣不好，我會要求呼叫者嘗試不同的前綴。

更確切地說：

// 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-11 01:29:49 bitmask

我還在試着去了解。我知道這看起來很簡單，但我無法控制。如果我的fixedPrefix = [5]和我的unbound = [6,7,8]。它檢查所有未綁定的元素。然後花6並檢查5 + 6是否爲素數？那麼如果它是fixedPrefix變成[5,6]和unbound變成[7,8]？ – Claud 2012-04-11 01:45:23

@ Claud25：不，這將是一個可能的優化。現在，只有在遞歸的最後一級達到時，纔會檢查整個序列。你可能已經放棄了在任何情況下都不會導致有效序列的前綴，但是我沒有在這個答案中包括這個，以使核心思想更加清晰。 – bitmask 2012-04-11 08:09:15

你的函數（僞代碼與否）不會產生任何效果。我實際上不確定它應該做什麼。即。 u = 0;緊接着是if(u == 4);和isPrime函數總是通過(Integers[0]+integers[0])。

我相信你所說的backtracking更適合稱爲遞歸函數（可以調用自己的函數）。回溯是一個遞歸函數可以表現的特定行爲的窮（模糊）名稱。

如果你想要一個遞歸函數，你需要取消這個並重新開始。用純英文（或其他語言）寫出函數的功能。然後，一旦你知道你需要傳遞給它的代碼，失敗和成功之間的區別以及在失敗或成功時返回什麼（在失敗時如何修改向量）。

超級提示：對於小數目的整數選擇，例如您出席的，請在stl <algorithm>中嘗試next_permutation()以快速檢查向量中可能的整數排列方式。

來源

2012-04-11 01:55:05 dB8

顯然我的僞代碼是廢話，但我在紙上和我的例子中用英文做了這個問題。我只想知道如何通過回溯來完成我在紙上做的事情。所以回溯只是一個遞歸函數，但如果它是死衚衕，它會停止？ – Claud 2012-04-11 02:00:15

馬虎英語：是矢量[n] +矢量[n + 1]素數？如果是這樣，通過向其傳遞向量和n + 1再次調用函數來嘗試向量[n + 1] +向量[n + 2]。如果是，並且n + 1是向量的最後一個值，則返回true。如果沒有，請將函數交換爲向量中的一些值並返回false。 – dB8 2012-04-11 02:09:37

備註：如果您在遞歸函數中使用任何複雜類型（如），並且您可以允許修改它，請按引用傳遞。即。 '布爾回溯（＆myvec會，INT N）{}' – dB8 2012-04-11 02:24:26

回溯算法的黃金序列

回答

相關問題