回溯法要如何理解

回溯法要怎么理解？
我遇到过一些回溯算法，总是不能理解，比如下面这个输出1234四个数全排列的程序，要怎么理解呢？求大神解释

C/C++ code

#include <stdio.h>#include <assert.h>#define swap(A, a, b, tmp)\{\         (tmp) = A[(a)];\         A[(a)] = A[(b)];\         A[(b)] = (tmp);\ }  void print_r(const int A[], int len);void perm(int A[], int start, int end, int len);int main(){        int A[4] = {1, 2, 3, 4};        perm(A, 0, 3, 4);        getchar();        return 0;}void print_r(const int A[], int len){        assert(NULL != A);        int i;        for (i = 0; i < len; i++)                printf("%d ", A[i]);        printf("\n");}void perm(int A[], int start, int end, int len){        assert(NULL != A);        int i, tmp = 0;        if (start == end) {                print_r(A, len);        } else {                for (i = start; i <= end; i++) {                        swap(A, i, start, tmp);                        perm(A, start+1, end, len);                        swap(A, i, start, tmp);                }        }}

[解决办法]
所谓有路则通,无路则返.

这个算法的理解,你还是用小数据,比如2个,3个,4个这样模拟一两遍程序运行就知道了.
[解决办法]
用迷宫问题或者8皇后什么的，拿最简单的模拟一下，就是让迷宫小一点或者4皇后。
简单的说就是有路就一直走，没路就返回。
你可以想象你在一个迷宫里，要找出口，刚开始你只能沿着某个方向一直走，如果发现是死路，就只好回头，然后重走。

查看更多 下一篇