Backtrack на любом языке программирования

Question

Мне была дана задача написать программу для перестановки строк. Я понимаю логику, но не точное значение Backtrack в этой программе. Пожалуйста, объясните функциональность for-loop, когда будет вызываться swap, когда будет называться permutate(), и точное значение backtrack.

# 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; 
} 

Answer 1

Sketching стек вызовов может помочь вам понять, как работает алгоритм. Примерная строка «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) до конца, и на каждом шаге мы меняем эту позицию с начальной точкой, рекурсивно вызываем перестановку() для печати каждая перестановка этой новой строки, и после этого мы возвращаем строку обратно в прежнее состояние, так что у нас есть исходная строка, чтобы повторить тот же процесс со следующей позицией.

Лично мне не нравится этот комментарий, говорящий «backtrack». Лучшим термином было бы «намотка назад», потому что в этот момент рекурсия возвращается обратно, и вы готовите свою строку для следующего рекурсивного вызова. Backtrack обычно используется для ситуации, в которой вы изучали поддерево, и вы не нашли решения, поэтому вы возвращаетесь назад (backtrack) и пытаетесь использовать другую ветку. Взято из Википедии:

Откат общий алгоритм для нахождения всех (или некоторых) решения некоторой вычислительной задачи, которые последовательно строит кандидатов решений, и отказывается от каждого частичного кандидата гр («откатывается») как только он определит, что c не может быть , действительное решение.

Обратите внимание, что этот алгоритм не сгенерирует множество перестановок, поскольку он может печатать одну и ту же строку более одного раза, когда повторяются буквы. Крайний случай - когда вы применяете его к строке «aaaaa» или любой другой строке с одной уникальной буквой.

Answer 2

«с возвратами» означает, что вы гонг один шаг назад в своем пространстве решений (думаю о нем, как дерево решений, и вы собираетесь на один уровень вверх). Он обычно используется, если вы можете исключить определенные поддеревья в пространстве принятия решений и значительно повысить производительность по сравнению с полным поиском дерева решений тогда и только тогда, когда очень вероятно, что вы можете исключить большие части решения space.

Вы можете найти исчерпывающий expalnation подобного алгоритма здесь: Using recursion and backtracking to generate all possible combinations