当前位置:首页 >> IT/计算机 >>

回溯算法(含代码)


回溯算法
引言 寻找问题的解的一种可靠的方法是首先列出所有候选解,然后依次检查每一个,在检查完所有或部分 候选解后,即可找到所需要的解。理论上,当候选解数量有限并且通过检查所有或部分候选解能够得到所 需解时,上述方法是可行的。不过,在实际应用中,很少使用这种方法,因为候选解的数量通常都非常大 (比如指数级,甚至是大数阶乘) ,即便采用最快的计算机也只能解决规模很小的问题。对候选解进行系统 检查的方法有多种,其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检 查通常会使问题的求解时间大大减少(无论对于最坏情形还是对于一般情形) 。事实上,这些方法可以使我 们避免对很大的候选解集合进行检查,同时能够保证算法运行结束时可以找到所需要的解。因此,这些方 法通常能够用来求解规模很大的问题。 算法思想 回溯(backtracking)是一种系统地搜索问题解答的方法。为了实现回溯,首先需要为问题定义一个 解空间(solution space) ,这个空间必须至少包含问题的一个解(可能是最优的) 。 下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图(迷宫问题)或树(N 皇后问题)。 一旦定义了解空间的组织方法,这个空间即可按深度优先的方法从开始节点进行搜索。 回溯方法的步骤如下: 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 <stdio.h> #include <malloc.h> #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; } //输出链表元素 void Display(LinkList L) { LNode *p=L; if(!(p->next)) { printf("NULL,"); return; } else p=p->next; while(p) { printf("%d,",p->data); p=p->next; } } //求幂集 void PowerSet(int i,LinkList A,LinkList &B) { int k=0; ElemType e=0; if(i>ListLength(A)) { Display(B); printf("\n"); } else { GetElem(A,i,e); k=ListLength(B); ListInsert(B,k+1,e); PowerSet(i+1,A,B);

