以任何编程语言回溯

-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

以任何编程语言回溯

回答

相关问题