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

文档介绍：回溯方法的步骤如下:
     1) 定义一个解空间,它包含问题的解。
     2) 用适于搜索的方式组织该空间。
     3) 用深度优先法搜索该空间,利用限界函数避免移动到不可能产生解的子空间。
回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻,仅保留从开始节点到当前节点的路径。因此,回溯算法的空间需求为O(从开始节点起最长路径的长度)。这个特性非常重要,因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话,再多的空间也不够用。
算法应用:
回溯算法的求解过程实质上是一个先序遍历一棵"状态树"的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中。
(1) 幂集问题(组合问题) (参见《数据结构》(严蔚敏))
     求含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中元素进行“取”或“舍”的过程,并且可以用一棵状态树来表示。求幂集元素的过程即为先序遍历这棵状态树的过程。
程序:
#include <>
#include <>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode,*LinkList;
//初始化
LinkList ListInit()
{
    LNode *base=(LinkList)malloc(sizeof(LNode));
    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&&j<i-1)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i-1)
        return ERROR;
    s=(LNode *)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&&j<i-1)
    {
        p=p->next;
        ++j;
    }
    if(!(p->next)||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;
}
//查找一个元素
int GetElem(LinkList L,int i,ElemType &e)
{
    LNode *p=L;
    int j=0;
    while(p->next&&j<i)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i)
        return ERROR;
    e=p->data;
    return OK;
}