中國數(shù)學(xué)建模-編程交流-搜索算法基礎(chǔ)

1、中國數(shù)學(xué)建模 -編程交流 - 搜索算法基礎(chǔ)搜索算法基礎(chǔ)搜索算法是利用計(jì)算機(jī)的高性能來有目的的窮舉一個(gè)問題的部分或所有的可能情況， 從 而求出問題的解的一種方法。 搜索過程實(shí)際上是 根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并 尋找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)的過程。所有的搜索算法從其最終的算法實(shí)現(xiàn)上來看，都可以劃分成兩個(gè)部分一一控制結(jié)構(gòu)和產(chǎn)生系統(tǒng) ，而所有的算法的優(yōu)化和改進(jìn)主要都是通過修改其控制結(jié)構(gòu)來完成的。 現(xiàn)在主要對(duì) 其控制結(jié)構(gòu)進(jìn)行討論，因此對(duì)其產(chǎn)生系統(tǒng)作如下約定：Function ExpendNode（Situation:Tsituation;ExpendWayNInteger）:TSituation;

2、表示對(duì)給出的節(jié)點(diǎn)狀態(tài) Sitution 采用第 ExpendWayNo 種擴(kuò)展規(guī)則進(jìn)行擴(kuò)展， 并且返回 擴(kuò)展后的狀態(tài)。（本文所采用的算法描述語言為類Pascal。）第一部分 基本搜索算法一、回溯算法回溯算法是所有搜索算法中最為基本的一種算法，其采用了一種“走不通就掉頭 ”思想作為其控制結(jié)構(gòu)， 其相當(dāng)于采用了 先根遍歷的方法來構(gòu)造解答樹 ，可用于找解或所有解以及 最優(yōu)解。具體的算法描述如下： 非遞歸算法 vType Node（節(jié)點(diǎn)類型）=RecordSitutation:TSituation （當(dāng)前節(jié)點(diǎn)狀態(tài)） ;Way-NInteger （已使用過的擴(kuò)展規(guī)則的數(shù)目）；Endv VarList（

3、回溯表 ）:Array1.Max（ 最大深度 ） of Node；pos（當(dāng)前擴(kuò)展節(jié)點(diǎn)編號(hào)）:1 nteger;v Init List v -0;posv -1;List1.Situation v -初始狀態(tài) ;v Main Program While （pos 0（有路可走）and （未達(dá)到目標(biāo)）doBeginIf pos=Max then （數(shù)據(jù)溢出 ,跳出主程序 ）;Listpos.Way-N=Listpos.Way-No+1;If （Listpos.Way-NO v =TotalExpendMethod） then （ 如果還有沒用過的擴(kuò) 展規(guī)則 ）BeginIf （可以使用當(dāng)前擴(kuò)展規(guī)

4、則 ） thenBegin（用第 way 條規(guī)則擴(kuò)展當(dāng)前節(jié)點(diǎn) ）Listpos+1.Situation:=ExpendNode（Listpos.Situation,Listpos.Way-NO）;Listpos+1.Way-N=0;pos:=pos+1;End-If;End-IfElse Beginpos:=pos-1;End-ElseEnd-While;遞歸算法 Procedure BackTrack（Situation:TSituation;deepth:Integer）;Var I :Integer;BeginIf deepth Max then （空間達(dá)到極限，跳出本過程）;If Si

5、tuation=Target then （找到目標(biāo) ）;For I:=1 to TotalExpendMethod doBegin BackTrack（ExpendNode（Situation，I），deepth+1）;End-For;End;范例：一個(gè) M*M 的棋盤上某一點(diǎn)上有一個(gè)馬， 要求尋找一條從這一點(diǎn) 出發(fā)不重復(fù)的跳完棋盤上所有的點(diǎn)的路線。評(píng)價(jià)：回溯算法對(duì)空間的消耗較少， 當(dāng)其與分枝定界法一起使用時(shí)， 對(duì) 于所求解在解答樹中層次較深的問題有較好的效果。 但應(yīng)避免在后繼節(jié)點(diǎn)可能與前繼節(jié)點(diǎn)相 同的問題中使用，以免產(chǎn)生循環(huán)。二、深度搜索與廣度搜索 深度搜索與廣度搜索的控制結(jié)構(gòu)和產(chǎn)生系統(tǒng)很相

