回溯算法原理和几个常用的算法实例

《回溯算法原理和几个常用的算法实例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、回溯算法思想：     回溯（backtracking）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（solutionspace），这个空间必须至少包含问题的一个解（可能是最优的）。    下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图(迷宫问题)或树(N皇后问题)。一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。回溯方法的步骤如下：    1)定义一个解空间，它包含问题的解。     2)用适于搜索的方式组织该空间。    3)用深度

2、优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。算法应用：回溯算法的求解过程实质上是一个先序遍历一棵"状态树"的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中。(1)幂集问题(组合问题)(参见《数据

3、结构》（严蔚敏）)    求含N个元素的集合的幂集。    如对于集合A={1,2,3},则A的幂集为    p(A)={{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},Φ}幂集的每个元素是一个集合，它或是空集，或含集合A中的一个元素，或含A中的两个元素，或者等于集合A。反之，集合A中的每一个元素，它只有两种状态：属于幂集的元素集，或不属于幂集元素集。则求幂集P（A）的元素的过程可看成是依次对集合A中元素进行“取”或“舍”的过程，并且可以用一棵状态树来表示。求幂集元素的过程即为

4、先序遍历这棵状态树的过程。程序：#include #include #define ERROR 0#define OK 1typedef int ElemType;typedef struct LNode{    ElemType data;    struct LNode *next;} LNode,*LinkList;//初始化LinkList ListInit(){    LNode *base=(LinkList)malloc(sizeof(LNode)); 

5、   base->data=0;    base->next=NULL;    return base;}//插入一个元素int ListInsert(LinkList L,int i,ElemType e){    LNode *p,*s;    int j=0;    p=(LNode *)L;    while(p&&jnext;        ++j;    }    if(!p

6、

7、j>i-1)        return ERROR;    s=(L

8、Node *)malloc(sizeof(LNode));    s->data=e;    s->next=p->next;    p->next=s;    return OK;}//删除一个结点int ListDelete(LinkList &L,int i,ElemType &e){    LinkList p=L,q;    int j=0;    while(p->next&&jnext;        ++j;    }    if(!(p->n

9、ext)

10、

11、j>i-1)        return ERROR;    q=p->next;    p->next=q->next;    e=q->data;    free(q);}//长度int ListLength(LinkList L){    LinkList p=L;    int j=0;    if(!L)        return ERROR;    while(p->next)    {        p=p->next;        ++j;    }    return j

12、;}//查找一个元素int GetElem(LinkList L,int i,ElemType &e){    LNode *p=L;    int j=0;    while(p->next&&jnext;        ++j;    }    if(!p

13、

14、j>i)        return ERROR;    e=p->data;    return OK;}//输出链表元素