算法系列---回溯算法引言
尋找問(wèn)題的解的一種可靠的方法是首先列出所有候選解，然后依次檢查每一個(gè)，在檢查完所有或部分候選解后，即可找到所需要的解。理論上，當(dāng)候選解數(shù)量有限并且通過(guò)檢查所有或部分候選解能夠得到所需解時(shí)，上述方法是可行的。不過(guò)，在實(shí)際應(yīng)用中，很少使用這種方法，因?yàn)楹蜻x解的數(shù)量通常都非常大（比如指數(shù)級(jí)，甚至是大數(shù)階乘），即便采用最快的計(jì)算機(jī)也只能解決規(guī)模很小的問(wèn)題。對(duì)候選解進(jìn)行系統(tǒng)檢查的方法有多種，其中回溯和分枝定界法是比較常用的兩種方法。按照這兩種方法對(duì)候選解進(jìn)行系統(tǒng)檢查通常會(huì)使問(wèn)題的求解時(shí)間大大減少（無(wú)論對(duì)于最壞情形還是對(duì)于一般情形）。事實(shí)上，這些方法可以使我們避免對(duì)很大的候選解集合進(jìn)行檢查，同時(shí)能夠保證算法運(yùn)行結(jié)束時(shí)可以找到所需要的解。因此，這些方法通常能夠用來(lái)求解規(guī)模很大的問(wèn)題。 算法思想 回溯方法的步驟如下： 算法應(yīng)用  #include <stdio.h>#include <malloc.h>#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)); base->data=0; base->next=NULL; return base;}//插入一個(gè)元素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;}//刪除一個(gè)結(jié)點(diǎn)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);}//長(zhǎng)度int ListLength(LinkList L){ LinkList p=L; int j=0; if(!L) return ERROR; while(p->next) { p=p->next; ++j; } return j;}//查找一個(gè)元素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)迷宮問(wèn)題(參見(jiàn)《數(shù)據(jù)結(jié)構(gòu)》（嚴(yán)蔚敏）) 1．從入口進(jìn)入迷宮之后，不管在迷宮的哪一個(gè)位置上，都是先往東走，如果走得通就繼續(xù)往東走，如果在某個(gè)位置上往東走不通的話，就依次試探往南、往西和往北方向，從一個(gè)走得通的方向繼續(xù)往前直到出口為止； 2．如果在某個(gè)位置上四個(gè)方向都走不通的話，就退回到前一個(gè)位置，換一個(gè)方向再試，如果這個(gè)位置已經(jīng)沒(méi)有方向可試了就再退一步，如果所有已經(jīng)走過(guò)的位置的四個(gè)方向都試探過(guò)了，一直退到起始點(diǎn)都沒(méi)有走通，那就說(shuō)明這個(gè)迷宮根本不通； 由此，求迷宮中一條路徑的算法的基本思想是： 設(shè)定當(dāng)前位置的初值為入口位置； 程序如下:
#include <stdio.h>#define WALL 0 //墻#define CORRIDOR 1 //通道#define PATH 9 //為路徑上的一塊#define TRIED 2 //#define ROW_NUM 7 //迷宮數(shù)組行數(shù)#define COL_NUM 13 //列數(shù)#define TRUE 1#define FALSE 0#define MAXSIZE 50typedef struct { int row; int col;}PosType;typedef struct { int ord; //通道塊在路徑上的"序號(hào)" PosType seat; //通道塊在迷宮中的坐標(biāo) int di; //當(dāng)前通道塊的方向}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}};//當(dāng)前位置是否可以通過(guò)bool Valid(PosType pos){ if(pos.row>=0&&pos.row<=ROW_NUM&&pos.col>=0&&pos.col<=COL_NUM&&grid[pos.row][pos.col]==CORRIDOR) return TRUE; else return FALSE;}void FootPrint(PosType pos)//留下足跡{ grid[pos.row][pos.col]=PATH;}void Undo(PosType pos) //留下不能通過(guò)的標(biāo)識(shí){ grid[pos.row][pos.col]=TRIED;}//當(dāng)前位置的下一個(gè)位置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;}//是否到達(dá)終點(diǎn)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皇后問(wèn)題:
#include <stdio.h>#include <math.h>#define N 4int col[N+1];//輸出結(jié)果void Output(){ for(int i=1;i<=N;i++) { printf("(%d,%d)\n",i,col[i]); } printf("\n");}//求解函數(shù)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; //設(shè)置第一行 Queen(2,N); }}結(jié)果如下: 標(biāo)簽: 算法 |
|
|
