当前位置:首页 >> 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); } }


相关文章:
回溯算法(含代码).doc
回溯算法(含代码) - 回溯算法 引言 寻找问题的解的一种可靠的方法是首先列出所
回溯算法(一).doc
回溯算法(一) - 第一部分 回溯 寻找问题的解的一种可靠的方法是首先列出所有候
算法:回溯_(伪代码).doc
算法:回溯_(伪代码)_计算机软件及应用_IT/计算机_专业资料。算法:回溯_(伪代码)回溯(整体思路:时刻想着程序是在遍历解空间(树) ,将代码与遍历步骤一一对应) 变...
算法回溯法的源代码.doc
算法回溯法源代码 - #include stdafx.h // 优化了回溯代码 // 即不移动到不可能包含比当前最优解还要好的解的右子树 #include<iostream.h> templa...
回溯算法.doc
回溯算法 - 淮海工学院计算机工程学院 实验报告书 课程名:题目: 《算法分析与设计》 实验 4 回溯算法 班学姓 级: 号: 名: 软件 142 2014122886 杨志...
回溯算法_图文.ppt
n皇后问题就转换为n个数字的全排, 只需把符合要求的方案挑选出来就行了, 那么此问题就可以转换为生成n个数字的 全排,我们可以利用回溯法来实现。 代码实现: ...
回溯算法实验.doc
回溯算法实验 - 算法设计分析实验: 素数环问题和n皇后问题... 回溯算法实验_计算机软件及应用_IT/计算机_专业资料...上机前,完成程序代码的编写 2)独立完成实验及实...
回溯算法的应用.doc
回溯算法的应用_计算机软件及应用_IT/计算机_专业资料。回溯算法的应用回溯算法的应用 课程名称: 院系: 算法设计与分析 *** *** *** 学生姓名: 学号: 专业班...
回溯算法_图文.ppt
回溯算法 - 算法设计与分析 王歧 目录 ? ? ? ? ? ? ? ? 动态规划 贪心算法 状态空间搜索法 分治法 随机算法 模拟算法 递归算法 数论算法 回溯算法 ? ...
算法分析与设计复习题及参考答案.doc
网络教育课程考试复习题及参考答案算法分析与设计一、...,指定 d,用伪代码描述求解子集和问题的回溯算法。...算法分析与设计部分含计... 暂无评价 18页 1下载...
回溯算法解决N皇后问题实验及其代码.doc
回溯算法解决N皇后问题实验及其代码 - 实验报告 4 回溯算法 实验 4 一、实验目的 1)掌握回溯算法的实现原理,生成树的建立以及限界函数的实现; 2)利用回溯算法...
回溯算法的应用.doc
回溯算法的应用 - 回溯算法的应用 课程名称: 院系: 算法设计与分析 计算机科
最佳调度问题(回溯算法).doc
[k]; } } } } 三、结果与分析: 算法源代码(C++描述) /* 最佳调度问题(回溯算法) 设有 n 个任务由 k 个可并行工作的机器来完成,完成任务 i 需要时间...
回溯算法解决背包问题_源代码.doc
回溯算法解决背包问题_源代码 - template<class Typew
回溯算法_图文.ppt
回溯算法 - 回溯算法 JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信
matlab中 回溯算法.doc
matlab中 回溯算法_IT/计算机_专业资料。matlab中的...图 1 6 - 2 用树形结构给出了含三个对象的 0...程序 16-3 给出最优装载的代码 template<class T...
回溯法_图文.ppt
回溯基本问题1、位串问题问题:生成含有n个字符的所有字符串。 解题思路:使用...用这个代码测试其性能关于基本的递归 ? 在每一次递归调用前优化代码算法 一般...
算法分析复习题目及答案.doc
算法分析复习题目及答案 - 一。选择题 1、二分搜索算法是利用( A、分治策略 A )实现的算法。 C、贪心法 A D、回溯法 )。 D、定义最优解 B、动态规划法...
回溯算法设计-new_图文.ppt
回溯算法设计-new - 《计算机导论与程序设计基础》 16.2 回溯算法设计 1 提纲 一. 回溯算法的含义 二. 用回溯算法解决问题的一般步骤 三. 回溯法解题思路--...
马踏棋盘回溯算法C 源代码.pdf
马踏棋盘回溯算法C 源代码 - : 马踏棋盘回溯算法完整源代码(在 VS2010
更多相关标签: