c++ - 任何编程语言的回溯

Closed. This question is off-topic。它当前不接受答案。












                            想改善这个问题吗？ Update the question，所以它是on-topic，用于堆栈溢出。

                        6年前关闭。



我被赋予编写字符串置换程序的任务。我理解该程序的逻辑，但不了解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;
}

最佳答案

绘制调用堆栈草图可以帮助您了解算法的工作原理。示例字符串“ 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
  （“ backtracks”）一旦确定c不可能是
  完成有效的解决方案。

请注意，此算法不会生成排列集，因为当重复的字母出现时，它可以多次打印同一字符串。一种极端情况是将其应用于字符串“ aaaaa”或带有一个唯一字母的任何其他字符串。

关于c++ - 任何编程语言的回溯，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19220216/