算法之挖地雷問題

算法之挖地雷問題一、問題陳述在一條河上有若干個地雷坑，每個地雷坑中埋有一定數(shù)量的地雷，地雷坑的編號為1、2、3、…、N(N<=100),如下表所示(N=10)：雷號地坑12345678910地雷數(shù)量81421733261517196同時在每個地雷坑中都有一張說明書(除最后一個地雷坑以外)。說明書指出，在挖完此坑的地雷之后，還可以繼續(xù)挖哪些坑。挖地雷的規(guī)則為可以從任何一個地雷坑開始，到任何一個地雷坑結(jié)束。同時，在挖完某個地雷坑中的地雷之后，可以選擇它可繼續(xù)挖的地雷坑之一繼續(xù)挖，但只能選擇一種。例如：從1坑開始，可挖到8枚地雷，挖完之后繼續(xù)挖2號地雷坑，挖完之后，可挖到14枚。挖完2坑之后，還可以挖3號地雷坑，可挖到2枚。由于3號坑之后不存在鏈接，因此挖地雷結(jié)束。按照上面的方法，從1號地雷坑開始，到3號地雷坑結(jié)束，總共可挖到地雷數(shù)量為8+14+2=24枚。同時，我們看到在挖完1號地雷坑中的地雷之后，可以選擇4號地雷坑，在挖完4號地雷坑之后可以選擇5號坑繼續(xù)挖，在挖完5號坑之后可以選擇6號坑繼續(xù)挖，在挖完6號坑之后可以選擇8號坑繼續(xù)挖，在挖完8號坑之后可?繼續(xù)挖10號坑，在挖完10號坑之后，挖地雷結(jié)束。此時總共可挖地雷數(shù)量為8+17+33+26+17+6=107。問題為：當?shù)乩卓又械牡乩讛?shù)量以及后繼關系給出之后，找出一個挖地雷的方法，能挖到最多的地雷。二、 動態(tài)規(guī)劃基本思想動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解.用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的。如果我們能夠保存己解決的子問題的答案，而在需要時再找出己求得的答案，這樣就可以避免大量的重復計算，節(jié)省時間。我們可以用一個表來記錄所有己解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路。具體的動態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。三、 算法描述1、 用動態(tài)規(guī)劃求解：由后往前查找：若從第n個地雷坑開始挖，此時可能得到a(n)枚地雷。若從第n-1個地雷坑開始挖，此時有2種可能：第n-1個到第n個地雷坑無法走通(可由r(n-l,n)判斷)，此時可挖a(n-l)枚。第n-1個到第n個地雷坑可以走通，則可挖a(n-l)+a(n)枚。一般情況，若從第1個地雷坑開始挖，根據(jù)關系r,找出1后面的所有可以走通的地雷坑，從中找出一條可挖最多地雷的路線，這樣可得到最多的挖地雷數(shù)。上面計算出從每個地雷坑開始能挖到最多的地雷數(shù)，此時找出一個最大值即可2、 地雷堆之間的聯(lián)系可用以卜?的數(shù)組表示：二維整數(shù)型數(shù)組底亞]表示,當r[i]U]=l表示從1到J的地雷坑可以走通，當r[i]U]=O表示從1到j的地雷坑走不通。例子中表示如下：卜12345678910101011010002010110000300000000401100005011100600110701118011900100四、程序代碼1、程序輸入按照提示第一行輸入地雷坑的個數(shù)，第二行輸入地雷坑中地雷個數(shù)，之間用空格隔開。第三行按照表格輸入從第i行第1個地雷坑開始到第1行最后地雷坑是否可以走通，1表示走的通,0表示走不通，之間用空格，輸入完第1行回車輸入1+1行數(shù)據(jù)。直到最后一行。2、程序代碼#iiiclude<iostieam.h>#defuiemax100〃定義最大地雷坑數(shù)nitmam()fi〃初始化mta[max]={0};〃記錄地雷坑地雷個數(shù)mtr[max][max]={O);//r[i][j]id錄從i到j地雷坑是否走的通mtb[max][3]={0};//b[][l]id錄挖出雷德總數(shù),b[][2]記錄挖出雷位置mtij.h,cmax;mtn;〃數(shù)據(jù)輸入cout?"請輸入地雷坑的個數(shù)：”；cin?n;cout?"請輸入地雷坑里雷的個數(shù)：”；fbr(i=l;i<=n;i-H-)cin?a[i];}如(J=】；jv=n;j++){lf(J==l)COUt?"請輸入第”vvivv”行，從“VVjVV”開始是否走的通：”；cin?r[i]|j];)}〃動態(tài)規(guī)劃算法開始for(i=n;i>0;i--)〃從最后一個地雷坑開始cmax=O;h=O;fbr(j=i;j<=nJ++){if(in][j]==l&&b|j][l]>cmax)//找到第i到第j的坑是否走的通，并找出最大值(h=J；cmax=b[j][l];}b[i][l]=a[i]+cniax;//i己錄當前獲得地雷的總數(shù)b[i][2]=h;〃記錄地雷坑的位置)}cmax=O;h=0;for(i= 找出記錄中最大地雷總數(shù)if(b[i][l]>cniax){h=i;cmax=b[i][l];)}cout?M挖出最多雷數(shù)為：”vvcmax<veiidl;