6、似，唯一的區(qū)別在于對(duì)擴(kuò)展節(jié)點(diǎn)選取 上。由于其保留了所有的前繼節(jié)點(diǎn)， 所以在產(chǎn)生后繼節(jié)點(diǎn)時(shí)可以去掉一部分重復(fù)的節(jié)點(diǎn)， 從 而提高了搜索效率。 這兩種算法每次都擴(kuò)展一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)， 而不同的是， 深度搜索 下一次擴(kuò)展的是本次擴(kuò)展出來的子節(jié)點(diǎn)中的一個(gè)， 而廣度搜索擴(kuò)展的則是本次擴(kuò)展的節(jié)點(diǎn)的 兄弟節(jié)點(diǎn)。在具體實(shí)現(xiàn)上為了提高效率，所以采用了不同的數(shù)據(jù)結(jié)構(gòu).廣度搜索 v TypeNode（節(jié)點(diǎn)類型）=RecordSitutation:TSituation （當(dāng)前節(jié)點(diǎn)狀態(tài)） ;Level:Integer（ 當(dāng)前節(jié)點(diǎn)深度 ）;Last :lnteger（父節(jié)點(diǎn)）;Endv Var List（節(jié)點(diǎn)表）:A

7、rray1.Max（最多節(jié)點(diǎn)數(shù)）of Node（節(jié)點(diǎn)類型）;open（總節(jié)點(diǎn)數(shù)）:1 nteger;close（待擴(kuò)展節(jié)點(diǎn)編號(hào)）:1 nteger;New-S:TSituation;（ 新節(jié)點(diǎn) ）v InitListv -0;openv -1;closev -0;List1.Situation v - 初始狀態(tài) ;List1.Level:=1;List1.Last:=0;v Main Program While （close v open（還有未擴(kuò)展節(jié)點(diǎn)）and（openv Max（ 空間未用完 ） and（未找到目標(biāo)節(jié)點(diǎn) ） doBeginclose:=close+1;For I:=1 to

8、 TotalExpendMethod do （擴(kuò)展一層子節(jié)點(diǎn)）BeginNew-S:=ExpendNode（Listclose.Situation,I）;If Not （New-S in List） then（擴(kuò)展出的節(jié)點(diǎn)從未出現(xiàn)過）Beginopen:=open+1;Listopen.Situation:=New-S;Listopen.Level:=Listclose.Level+1;Listopen.Last:=close;End-IfEnd-For;End-While;深度搜索 v Var Open:Array1.Max of Node;（ 待擴(kuò)展節(jié)點(diǎn)表 ）Close:Array1.Ma

9、x of Node;（ 已擴(kuò)展節(jié)點(diǎn)表 ）openL,closeL:Integer;（ 表的長度 ）New-S:Tsituation;（ 新狀態(tài) ）v Init Openv -0; Close v -0;OpenL v -1;CloseL v -0;Open1.Situation v - 初始狀態(tài) ;Open1.Level v -1;Open1.Last v -0;v Main Program While （openL 0） and （closeL v Max） and （openL v Max） doBegincloseL:=closeL+1;ClosecloseL:=OpenopenL;op

10、enL:=openL-1;For I:=1 to TotalExpendMethod do （擴(kuò)展一層子節(jié)點(diǎn)）BeginNew-S:=ExpendNode（ClosecloseL.Situation,I）;If Not （New-S in List） then（擴(kuò)展出的節(jié)點(diǎn)從未出現(xiàn)過）BeginopenL:=openL+1;OpenopenL.Situation:=New-S;OpenopenL.Level:=ClosecloseL.Level+1;OpenopenL.Last:=closeL;End-IfEnd-For;End;范例：迷宮問題，求解最短路徑和可通路徑。評(píng)價(jià)： 廣度搜索是求解最

