第二講回溯法

第二講回溯法第1頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月關(guān)于搜索人類(lèi)的思維過(guò)程既是一個(gè)搜索過(guò)程。先來(lái)看一個(gè)智力游戲第2頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月傳教士與野人有三個(gè)傳教士和三個(gè)野人渡河，河邊有一條船，每次只能乘坐2人，為了傳教士的安全，應(yīng)如何規(guī)劃渡船方案，使得任何時(shí)刻，在河的兩岸及船上，傳教士的人數(shù)不能少于野人數(shù)。 第3頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第4頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月搜索分類(lèi)第5頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月基本思想回溯法是一種通用性解法，可以將回溯法看作是帶優(yōu)化的窮舉法?；厮莘ǖ幕舅枷胧窃谝豢煤袉?wèn)題全部可能解的狀態(tài)空間樹(shù)上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點(diǎn)。搜索過(guò)程中，每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，則判斷該結(jié)點(diǎn)為根的子樹(shù)是否含有問(wèn)題的解，如果可以確定該子樹(shù)中不含有問(wèn)題的解，則放棄對(duì)該子樹(shù)的搜索，退回到上層父結(jié)點(diǎn)，繼續(xù)下一步深度優(yōu)先搜索過(guò)程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài)空間樹(shù)，再進(jìn)行搜索，而是在搜索過(guò)程，逐步構(gòu)造出狀態(tài)空間樹(shù)，即邊搜索，邊構(gòu)造。第6頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第7頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月應(yīng)用步驟1、確定問(wèn)題狀態(tài)結(jié)構(gòu)；2、分析問(wèn)題狀態(tài)空間樹(shù)；3、確定深度搜索與回溯規(guī)則；4、確定解狀態(tài)判別規(guī)則；第8頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月二個(gè)問(wèn)題八皇后問(wèn)題全排列問(wèn)題第9頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月N皇后問(wèn)題問(wèn)題：在一個(gè)n×n的棋盤(pán)上布置n個(gè)王后，使其相互不能攻擊，即每行、每列，每斜線(xiàn)都只有一個(gè)皇后；問(wèn)題的狀態(tài)即棋盤(pán)的布局狀態(tài)，狀態(tài)空間樹(shù)的根為空棋盤(pán)，每個(gè)布局的下一步可能布局為該布局結(jié)點(diǎn)的子結(jié)點(diǎn)；由于可以預(yù)知，在每行中有且只有一個(gè)王后，因此為了簡(jiǎn)化狀態(tài)空間樹(shù)，采用逐行布局的方式，即每個(gè)布局有n個(gè)子結(jié)點(diǎn)；第10頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月N后問(wèn)題回溯過(guò)程分析1、從空棋盤(pán)起，逐行放置棋子。2、每在一個(gè)布局中放下一個(gè)棋子，即推演到一個(gè)新的布局。3、如果當(dāng)前行上沒(méi)有可合法放置棋子的位置，則回溯到上一行，重新布放上一行的棋子。第11頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月N后問(wèn)題算法描述初始化空棋盤(pán)（起始狀態(tài)）；從第一行開(kāi)始準(zhǔn)備放子，直至第一行出現(xiàn)回溯在當(dāng)前行r中查找下一個(gè)可以放置王后的位置

如果找到了可以擺放的位置放下一個(gè)子

如果已經(jīng)是最后一行得到一個(gè)解撤掉該子，繼續(xù)尋找下一個(gè)解

否則（未到最后一行）準(zhǔn)備處理下一行

否則（沒(méi)有找到可以擺放的位置）回溯到上一行，并撤掉該行的棋子第12頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月第13頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月算法偽碼得到求解皇后問(wèn)題的算法如下：

{

輸入棋盤(pán)大小值n；

m=0;

good=1;

do{

if(good)

if(m==n)

{

輸出解；

改變之，形成下一個(gè)候選解;

}

else

擴(kuò)展當(dāng)前候選接至下一列；

else

改變之，形成下一個(gè)候選解；

good=檢查當(dāng)前候選解的合理性；

}while(m!=0);

}第14頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月引入輔助變量一維數(shù)組（col[]），值col表示在棋盤(pán)第i列、col行有一個(gè)皇后。例如：col[3]=4，就表示在棋盤(pán)的第3列、第4行上有一個(gè)皇后。另外，為了使程序在找完了全部解后回溯到最初位置，設(shè)定col[0]的初值為0當(dāng)回溯到第0列時(shí)，說(shuō)明程序已求得全部解，結(jié)束程序運(yùn)行。數(shù)組a[]，a[k]表示第k行上還沒(méi)有皇后；數(shù)組b[]，b[k]表示第k列右高左低斜線(xiàn)上沒(méi)有皇后；數(shù)組c[]，c[k]表示第k列左高右低斜線(xiàn)上沒(méi)有皇后；第15頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月【程序】

#include

<stdio.h>

#include

<stdlib.h>

#define

MAXN

20

intn,m,good;

intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

voidmain()

