算法-搜索與回溯對(duì)于某個(gè)問題如果沒有

搜索與對(duì)于某個(gè)問題，如果沒有高效的算法，或者用高效即通過枚舉每一種可行的方案來找到題目的答案。 只要當(dāng)前枚舉到的狀態(tài)可行度 就繼續(xù)枚舉下去。當(dāng)找到一 方案或者無法繼續(xù)枚舉下去時(shí) 就退回到上一狀態(tài)。退回到 一狀態(tài)的過程叫做回溯給定給定n（n≤10），求1,2,3,…,n的全排列數(shù)什么是全排列如果一個(gè)數(shù)列含包含這n個(gè)數(shù)，并且這n個(gè)都僅出現(xiàn)一次，符合該條件的所有數(shù)列叫做這n個(gè)數(shù)的全排列。如1,2,3三個(gè)元素的全排列為1,2,31,3,22,3,13,1,2可能有的同學(xué)已經(jīng)注意到這個(gè)問題的答案就是如果要輸出所有方案呢

一個(gè)方我們可以用一個(gè)布爾數(shù)組used示每個(gè)數(shù)字是否用過，用過為e未用過為false。用ans[i]記錄第i個(gè)位置的數(shù)是多少#include#includeusingnamespaceintintintint{return}voiddfs(int{int