11、優(yōu)解的一種較好的方法， 在后面將會(huì)對(duì)其進(jìn)行 進(jìn)一步的優(yōu)化。 而深度搜索多用于只要求解， 并且解答樹中的重復(fù)節(jié)點(diǎn)較多并且重復(fù)較難判 斷時(shí)使用，但往往可以用 A* 或回溯算法代替。第二部分 搜索算法的優(yōu)化一、雙向廣度搜索 廣度搜索雖然可以得到最優(yōu)解，但是其空間消耗增長太快。但如果從正反兩個(gè) 方向進(jìn)行廣度搜索，理想情況下可以減少二分之一的搜索量，從而提高搜索速度。范例：有 N 個(gè)黑白棋子排成一派，中間任意兩個(gè)位置有兩個(gè)連續(xù)的空格。每次空格可 以與序列中的某兩個(gè)棋子交換位置， 且兩子的次序不變。 要求出入長度為 length 的一個(gè)初始 狀態(tài)和一個(gè)目標(biāo)狀態(tài)，求出最少的轉(zhuǎn)化步數(shù)。問題分析：該題要求求出最

12、少的轉(zhuǎn)化步數(shù)，但如果直接使用廣度搜索， 很容易產(chǎn)生數(shù)據(jù)溢出。 但如果從初始狀態(tài)和目標(biāo)狀態(tài)兩個(gè)方向同時(shí)進(jìn)行擴(kuò)展， 如果兩棵解答 樹在某個(gè)節(jié)點(diǎn)第一次發(fā)生重合，則該節(jié)點(diǎn)所連接的兩條路徑所拼成的路徑就是最優(yōu)解。plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained);2004-5-27 21:29:01b對(duì)廣度搜索算法的改進(jìn)：1、添加一張節(jié)點(diǎn)表，作為反向擴(kuò)展表。2、在 while 循環(huán)體中在正向擴(kuò)展代碼后加入反向擴(kuò)展代碼，其擴(kuò)展過 程不能與正向過程共享一個(gè) for 循環(huán)。3、在正向擴(kuò)展出一個(gè)節(jié)點(diǎn)后，需在反

13、向表中查找是否有重合節(jié)點(diǎn)。反 向擴(kuò)展時(shí)與之相同。對(duì)雙向廣度搜索算法的改進(jìn)：略微修改一下控制結(jié)構(gòu)， 每次 while 循環(huán)時(shí)只擴(kuò)展正反兩個(gè)方向中節(jié)點(diǎn) 數(shù)目較少的一個(gè)， 可以使兩邊的發(fā)展速度保持一定的平衡， 從而減少總擴(kuò)展節(jié)點(diǎn)的個(gè)數(shù)， 加 快搜索速度。二、分支定界分支定界實(shí)際上是 A* 算法的一種雛形，其對(duì)于每個(gè)擴(kuò)展出來的節(jié)點(diǎn)給 出一個(gè)預(yù)期值，如果這個(gè)預(yù)期值不如當(dāng)前已經(jīng)搜索出來的結(jié)果好的話，則將這個(gè)節(jié)點(diǎn)（包括其子節(jié)點(diǎn) ）從解答樹中刪去，從而達(dá)到加快搜索速度的目的。范例：在一個(gè)商店中購物， 設(shè)第I種商品的價(jià)格為 Ci。但商店提供一種折扣，即給出一組商品的組合，如果一次性購買了這一組商品，則可以享受較

14、優(yōu)惠的價(jià)格。 現(xiàn)在給出一張購買清單和商店所提供的折扣清單，要求利用這些折扣，使所付款最少。問題分析： 顯然， 折扣使用的順序與最終結(jié)果無關(guān)， 所以可以先將所有 的折扣按折扣率從大到小排序， 然后采用回溯法的控制結(jié)構(gòu)， 對(duì)每個(gè)折扣從其最大可能使用 次數(shù)向零遞減搜索，設(shè) A 為以打完折扣后優(yōu)惠的價(jià)格， C 為當(dāng)前未打折扣的商品零售價(jià)之 和，則其預(yù)期值為 A+a*C ，其中 a 為下一個(gè)折扣的折扣率。如當(dāng)前已是最后一個(gè)折扣，則 a=1。對(duì)回溯算法的改進(jìn)：1、添加一個(gè)全局變量 BestAnswer ，記錄當(dāng)前最優(yōu)解。2、 在每次生成一個(gè)節(jié)點(diǎn)時(shí)，計(jì)算其預(yù)期值，并與BestAnswer 比較。如 果不好，