{

intj;

charawn;

printf(“Entern:

“);

scanf(“%d”,&n);

for(j=0;j<=n;j++)

a[j]=1;

for(j=0;j<=2*n;j++)

cb[j]=c[j]=1;

m=1;

col[1]=1;

good=1;

col[0]=0;

do{

if(good)

if(m==n)

{

printf(“列\(zhòng)t行”);

for(j=1;j<=n;j++)

printf(“%3d\t%d\n”,j,col[j]);

printf(“Enteracharacter(Q/qforexit)!\n”);

scanf(“%c”,&awn);

if(awn==’Q’||awn==’q’)

exit(0);

while(col[m]==n)

{

m--;

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;

}

col[m]++;

}

else

{

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;

col[++m]=1;

}

else

{

while(col[m]==n)

{

m--;

a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;

}

col[m]++;

}

good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];

}while(m!=0);

}

第16頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月全排列問(wèn)題問(wèn)題生成1..n的全排列。問(wèn)題狀態(tài)可以將一個(gè)局部排列看作一個(gè)問(wèn)題狀態(tài)。問(wèn)題狀態(tài)空間樹(shù)由空排列出發(fā)，在一個(gè)局部排列上每增排一位數(shù)字，即可得到新的一個(gè)排列。所有局部排列之間的推導(dǎo)關(guān)系即可構(gòu)成一棵問(wèn)題狀態(tài)空間樹(shù)。輔助向量設(shè)計(jì)可設(shè)置輔助向量D1..n，其中Di表示i是否已經(jīng)被排列。第17頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月全排列問(wèn)題算法描述初始化空排列，開(kāi)始逐位進(jìn)行排列；循環(huán)，直到第一位出現(xiàn)回溯尋找當(dāng)前位的下一個(gè)可排列數(shù)字；若存在可排列數(shù)字排列若已排列滿(mǎn)，則輸出一個(gè)排列，并刪除該位（準(zhǔn)備下一個(gè)排列）否則準(zhǔn)備排列下一位否則（無(wú)可排列數(shù)字）退回上一位，并刪除所排列數(shù)字第18頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月回溯法的分析一個(gè)可以用回溯法求解的問(wèn)題，通?？梢员硎鰹橐韵滦问剑?/p>

對(duì)由n元組(x1,x2,…,xn)組成的狀態(tài)空間E={(x1,…,xn)}，給定n元組上的一個(gè)約束集D，求：E中滿(mǎn)足D的全部約束條件的所有n元組。將E中滿(mǎn)足D的全部約束條件的一個(gè)n元組稱(chēng)為問(wèn)題的一個(gè)解。通常約束集D具有完備性，即若i元組(x1…xi)滿(mǎn)足D中僅涉及x1…xi的所有約束，則(x1…xj)j<i也滿(mǎn)足D中僅涉及x1…xj的所有約束；也就是說(shuō)，若(x1…xj)不能滿(mǎn)足D中所有涉及x1…xj的約束，則任何以(x1…xj)為前綴的i元組(x1…xi)i>j也不能滿(mǎn)足D中涉及x1…xi的約束，不必再繼續(xù)搜索問(wèn)題的解。第19頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月回溯法的分析回溯求解的效率在很大程度上依賴(lài)于：

產(chǎn)生局部解的時(shí)間；

計(jì)算約束所需的時(shí)間；

滿(mǎn)足局部約束的解的個(gè)數(shù)；通?？梢詰?yīng)用重排原理，先搜索分支較少的局部解，在約束不滿(mǎn)足時(shí)，可以裁剪去較多的搜索分支，從而提高搜索效率。第20頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月一般圖搜索回溯搜索：只保留從初始態(tài)到當(dāng)前態(tài)的一條路徑圖搜索：保留所有搜索過(guò)的路徑實(shí)際上，圖搜索測(cè)量是實(shí)現(xiàn)從一個(gè)隱含圖中，生成一部分確實(shí)含有一個(gè)目標(biāo)節(jié)點(diǎn)的顯示表示的子圖搜索過(guò)程。第21頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月啟發(fā)式搜索算法利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，減低問(wèn)題復(fù)雜度的目的，希望引入啟發(fā)知識(shí)，在保證找到最優(yōu)解的情況下，盡可能減少搜索范圍，提高搜索效率。強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解第22頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月小結(jié)

回溯方法的步驟如下：

1)定義一個(gè)解空間，它包含問(wèn)題的解。

2)用適于搜索的方式組織該空間。

3)用深度優(yōu)先法搜索該空間，利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。

回溯算法的一個(gè)有趣的特性是在搜索執(zhí)行的同時(shí)產(chǎn)生解空間。在搜索期間的任何時(shí)刻，僅保留從開(kāi)始節(jié)點(diǎn)到當(dāng)前E-節(jié)點(diǎn)的路徑。因此，回溯算法的空間需求為O（從開(kāi)始節(jié)點(diǎn)起最長(zhǎng)路徑的長(zhǎng)度）。這個(gè)特性非常重要，因?yàn)榻饪臻g的大小通常是最長(zhǎng)路徑長(zhǎng)度的指數(shù)或階乘。所以如果要存儲(chǔ)全部解空間的話(huà)，再多的空間也不夠用第23頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月經(jīng)典問(wèn)題[迷宮老鼠][0/1背包問(wèn)題][旅行商問(wèn)題]第24頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月練習(xí)1.找出所有從m個(gè)元素中選取n(n<=m)元素的組合。2.設(shè)有A,B,C,D,E5人從事j1,j2,j3,j4,j55項(xiàng)工作每人只能從事一項(xiàng),它們的效益表如下。求最佳安排,使效益最高.第25頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月3.N個(gè)數(shù)中