八、回溯法

　　回溯跟遞歸都是程序員考試?yán)锍３霈F(xiàn)的問題,大家必須掌握!

　　回溯法的有關(guān)概念:

　　1) 解答樹:葉子結(jié)點(diǎn)可能是解,對結(jié)點(diǎn)進(jìn)行后序遍歷.
　　2) 搜索與回溯
　　五個數(shù)中任選三個的解答樹(解肯定有三層,至葉子結(jié)點(diǎn)): 
　　　　　　　　　　　　　　　ROOT 虛根
　　　　　　　　/　　　　　　/　　　 |　　\　　\
　　　　　　　 1　　　　　 2　　　　 3　　4　　 5
　　　　/ 　|　 |　 \　　/ | \ 　　 /\　　|
　　　 2　　3　 4　　5　3　4　5　　4　5　 5
　　　/|\ 　/\　|　 /\　|　|
　　 3 4 5 4　5 5　4　5 5　5

　　回溯算法實(shí)現(xiàn)中的技巧:棧
　　要搞清回溯算法，先舉一個(中序遍歷二叉樹的非遞歸算法)來說明棧在非遞歸中所起的作用。
　　　　　 A 過程：push()->push()->push()->push()棧內(nèi)結(jié)果:ABDE(E為葉子,結(jié)束進(jìn)棧)
　　　　　/ \　　　pop()　　　ABD(E無右孩子,出棧)
　　　　 B　 C　　 pop()　　　AB(D無右孩子,出棧) 
　　　　/\　　　　 pop()　　　A(B有右孩子,右孩子進(jìn)棧)
　　　 D　F 　　　　.　　　　　 .
　　　/　/\　　　　 . 　　　　　.
　　 E　G　H　　　　. 　　　　　.
　　/　　　　　　　 .　　　　　 .
　 I　　　　　　　 最后結(jié)果： EDBGFIHAC
　　簡單算法:
　　　　…
　　　if(r!=NULL) //樹不空
　　　{ while(r!=NULL) 
　　　　{ push(s,r);
　　　　　r=r->lch;　　　//一直向左孩子前進(jìn)
　　　　}
　　　　while(!empty(s)) // 棧非空,出棧
　　　　{ p=pop(s);
　　　　　printf(p->data);
　　　　　p=p->rch;　　　//向右孩子前進(jìn)
　　　　　while(p!=NULL)
　　　　　{ push(s,p);
　　　　　　p=p->lch; //右孩子進(jìn)棧
　　　　　}
　　　　} 
　　　}　//這就是傳說中的回溯,嘻嘻……沒嚇著你吧

　　5選3問題算法:

　　思想: 進(jìn)棧:搜索
　　出棧:回溯
　　邊建樹(進(jìn)棧)邊遍歷(出棧)
　　基本流程: 
　　太復(fù)雜了,再說我不太喜歡用WORD畫圖（有損形象），以后再整理!

　　程序: n=5;r=3
　　　　　……
　　　　　init(s)　　//初始化棧
　　　　　push(s,1)　//根進(jìn)棧
　　　　　while(s.top<r-1)&&(s.data[s.top]!=n) //有孩子
　　　　　　push(s,s.data[s.top]+1); //孩子入棧
　　　　　while(!empty(s))
　　　　　{ if(s.top=r-1)
　　　　　　判斷該"解"是否為解.
　　　　　　x=pop(s); //保留x,判斷是否為最大值n,如果是n,則出棧
　　　　　　while(x==n)
　　　　　　x=pop(s);
　　　　　　push(s,x+1);
　　　　　　while(s.top<r-1)&&(s.data[s.top]!=n)
　　　　　　push(s,s.data[s.top]+1);
　　　　　}

　　背包問題: TW=20 , w[5]={6,10,7,5,8} 