15、則調(diào)用回溯過程。三、A* 算法A*算法中更一般的引入了一個(gè)估價(jià)函數(shù)f,其定義為f=g+h。其中g(shù)為到達(dá)當(dāng)前節(jié)點(diǎn)的耗費(fèi)， 而 h 表示對(duì)從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的耗費(fèi)的估計(jì)。 其必須滿足兩個(gè)條 件：h*。1、h 必須小于等于實(shí)際的從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)的最小耗費(fèi)2、 f 必須保持單調(diào)遞增。A* 算法的控制結(jié)構(gòu)與廣度搜索的十分類似，只是每次擴(kuò)展的都是當(dāng)前 待擴(kuò)展節(jié)點(diǎn)中 f 值最小的一個(gè)， 如果擴(kuò)展出來的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)重復(fù)， 則刪去這個(gè)節(jié)點(diǎn)。 如果與待擴(kuò)展節(jié)點(diǎn)重復(fù)， 如果這個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)值較小， 則用其代替原待擴(kuò)展節(jié)點(diǎn)， 具體 算法描述如下：范例：一個(gè) 3*3 的棋盤中有 1-8八個(gè)數(shù)字和一個(gè)空

16、格， 現(xiàn)給出一個(gè)初始 態(tài)和一個(gè)目標(biāo)態(tài)，要求利用這個(gè)空格，用最少的步數(shù)，使其到達(dá)目標(biāo)態(tài)。問題分析：預(yù)期值定義為h=|x-dx|+|y-dy| 。估價(jià)函數(shù)定義為 f=g+h 。v TypeNode（節(jié)點(diǎn)類型）=RecordSitutation:TSituation （當(dāng)前節(jié)點(diǎn)狀態(tài)） ;g:l nteger;（到達(dá)當(dāng)前狀態(tài)的耗費(fèi)）h:lnteger;（預(yù)計(jì)的耗費(fèi)）f:Real;（估價(jià)函數(shù)值）Last:lnteger;（父節(jié)點(diǎn)）Endv VarList（節(jié)點(diǎn)表）:Array1.Max（最多節(jié)點(diǎn)數(shù)）of Node（節(jié)點(diǎn)類型）;open（總節(jié)點(diǎn)數(shù)）:Integer;close（待擴(kuò)展節(jié)點(diǎn)編號(hào)）:1 nte

17、ger;New-S:Tsituation;（ 新節(jié)點(diǎn) ）v lnitListv -0; ope nv -1;closev -0;List1.Situation v - 初始狀態(tài) ;v Main Program While （close v open（還有未擴(kuò)展節(jié)點(diǎn)）and（openv Max（ 空間未用完 ） and（未找到目標(biāo)節(jié)點(diǎn) ） doBeginBeginclose:=close+1;For I:=close+1 to open do （ 尋找估價(jià)函數(shù)值最小的節(jié)點(diǎn) ）Beginif Listi.f v Listclose.f thenBegin交換 Listi 和 Listclose;E

18、nd-If;End-For;End;For I:=1 to TotalExpendMethod do （擴(kuò)展一層子節(jié)點(diǎn)）BeginNew-S:=ExpendNode（Listclose.Situation,I）If Not （New-S in List1.close） then（擴(kuò)展出的節(jié)點(diǎn)未與已擴(kuò)展的節(jié)點(diǎn)重復(fù) ）BeginIf Not （New-S in Listclose+1.open） then （擴(kuò)展出的節(jié)點(diǎn)未與待擴(kuò)展的節(jié)點(diǎn)重復(fù) ）Begin open:=open+1;Listopen.Situation:=New-S;Listopen.Last:=close;Listopen.g:=

19、Listclose.g+cost;Listopen.h:=GetH(Listopen.Situation);Listopen.f:=Listopen.h+Listopen.g;End-IfElse BeginIf Listclose.g+cost+GetH(New-S) v Listsame.f then( 擴(kuò)展出來的節(jié)點(diǎn)的估價(jià)函數(shù)值小于與其相同的節(jié)點(diǎn))BeginListsame.Situation:= New-S;Listsame.Last:=close;Listsame.g:=Listclose.g+cost;Listsame.h:=GetH(Listopen.Situation);Lis

