-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

「バックトラック」とは、ソリューション スペースで 1 ステップ戻ることを意味します (これを決定木と考えて、1 レベル上に移動します)。通常、決定空間内の特定のサブツリーを除外できる場合に使用され、ソリューション空間の大部分を除外できる可能性が非常に高い場合にのみ、決定木の完全な調査と比較してパフォーマンスが大幅に向上します。 .

ここで同様のアルゴリズムの徹底的な説明を見つけることができます: Using recursion and backtracking to generate all possible conversions

于 2013-10-07T08:46:19.160 に答える