　　解的條件:1) 該解答樹的葉子結(jié)點(diǎn)
　　2) 重量最大
　　解答樹如下：　　　ROOT
　　　　　　　/ | | | \
　　　　　　　　　 6 10　　 7　　　5　 8
　　　　　　　　/ | | \　 / | \　 / \　| 
　　　　　　　 10 7 5　8 7　5　8 5　 8 8
　　　　　　　　　| |　　　　　　| 
　　　　　　　　　5 8　　　　　　8
　　程序:
　　temp_w 表示棧中重量和
　　…
　　init(s); //初始化棧
　　i=0;
　　While(w[i]>TW)
　　　i++;
　　　If(i==n) Return -1; //無解
　　　Else {
　　　　Push(s,i);
　　　　Temp_w=w[i];
　　　　i++;
　　　　while(i<n)&&(temp_w+w[i]<=TW)
　　　　　{ push(s,i);
　　　　　　temp_w+=w[i];
　　　　　　i++;
　　　　}
　　　　max_w=0;
　　　　while(!empty(s))
　　　　　{ if(max_w<temp_w)
　　　　　　　max_w=temp_w;
　　　　　　　x=pop(s);
　　　　　　　temp_w-=w[x];
　　　　　　　x++;
　　　　　　　while(x<n)&&(temp_w+w[x]>TW)
　　　　　　　　x++;
　　　　　　　while(x<n)
　　　　　　　{ push(s,x);
　　　　　　　　temp_w=temp_w+w[x];
　　　　　　　　x++;
　　　　　　　　while(x<n)&&(temp_w+w[x]>TW)
　　　　　　　　x++;
　　　　　　　}
　　　　　}
　　請大家思考:四色地圖問題,比如給中國地圖涂色,有四種顏色,每個省選一種顏色,相鄰的省不能取同樣的顏色.不許偷懶，不能選人口不多于xxxxＷ的"大國"哦!如果真的有一天臺灣獨(dú)立了，下場就是這樣了，一種顏色就打發(fā)了，不過臺灣的程序員們賺到了，省事！呵呵。

    貪婪法:

　　不求最優(yōu)解,速度快(以精確度換速度)

　　例:哈夫曼樹,最小生成樹

　　裝箱問題:

　　有n個物品,重量分別為w[n]，要把這n個物品裝入載重為TW的集裝箱內(nèi),需要幾個集裝箱?
　　思想1:對n個物品排序
　　拿出第1個集裝箱，從大到小判斷能不能放。
　　2 …
　　3 …
　　. …
　　. …
　　思想2: 對n個物品排序
　　用物品的重量去判斷是否需要一只新箱子，如果物品重量小于本箱子所剩的載重量,則裝進(jìn)去,反之則取一只新箱子。

　　程序:
　　count=1;qw[0]=TW;
　　for(i=0;i<n;i++)
　　{
　　　k=0;
　　　while(k<count)&&(w[i]>qw[k])
　　　　k++;
　　　　if(w[i]<=qw[k])
　　　　　qw[k]=qw[k]-w[i];
　　　　　code[i]=k; //第i個物品放在第k個箱子內(nèi)
　　　　else
　　　　　{count++; //取一個新箱子
　　　　　　qw[count-1]=TW-w[i];
　　　　　　code[i]=count-1;
　　　　}
　　}

　　用貪婪法解背包問題:
　　n個物品，重量:w[n] 價值v[i]
　　背包限重TW，設(shè)計(jì)一個取法使得總價值最大.
　　方法:
　　　0　　1　　2　　3　…　n-1
　　　w₀ w₁ 　w₂ 　w₃…　w_n-1
　　　v₀ v₁ 　v₂ 　v₃…　v_n-1 
　　　v₀/w₀ …　　　　　v(_n-1)/w(_n-1) 求出各個物品的"性價比"

　　先按性價比從高到低進(jìn)行排序

　　已知:w[n],v[n],TW
　　程序:
　　…
　　for(I=1;I<n;I++)
　　　d[i]=v[i]/w[i]; //求性價比
　　　for(I=0;I<n;I++)
　　　{ max=-1;
　　　　for(j=0;j<n;j++)
　　　　{ if(d[j]>max)
　　　　　{ max=d[j];x=j; }
　　　　}　
　　　　e[i]=x;
　　　　d[x]=0;
　　　}
　　　temp_w=0;temp_v=0;
　　for(i=0;i<n;i++)
　　　{ if(temp_w+w[e[i]]<=TW)
　　　　　temp_v=temp_v+v[e[v]];
　　}

    分治法:

　　思想:把規(guī)模為n的問題進(jìn)行分解,分解成幾個小規(guī)模的問題.然后在得到小規(guī)模問題的解的基礎(chǔ)上,通過某種方法組合成該問題的解.

　　例:數(shù)軸上有n個點(diǎn)x[n],求距離最小的兩個點(diǎn).
　　分:任取一點(diǎn),可以把x[i]這n個點(diǎn)分成兩個部分
　　小的部分 分點(diǎn) 大的部分
　　　　|_._.__.__.____._|__._._.__._.__._______._.__._._.__.___._____._|
　　治:解=min{小的部分的距離最小值;
　　　大的部分的距離最小值;
　　　大的部分最小點(diǎn)和小的部分最大點(diǎn)這兩點(diǎn)之差;}

      想必大家看到這里也累了，那就留一份模擬題給大家做做吧，看一下自己的實(shí)力。答案附在后面那。

上一頁  [1] [2] [3] [4] [5] [6] [7] [8] [9] 下一頁