20、tsame.f:=Listopen.h+Listopen.g;End-If;End-Else;End-IfEnd-For;End-While;對(duì) A* 算法的改進(jìn) -分階段 A* ：當(dāng) A* 算法出現(xiàn)數(shù)據(jù)溢出時(shí)，從待擴(kuò)展節(jié)點(diǎn)中取出若干個(gè)估價(jià)函數(shù)值較小的節(jié)點(diǎn)，然后放棄其余的待擴(kuò)展節(jié)點(diǎn)，從而可以使搜索進(jìn)一步的進(jìn)行下去。plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained);第三部分 搜索與動(dòng)態(tài)規(guī)劃的結(jié)合例 1.有一個(gè)棋子，其 1、6面 2、4面 3、5 面相對(duì)?，F(xiàn)給出一個(gè) M*N 的棋盤， 棋子起初

21、處于 （1,1）點(diǎn)，擺放狀態(tài)給定，現(xiàn)在要求用最少的步數(shù)從（1,1）點(diǎn)翻滾到 （M,N） 點(diǎn)，并且 1 面向上。分析：這道題目用簡單的搜索很容易發(fā)生超時(shí)，特別當(dāng)M 、N 較大時(shí)。所以可以考慮使用動(dòng)態(tài)規(guī)劃來解題。對(duì)于一個(gè)棋子，其總共只有 24 種狀態(tài)。在 （1,1） 點(diǎn)時(shí)， 其向右翻滾至（2,1）點(diǎn)，向上翻滾至（1,2）點(diǎn)。而任意（I, J）點(diǎn)的狀態(tài)是由（1-1 ,）和（I, J-1）點(diǎn)狀態(tài)推導(dǎo)出來的。所以如果規(guī)定棋子只能向上和向右翻滾，則可以用動(dòng)態(tài)規(guī)劃的方 法將到達(dá)（M, N ）點(diǎn)的所有可能的狀態(tài)推導(dǎo)出來。顯然，從（1，1）到達(dá)（N , M ）這些狀態(tài)的路徑時(shí)最優(yōu)的。如果這些狀態(tài)中有 1面向上的

22、，則已求出解。如果沒有，則可以從（M， N）點(diǎn)開始廣度搜索，以（M，N ）點(diǎn)的狀態(tài)組作為初始狀態(tài)，每擴(kuò)展一步時(shí)，檢查當(dāng)前所 得的狀態(tài)組是否有狀態(tài)與到達(dá)格子的狀態(tài)組中的狀態(tài)相同,如果有, 則由動(dòng)態(tài)規(guī)劃的最優(yōu)性和廣度搜索的最優(yōu)性可以保證已求出最優(yōu)解。例2給出一個(gè)正整數(shù) n，有基本元素a，要求通過最少次數(shù)的乘法，求出a5。分 析： 思 路一 ： 這 道 題從 題面 上 來看 非 常象 一道 動(dòng)態(tài) 規(guī) 劃題 ，a5=aAx1*aAx2。在保證aAx1和aAx2的最優(yōu)性之后，a5的最優(yōu)性應(yīng)該得到保證。但是仔細(xì) 分析后可以發(fā)現(xiàn)，aAx1與aAx2的乘法過程中可能有一部分的重復(fù)，所以在計(jì)算an時(shí)要減去其重復(fù)

23、部分。由于重復(fù)部分的計(jì)算較繁瑣，所以可以將其化為一組展開計(jì)算。描述如下：I:=n;（拆分 a5）splitn:=x1;（ 分解方案 ）Usedn:=True;（ 在乘法過程中出現(xiàn)的數(shù)字 ）Repeat（不斷分解數(shù)字）UsedI-splitI:=True;UsedsplitI:=True;Dec（I）;While （I 1） and （not Usedl） do dec（l）;Until I=1;For l:=n downto 1 do（ 計(jì)算總的乘法次數(shù) ）lf Usedl then count:=count+1;Result:=count;（ 返回乘法次數(shù) ）思路二：通過對(duì)思路一的輸出結(jié)果的