if{for(i=1;i<=n;i++)printf("%d",}for{if{ //標(biāo) //回}}}深深度優(yōu)先搜索的一般框架void{if已找到一種方then枚舉每種選if選擇可then}TYVJM發(fā)現(xiàn)身高接近的人似乎更合得來。M7舉辦的派對(duì)共有()個(gè)人參加，M需要把他們安排在圓桌上。M的安排原則是，圓桌上任意兩個(gè)相鄰人的身高之差不能超過。請(qǐng)告訴M7他共有多少種安排方法。輸出符合要求的安排總12 23 312是同一種安排方把n個(gè)人安排在圓桌上，其實(shí)就是n個(gè)數(shù)的我們可以與上一題一樣求出每個(gè)排列，再檢驗(yàn)這個(gè)方是否符合條因?yàn)?23 231 312是同一方案，所以我們的方案數(shù)要除有沒有更好的做法我們發(fā)現(xiàn)，當(dāng)我們確定下第一個(gè)位置的人與第二個(gè)位置的人時(shí)，他們的身高可能已經(jīng)不符合要求了，但我們?nèi)匀凰阉髁讼氯?。我們可以一邊搜索一邊判斷。依次確定每個(gè)位置上的人，檢驗(yàn)一下該位置的人與前一位置的人是否符合要求當(dāng)所有人都已確定，再檢驗(yàn)n位置與1位置的人是否符要我們可以把第一個(gè)人固定在第一個(gè)位置再進(jìn)行搜索，這樣最后的答案就不用再除以nprogramcan:array[0..10]ofboolean;a,ans:array[0..10]oflongint;procedureifi>nifabs(ans[n]-theninc(s);

forj:=1tondoifcan[j]and(abs(a[j]-ans[i-1])<=k)fori:=1tondoread(a[i]);經(jīng)典問N皇后問在n×n（n≤）的國(guó)際象棋棋盤上，放置n個(gè)皇后，使任何一個(gè)皇后都不能吃掉另一個(gè)，需滿足的條件是：同一行、同一列、同一對(duì)角線上只能有一個(gè)皇后。43214321我們可以依次確定每一行皇的位

若無法放下皇后則回到上一行即回

當(dāng)n行的皇后都已確定后，我就找到了一種方放放用a數(shù)組標(biāo)記某列能否用b數(shù)組標(biāo)記左下到右上的對(duì)角線能否用c數(shù)組標(biāo)記右programbahuanghou;a,b,c:array[-100..100]f:array[0..100]oflongint;proceduredfs(i:longint);

c[i-ifi>nforj:=1tonifa[j]andb[i+j]andc[i-

石石子合你有n堆石頭質(zhì)量分別為W1，W2，……，Wn(W≤100000）?，F(xiàn)需要你將石頭合并為兩部分，使兩部分的質(zhì)量之和最接近輸入：第一行為整數(shù)n（1≤n≤20），表示有n堆石子。第二行n個(gè)數(shù)，為每堆石子的質(zhì)量輸出：一行。只需要輸出合并后兩部分的質(zhì)量之和的差樣例輸入5581327樣例輸出3我們可以知道這我們可以知道這n堆石子的質(zhì)量和sum可以用搜索枚舉哪些石子放在第一部分，得到第一部分的質(zhì)量可以用搜索枚舉哪些石子放在第一部分，得到第一部分的質(zhì)量a，求出所有方案中（（a）a）中最小的即為答案。如果第一部分石子質(zhì)量之和已超過總質(zhì)量的一半，繼續(xù)向該如果第一部分石子質(zhì)量之和已超過總質(zhì)量的一半，繼續(xù)向該部分中加入石子，兩部分質(zhì)量差的絕對(duì)值必然增大，沒有繼續(xù)搜索的必要。programshizihebw:array[0..20]offunctionmin(a,b:longint):longint;ifa>bthenexit(b)elseprocedureif(tot*2>=sum)or(k>n)thenans:=min(ans,abs(sum-tot-

fori:=1ton輸入只有一個(gè)整數(shù)n，表示待拆分的自然數(shù)n。1+2與2+1時(shí)間限樣例輸7樣例輸

輸入7，則7拆分的結(jié)果一共有14種情況，所以輸出我們可以枚舉一個(gè)數(shù)，用n減去這個(gè)數(shù)，再枚舉一個(gè)數(shù)，再減去這個(gè)數(shù)，直至減到0，我們就找到了一種方案。但是這樣做會(huì)有重復(fù)，即對(duì)于3我們會(huì)先減1再減2，也會(huì)先減2再減1，該如何避免重復(fù)？我們可以在搜索的時(shí)候可以記錄一個(gè)變量last，表示上次減掉的是哪個(gè)數(shù)，我們只允許減小于等于last的數(shù)，這樣可以避免重復(fù)。programP1171;procedureiftot=0thenfori:=lastdownto1

s:=s-//因?yàn)槲覀儼裯=n了一種方案，所以方案數(shù)要減iftot-i>=0thendfs(i,tot-有有一個(gè)未填滿的數(shù)獨(dú)，求這個(gè)數(shù)獨(dú)填滿后能獲得的最大總分分?jǐn)?shù)計(jì)算方法總分?jǐn)?shù)為每個(gè)方格上的分值和完成這個(gè)數(shù)獨(dú)時(shí)填在相應(yīng)格上的數(shù)字的積的總NOIP2009靶形數(shù)時(shí)間限樣例輸70090000100005900002000800502000000000644002092010608008050401樣例輸一個(gè)最簡(jiǎn)單的想法我們可以從左上角到右下角枚舉每一個(gè)未填上的格子，再枚舉它可以放哪些數(shù)字，將它填上后繼續(xù)搜索。當(dāng)所有格子都填上后，計(jì)算一下總分，如果總分大于當(dāng)前最優(yōu)值就更新最優(yōu)值嚴(yán)重超時(shí)我們還可以對(duì)上面的想法進(jìn)行改進(jìn)：我們可以先計(jì)算出每個(gè)格子的選擇數(shù)先確定可選擇數(shù)小的格子從而避免搜索到過多無法得到可行方案的狀這樣還好，，但是依舊超時(shí)如果要使程序能通過任何數(shù)據(jù)，可以采用位運(yùn)算加速搜索和cinglnks，但這兩種方法在聯(lián)賽范圍內(nèi)基本不會(huì)出現(xiàn)，我們不進(jìn)行深入討論。另外還用一種方法可以得到10分：根據(jù)當(dāng)前狀態(tài)確定每個(gè)格子的選擇數(shù)programsudoku;fenshu:array[1..9,1..9]ofmap:array[0..9,0..9]oflongint;hang,lie,ge:array[1..9,1..9]ofboolean;x,y:array[0..81]oflongint;c:array[0..81]ofprocedurecalc;//計(jì)算總fori:=1to9forj:=1to9ifs>ansthenans:=s;procedureifk>tthenfori:=1totifc[i]forj:=1to9ifhang[x[i],j]andlie[y[i],j]andge[z[x[i],y[i]],j]thenifw>=minthenbreak;ifw<minend;//找出當(dāng)前選擇最少fori:=1to9do//枚舉填哪個(gè)ifhang[xx,i]andlie[yy,i]andge[z[xx,yy],i]thenc[p]:=true;//回fori:=1to9forj:=1to9ifmap[i,j]=0

給定整數(shù)給定整數(shù)和三個(gè)字符串s1,2,3，這三個(gè)字符由種大寫字母組成，相同的大寫字母代表相同的數(shù)字。這三個(gè)字符串表示三個(gè)進(jìn)制的數(shù)字a,b,c，且滿足ab=c，求各個(gè)大寫字母分別代表什么數(shù)字。51034NOIP2004考慮到進(jìn)位的問題，我們很容易想到從最低位開始搜索當(dāng)搜索到第i位時(shí)，會(huì)有以下幾種情況第i位3個(gè)數(shù)都已確第i位3第i位3第i位3個(gè)數(shù)都未確只需驗(yàn)證是否合法，合法則繼續(xù)搜

繼續(xù)搜索枚舉一個(gè)未知數(shù)，同2確定另一個(gè)未知數(shù)繼續(xù)搜枚舉兩個(gè)未知數(shù)，同2確定另一個(gè)未知數(shù)繼續(xù)搜通過上述處理我們可以通過大部分的數(shù)據(jù)，但是還是不能拿到滿分，最慢的一個(gè)數(shù)據(jù)要運(yùn)行分鐘左右。在搜索過程中，有些位還沒有搜到，但可能這些位上的3個(gè)數(shù)字都已確定，我們就可以先判斷這些位是否合法，這樣可以將時(shí)間大大縮短，所有數(shù)據(jù)均可在1內(nèi)出解廣度優(yōu)先搜廣度優(yōu)先搜索廣度優(yōu)先搜用隊(duì)列保存待擴(kuò)展的節(jié)點(diǎn)，從隊(duì)首隊(duì)取出節(jié)點(diǎn)，擴(kuò)展出的新節(jié)點(diǎn)放入隊(duì)尾，直到找到目標(biāo)節(jié)廣度優(yōu)先搜索的代碼框{{取隊(duì)首節(jié)點(diǎn)擴(kuò)展，并將擴(kuò)展出的節(jié)點(diǎn)放入隊(duì)尾必要時(shí)要記住每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)}}合理編碼，減小存儲(chǔ)代需要考慮的問一個(gè)boolean標(biāo)志數(shù)組flag判重用的標(biāo)志數(shù)組只需要362,880Hash時(shí)時(shí)間與空間的權(quán)1.從某個(gè)頂點(diǎn)出發(fā)開始訪問，被訪問的頂作相應(yīng)的標(biāo)記，并輸出訪問頂點(diǎn)號(hào)作相應(yīng)的標(biāo)記；3.再依次根2中所有被訪問的鄰接點(diǎn)，訪層，搜索量就會(huì)非常龐大，往往就POJ1077八數(shù)碼問八數(shù)碼問題是人工智能中的經(jīng)典問POJ1077八數(shù)碼問題：經(jīng)典搜索問3*308共0表01245788238231465712345678 21762247766例題：移字母（NKOJ目標(biāo)狀態(tài)為(b)1搜索過122345645678 ==(51)針對(duì)字符串的一些hash算法，比如ELFHash和雙向廣度優(yōu)先搜有些問題按照廣度優(yōu)先搜索法則擴(kuò)展點(diǎn)的規(guī)則，既適合順序，也適合逆序，于是我們考慮在尋找目標(biāo)結(jié)點(diǎn)或路徑的搜索過程中，初始結(jié)點(diǎn)向目標(biāo)結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)向初始結(jié)點(diǎn)同時(shí)進(jìn)行擴(kuò)展，直至在兩個(gè)擴(kuò)展方向上出現(xiàn)同一個(gè)子結(jié)點(diǎn)，搜索結(jié)束，這就是雙向搜索過程。如果確實(shí)存在一條從初始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最初始結(jié)點(diǎn)相交點(diǎn)→目標(biāo)結(jié)點(diǎn)所形成的一條路徑即是所求最佳正向擴(kuò)逆向擴(kuò)雙向搜索結(jié)點(diǎn)擴(kuò)展順答樹并不是棵完全樹在擴(kuò)展完一層后，下雙向搜索的數(shù)據(jù)結(jié)建立兩個(gè)隊(duì)列，OPEN[1]，CLOSED[1]，OPEN[2]，雙向廣度優(yōu)先搜索算法//DOUBFS初始化，初始結(jié)點(diǎn)，和目標(biāo)結(jié)點(diǎn)分別進(jìn)入OPEN[1]和OPEN[2]表head[1]=1;tail[1]=1;head[2]=1;if(tail[1]-head[1]<=tail[2]-head[2])t=1;elset=2；//優(yōu)先擴(kuò)展待討論節(jié)點(diǎn)比較少那個(gè)方for(i=head[t];i<=tail[t];i++)expand(t)；//討論隊(duì)列中的結(jié)//函數(shù)expand(t)void