ListDelete(B,k+1,e); PowerSet(i+1,A,B); } } int main() { LinkList list=ListInit(); //初始化 LinkList list2=ListInit();//初始化 ListInsert(list,1,1);//插入元素 ListInsert(list,2,2); ListInsert(list,3,3); Display(list);//输出元素 printf("\npower set is:\n"); PowerSet(1,list,list2);//求幂集 }

(2)迷宫问题 迷宫问题(参见《数据结构》 (严蔚敏)) 迷宫问题 计算机解迷宫时,通常用的是"试探和回溯"的方法,即从入口出发,顺某一方向向前探索,若能走通,则 继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止,如果所有可能 的通路都试探过,还是不能走到终点,那就说明该迷宫不存在从起点到终点的通道。 1.从入口进入迷宫之后,不管在迷宫的哪一个位置上,都是先往东走,如果走得通就继续往东走,如 果在某个位置上往东走不通的话,就依次试探往南、往西和往北方向,从一个走得通的方向继续往前直到 出口为止; 2.如果在某个位置上四个方向都走不通的话,就退回到前一个位置,换一个方向再试,如果这个位置 已经没有方向可试了就再退一步,如果所有已经走过的位置的四个方向都试探过了,一直退到起始点都没 有走通,那就说明这个迷宫根本不通;

3.所谓"走不通"不单是指遇到"墙挡路",还有"已经走过的路不能重复走第二次",它包括"曾经走过 而没有走通的路"。显然为了保证在任何位置上都能沿原路退回,需要用一个"后进先出"的结构即栈来保存 从入口到当前位置的路径。并且在走出出口之后,栈中保存的正是一条从入口到出口的路径。 由此,求迷宫中一条路径的算法的基本思想是: 若当前位置"可通",则纳入"当前路径",并继续朝"下一位置"探索;若当前位置"不可通",则应顺着"来的 方向"退回到"前一通道块",然后朝着除"来向"之外的其他方向继续探索;若该通道块的四周四个方块均" 不可通",则应从"当前路径"上删除该通道块。 设定当前位置的初值为入口位置; do{ 若当前位置可通, 则{ 将当前位置插入栈顶; // 纳入路径

若该位置是出口位置,则算法结束; // 此时栈中存放的是一条从入口位置到出口位置的路径 否则切换当前位置的东邻方块为新的当前位置; } 否则 { 若栈不空且栈顶位置尚有其他方向未被探索, 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块; 若栈不空但栈顶位置的四周均不可通, 则{ 删去栈顶位置; // 从路径中删去该通道块 若栈不空,则重新测试新的栈顶位置, 直至找到一个可通的相邻块或出栈至栈空; } } } while (栈不空); 程序如下:

#include <stdio.h> #define WALL 0 //墙 #define CORRIDOR 1 //通道 #define PATH 9 //为路径上的一块 #define TRIED 2 // #define ROW_NUM 7 //迷宫数组行数 #define COL_NUM 13 //列数 #define TRUE 1 #define FALSE 0 #define MAXSIZE 50 typedef struct { int row; int col; }PosType; typedef struct { int ord; //通道块在路径上的"序号" PosType seat; //通道块在迷宫中的坐标 int di; //当前通道块的方向 }SElemType; typedef struct {

SElemType S[MAXSIZE]; int top; }MazeType; //迷宫 int grid[ROW_NUM][COL_NUM]={{1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1}, {1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1}, {1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1}, {1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}}; //当前位置是否可以通过 bool Valid(PosType pos) { if(pos.row>=0&&pos.row<=ROW_NUM&&pos.col>=0&&pos.col<=COL_NUM&&grid[po s.row][pos.col]==CORRIDOR) return TRUE; else return FALSE; } void FootPrint(PosType pos)//留下足迹 { grid[pos.row][pos.col]=PATH; } void Undo(PosType pos) //留下不能通过的标识 { grid[pos.row][pos.col]=TRIED; } //当前位置的下一个位置 PosType NextPos(PosType cur,int di) { PosType next; switch(di) { case 0: //东 next.row=cur.row; next.col=cur.col+1; break; case 1: //南 next.row=cur.row+1; next.col=cur.col; break; case 2: //西 next.row=cur.row;

next.col=cur.col-1; break; case 3: //北 next.row=cur.row-1; next.col=cur.col; break; } return next; } //是否到达终点 bool Done(PosType cur,PosType end) { if(cur.row==end.row&&cur.col==end.col) return TRUE; else return FALSE; } //寻找迷宫路径 bool MazePath(MazeType &path,PosType start,PosType end) { SElemType e; path.top=-1; int step=1; PosType curpos=start; do { if(Valid(curpos)) { FootPrint(curpos); e.ord=step; e.di=0; e.seat=curpos; path.S[++path.top]=e; if(Done(curpos,end)) return TRUE; curpos=NextPos(curpos,0); step++; } else { if(path.top>-1)//棧不空 { e=path.S[path.top--]; while(e.di==3&&path.top>-1)

{ Undo(e.seat); e=path.S[path.top--]; } if(e.di<3) { e.di++; path.S[++path.top]=e; curpos=NextPos(e.seat,e.di); } }//if }//else }while(path.top>-1); return FALSE; } //输出路径 void PrintPath(MazeType path) { int i=0; while(i<=path.top) { printf("第%d 步:(%d,%d)\n",path.S[i].ord,path.S[i].seat.row,path.S[i].seat.col); i++; } } //输出路径 void PrintPath2() { for(int i=0;i<ROW_NUM;i++) for(int j=0;j<COL_NUM;j++) if(grid[i][j]==PATH) printf("(%d,%d)\n",i,j); } int main() { MazeType path; PosType start={0,0},end={6,12}; if(MazePath(path,start,end)) PrintPath(path); else printf("not reachable!\n"); PrintPath2(); }

(3)N 皇后问题 皇后问题: 在一个 N*N 的棋盘上放置 N 个皇后,且使得每两个之间不能互相攻击,也就是使得每两个不在同一行, 同一列和同一斜角线上。 对于 N=1,问题的解很简单,而且我们很容易看出对于 N=2 和 N=3 来说,这个问题是无解的。所让我 们考虑 4 皇后问题并用回溯法对它求解。因为每个皇后都必须分别占据—行,我们需要做的不过是为图 1 棋盘上的每个皇后分配一列。

我们从空棋盘开始,然后把皇后 1 放到它所在行的第一个可能位置上,也就是第一行第—列。对于皇 后 2,在经过第一列和第二列的失败尝试之后,我们把它放在第一个可能的位置,就是格子〔2,3),位于 第二行第二列的格子。这被证明是一个死胡同,因为皇后:将没有位置可放。所以,该算法进行回溯,把皇 后 2 放在下一个可能位置(2,4)上。然后皇后 3 就可以放在(3,2),这被证明是另一个死胡同。该算法然 后就回溯到底,把皇后 1 移到(1,2)。接着皇后 2 到(2,4),皇后 3 到(3,1),而皇后 4 到(4,3),这 就是该问题的一个解。图 2 给出了这个查找的状态空间树。