24、分析可以發(fā)現(xiàn)一個(gè)規(guī)律：aA19=aA1*aA18aA18=aA2*aA16aA16=aA8*aA8aA8=aA4*aA4aA4=aA2*aA2aA2=a*a對(duì)于一個(gè)n,先構(gòu)造一個(gè)最接近的2Ak，然后利用在構(gòu)造過程中產(chǎn)生的2A|,對(duì)n-2Ak進(jìn)行二進(jìn)制分解，可以得出解。對(duì)次數(shù)的計(jì)算的描述如下：count:=0;RepeatIf n mod 2 = 0 then count:=count+1Else count:=count+2;n:=n div 2;Until n=1;Result:=count;反思：觀察下列數(shù)據(jù)：aA15 aA23 aA27Cost:5 Cost:6 Cost:6aA2=aA

25、1*aA1 aA2=aA1*aA1 aA2=aA1*aA1aA3=aA1*aA2 aA3=aA1*aA2 aA3=aA1*aA2aA6=aA3*aA3 aA5=aA2*aA3 aA6=aA3*aA3 aA12=aA6*aA6 aA10=aA5*aA5 aA12=aA6*aA6 aA15=aA3*aA12 aA20=aA10*aA10 aA24=aA12*aA12 aA23=aA3*aA20 aA27=aA3*aA24這些數(shù)據(jù)都沒有采用思路二種的分解方法， 而都優(yōu)于思路二中所給出的 解。但是經(jīng)過實(shí)測， 思路一二的所有的解的情況相同，而卻得不出以上數(shù)據(jù)中的解。經(jīng)過對(duì) aA2- aA15的數(shù)據(jù)的完全

26、分析，發(fā)現(xiàn)對(duì)于一個(gè)aAn,存在多個(gè)分解方法都可以得出最優(yōu)解，而在思路一中只保留了一組分解方式。例如對(duì)于 aA6 只保留了 aA2*aA4 ，從而使 aA3*aA3 這 條路中斷, 以至采用思路一的算法時(shí)無法得出正確的耗費(fèi)值, 從而丟失了最優(yōu)解。 所以在計(jì) 算 aAn=aAx1*aAx2 的重復(fù)時(shí),要引入一個(gè)搜索過程。例如 :aA15=aA3*aA12 , aA12=aA6*aA6 , 而 aA6=aA3*aA3 。如果采用了 aA6=aA2*aA4 ,則必須多用一步。v TypeLink=ANode; （使用鏈表結(jié)構(gòu)紀(jì)錄所有的可能解）Node=Record split:Integer;next

27、 :Link;End;v Var Solution:Array1.1000 of Link;（對(duì)于 aAn 的所有可能解）Cost :Array1.1000 of Integer; （解的代價(jià)）max :Integer; （推算的上界）v Main Program Procedure GetSolution;Var i,j :Integer; min,c:Integer; count:Integer; temp,tail:Link;plan :Array1.500 of Integer; nUsed:Array1.1000 of Boolean;Procedure GetCost（From,C

28、ost:Integer）; （搜索計(jì)算最優(yōu)解）Var temp:Link;a,b :Boolean;i :Integer;BeginIf Cost c then Exit; （剪枝）If From=1 then （遞歸終結(jié)條件）BeginIf Costv c then c:=Cost;Exit;End;temp:=SolutionFrom;While temp v NIL do （搜索主體）a:=nUsedtempA.Split;If not a then inc(cost);n UsedtempSplit:=True;b:=nU sedFrom - tempA.Split;If not b

29、then inc(cost); nUsedFrom-tempA.Split:=True;i:=From-1;While (i 1) and (not nUsedi) do dec(i);GetCost(i,Cost);If not a then dec(cost);If not b then dec(cost); nUsedFrom-tempA.Split:=b; nUsedtempA.Split:=a;temp:=tempA.next;End;End;BeginFor i:=2 to Max do (動(dòng)態(tài)規(guī)劃計(jì)算所有解)Begincount:=0;min:=32767;For j:=1 to

30、 i div 2 do (將 I 分解為 I-J 和 J)Beginc:=32767;FillChar(nUsed,Sizeof(nUsed),0); nUsedj:=True;nUsedi-j:=True;If j=i-j then GetCost(i-j,1)Else GetCost(i-j,2);If c v min thenBegincount:=1;min:=c; plancount:=j;EndElse if c=min thenBegin inc(count); plancount:=j;End;End;new(solutioni); (構(gòu)造解答鏈表)solutio niF.split:=pla n1;solutio n.n ext:=NIL;Costi:=min;tail:=solutioni;For j:=2