if(h!=0)cout?”挖地雷的路徑為：”《h;〃輸出查出最大地雷的路徑while(b[h][2]!=0)h=b[h][2];cout?n—>H?h;}cout?endl;)五、運行結(jié)果rDOCUIEIiTS\C++PROJECT\vdl\Debug\Tdl.exe*?|口X請輸入弛嗇抗的個數(shù)：10精箱入地雷垸里雷的個數(shù)：8142171開始是否走的通：2開始是否走的通：3開始是否走的通：廣4rDOCUIEIiTS\C++PROJECT\vdl\Debug\Tdl.exe*?|口X請輸入弛嗇抗的個數(shù)：10精箱入地雷垸里雷的個數(shù)：8142171開始是否走的通：2開始是否走的通：3開始是否走的通：廣4”?,4開始是否走的通；計入?蜜5行，從5開始是否走的通：必第6行，從6開始是否走的通：必第7行，加開始是否走的通：次第8行，從8開始是否走的通：計入?第9行，從9開始是否走的通：行入虞10行，從1。開始是否走的通:藪為：1200000000003311e11ei1e02615iii11?010000000196打地雷特路徑為：1—->4—->5-一>6—->8—->9Pressanykeytocontinue俯'?旺曰六、結(jié)論分析《算法設計與分析》課程考核要求本課程在教學計劃中為考查課。考核形式采用大作業(yè)形式，以打印文檔形式（每班五份）及電子稿的形式（每個人都要）驗收并提交。一.考核內(nèi)容你選擇的大作業(yè)。二?具體要求每個學生分別選擇一個題目，可用各種算法（包括你自己的計算方法）解題。提交每一個題目的完整的完成報告，報告內(nèi)容包括：（1） 算法的由來及其應用（你為何選擇這個題目，它目前研究狀況，有何用處等等）；（2） 算法思想（可以用流程圖、自然語言或偽代碼來描述）；（3） 算法實現(xiàn)的源程序代碼（代碼的主要部分語句要有注釋，函數(shù)要有功能說明）；（4） （通過截圖的方式）給出程序運行的結(jié)果：（5）算法分析（對算法作一定的分析：可以從算法復雜度、優(yōu)缺點或改進方法等角度來分析）。每一個報告題目為“分治法（動態(tài)規(guī)劃/貪心法）大作業(yè)報告”。正文中的大標題分別為：問題陳述（即題目），分治法（動態(tài)規(guī)劃/貪心法）基本思想、算法描述、程序代碼、運行結(jié)果、結(jié)論分析。大作業(yè)報告必須提交電子稿。封面標題如上，并附上班級，學號和姓名等。正文部分一律用五號宋體字（各級標題字體可以自行調(diào)整）。注意排版盡量做到規(guī)范美觀?？梢詤⒖既魏钨Y料，但杜絕抄襲。源程序代碼必須通過驗收（即在驗收時要能夠說明各行代碼的作用）。電子稿形式，題目.doc加上源碼目錄打成一個壓縮包，壓縮包名稱：題目一姓名一短學號.rar,發(fā)給課代表（不要單獨發(fā)我!），由課代表收齊后統(tǒng)一打包發(fā)給我。6.提交和驗收時間：2013年1月15Do三.成績