程序如下:

#include <stdio.h> #include <math.h> #define N 4 int col[N+1]; //输出结果

void Output() { for(int i=1;i<=N;i++) { printf("(%d,%d)\n",i,col[i]); } printf("\n"); } //求解函数 void Queen(int i,int n) { if(i>n) Output(); else { for(int j=1;j<=n;++j) { int k=1; col[i]=j; while(k<i) { if((col[k]-col[i])*(fabs(col[k]-col[i])-fabs(k-i))!=0) { k++; if(k==i) Queen(i+1,n); } else { break; } } } } } int main() { printf("the answer is:\n"); for(int i=1;i<=N;i++) { col[1]=i; //设置第一行 Queen(2,N); } }


赞助商链接
相关文章:
回溯算法的实验报告
回溯算法的实验报告 - 南华大学 计算机科学与技术学院 实验报告( 2016 ~2017 学年度 第二 学期 ) 课程名称 实验名称 程序设计语言与编译 回溯算法分析 姓名 何....
回溯算法解决批处理作业
回溯算法解决批处理作业_计算机软件及应用_IT/计算机_专业资料。算法分析代码实现及实验报告 回溯算法---解决批处理作业调度问题 回溯算法---解决批处理作业调度问题...
回溯算法1.0
编写程序,实现符号三角形问题算法 实验要求:利用回溯算法思想写出算法的程序代码。 算法分析: 回溯算法也叫试探法,它是一种系统地搜索问题的 解的方法。 回溯算法...
实验4 回溯算法
《算法设计与分析》实验报告 实验 4 回溯算法 姓名 学号 班级网络 131 实验...算法分析 时间复杂度:O(2n) 空间复杂度:O(n) 5、关键代码(含注释) #...
实验六 回溯算法
实验六 回溯算法 - 实验六 回溯算法(2 学时) 一、实验目的与要求 1、掌握装载问题的回溯算法; 2、初步掌握回溯算法; 二、实验题 有一批共 n 个集装箱要装...
回溯算法实验 - 频道分配问题
使用在线测评的算法题目评分系统来测试所写代码; 2、通过直观的应用问题,加深对回溯算法的理解; 三、实验环境任意 C 或 C++编写调试工具,北京大学 ICPC 在线测评...
算法实验报告:回溯法(C语言)
实验代码#include <stdio.h> #include <stdlib.h> #define max 8 int queen...回溯法使用约束函数剪 去不含可行解的分枝。当使用回溯法求最优化问题时,需要...
实验4 回溯算法
《算法设计与分析》实验报告 实验 4 二、实验环境 1、硬件环境 回溯算法 一、...算法分析 时间复杂度:O(2n) 空间复杂度:O(n) 5、关键代码(含注释) #...
实验五 回溯算法的设计与实现
实验五 回溯算法的设计与实现 - 学生实验报告 学 院: 软件与通信工程学院 算法分析与设计 软件 144 班 刘洋 0144119 课程名称: 专业班级: 姓学名: 号:...
算法:回溯_(伪代码)
算法:回溯_(伪代码)_计算机软件及应用_IT/计算机_专业资料。算法:回溯_(伪代码)回溯(整体思路:时刻想着程序是在遍历解空间(树) ,将代码与遍历步骤一一对应) 变...
更多相关标签: