-2

我的任务是编写一个字符串置换程序。我理解逻辑,但不是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;
}
4

2 回答 2

0

绘制调用堆栈可以帮助您了解算法的工作原理。示例字符串“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-07T09:16:23.817 回答
0

“回溯”意味着,您在解决方案空间中倒退了一步(将其视为决策树,您正在上升一级)。如果您可以排除决策空间中的某些子树,则通常使用它,并且与对决策树的全面探索相比,当且仅当您很有可能可以排除解决方案空间的较大部分时,才可以显着提高性能.

您可以在此处找到对类似算法的详尽解释:使用递归和回溯生成所有可能的组合

于 2013-10-07T08:46:19.160 回答