以任何編程語言回溯

-4

我被賦予編寫字符串排列程序的任務。我理解這個邏輯，但不是這個程序中Backtrack的確切含義。請解釋for循環功能，當將調用swap，調用permutate()時，以及回溯的確切含義。以任何編程語言回溯

# include <stdio.h> 


void swap (char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 


void permute(char *a, int i, int n) 
{ 
    int j; 
    if (i == n) 
    printf("%s\n", a); 
    else 
    { 
     for (j = i; j <= n; j++) 
     { 
      swap((a+i), (a+j)); 
      permute(a, i+1, n); 
      swap((a+i), (a+j)); //backtrack 
     } 
    } 
} 


int main() 
{ 
    char a[] = "ABC"; 
    permute(a, 0, 2); 
    getchar(); 
    return 0; 
}

來源

2013-10-07 Unknown User

這個問題似乎是題外話題，因爲它是關於算法理論而不是編程。 –

從你從哪裏得到CODE，你會明白所有的意思。 :) – Arya

@KerrekSB有什麼地方可以提出這類問題嗎？我想問問循環中的邏輯。它是如何工作的？ –

寫生調用堆棧可以幫助你瞭解算法是如何工作的。示例字符串「ABC」是一個很好的起點。基本上，這是將與ABC發生什麼：

permute(ABC, 0, 2) 
    i = 0 
    j = 0 
    permute(ABC, 1, 2) 
     i = 1 
     j = 1 
     permute(ABC, 2, 2) 
      print "ABC" 
     j = 2 
     string = ACB 
     permute(ACB, 2, 2) 
      print "ACB" 
     string = ABC 
    j = 1 
    string = BAC 
    permute(BAC, 1, 2) 
     .... (everything starts over)

像往常一樣，在上面的例子中，凹口限定內部的每個遞歸調用的發生了什麼。

for循環背後的推理是，字符串ABC的每個排列由ABC，BAC和CBA，以及子字符串BC，AC和BA的每個排列（從每個前面的字母中刪除第一個字母）給出。對於任何字符串S，可能的排列是通過交換每個位置與第一個位置以及每個這些字符串的所有排列來獲得的。可以這樣想：任何排列後的字符串都必須以原始字符串中的一個字母開始，因此您將每個可能的字母放在第一個位置，並遞歸地將相同的方法應用於字符串的其餘部分（不帶第一個字母）。

這就是循環所做的事情：我們從當前的起始點（即i）掃描字符串直到結束，並且在每一步我們將該位置與起點交換，遞歸調用permute（）打印這個新字符串的每個置換，然後我們將字符串恢復到它以前的狀態，以便我們有原始字符串在下一個位置重複相同的過程。

就我個人而言，我不喜歡那個評論說「回溯」。一個更好的術語是「回捲」，因爲在那時遞歸會回退，並且您準備好下一個遞歸調用的字符串。回溯通常用於您探索子樹並且您沒有找到解決方案的情況，因此您要回退（回溯）並嘗試不同的分支。從維基百科：

回溯查找所有（或部分）解決一些計算問題的通用算法，即逐步建立考生的解決方案，並放棄每個部分候選人C （「回溯」）只要它確定c不可能完成到一個有效的解決方案。

請注意，此算法不會生成一組置換，因爲它可以在重複字母時多次打印相同的字符串。一個極端的情況是，當你將它應用到字符串「aaaaa」或任何其他具有唯一字母的字符串時。

來源

2013-10-07 09:16:23

「回溯」的意思，你在你的解空間鑼退一萬步（認爲它作爲一個決策樹。你要去上一級）。如果您可以排除決策空間中的某些子樹，並且與完全探索決策樹相比，可以顯着提高性能，那麼通常會使用它，當且僅當您很可能可以排除解決方案的較大部分空間。

你可以找到類似的算法這裏的詳盡expalnation：Using recursion and backtracking to generate all possible combinations

來源

2013-10-07 08:46:19 OBu

你描述的是「分支和綁定」而不是回溯。 http://en.wikipedia.org/wiki/Branch_and_bound。 '分支定界算法由所有候選解的系統列舉組成，其中大部分無結果候選者被丟棄**集體**，通過使用被優化的數量的上限和下限估計邊界。' – fjardon

不，分支和界限是通過使用上限和下限的估計範圍來降低無結果的候選人**集體** - 這與我的研究中的描述有所不同。（你不需要回溯中的估計邊界） – OBu

你是對的，我誤解了你的答案的一部分。 – fjardon

以任何編程語言回溯

回答

相關問題