算法分析與設(shè)計

算法分析與設(shè)計回溯法回溯法回溯法有“通用的解題法”之稱，用它可以系統(tǒng)地搜索一個問題的所有解或任一解?；厮莘ㄊ且粋€既帶有系統(tǒng)性又帶有跳躍性的搜索算法。在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間的任一結(jié)點(diǎn)時，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過以該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ㄇ髥栴}的所有解時，要回溯到問題的一個解就可結(jié)束。這種以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法，它適用于解組合數(shù)較大的問題。算法框架回溯法解問題時，首先應(yīng)定義問題的解空間。問題的解空間中應(yīng)至少包含問題的一個解。對0-1背包問題來講，當(dāng)n=3時，其解空間為：000 010001 100011 101110 111回溯法求0-1背包問題ABCDFEGHIJKLMNO11111110000000W=[16,15,15]P=[45,25,25]C=30回溯法求TSP問題1234306102054ACDEBFGHIJKLMNOPQ1234342423434232算法存在的問題對解空間的組織采用樹結(jié)構(gòu)，導(dǎo)致算法的效率比較低下。為了提高算法的效率，通常采用兩種策略來避免無效搜索，提高回溯法的效率。（1）利用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處，剪去不滿足約束的子樹；（2）用限界函數(shù)剪去得不到最優(yōu)解的子樹?；厮莘ǖ幕静襟E（1）針對所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。遞歸回溯voidBacktrack(intt){ if(t>n)output(x); else{ for(i=f(n,t);i<=g(n,t);i++){ x[t]=h(i); if(constraint(t)&&bound(t)) Backtrack(t+1); } }}子集樹與排列樹ABCDFEGHIJKLMNO11111110000000voidBacktrack(intt){if(t>n)output(t);else{for(inti=0;i<=1;i++){ x[t]=i; if(constaint(t) &&bound(t)) Backtrack(t+1);}} }子集樹與排列樹ACDEBFGHIJKLMNOPQ1234342423434232voidbacktrack(intt){if(t>n)output(x);else{for(i=t;i<=n;i++){swap(x[t],x[i]); if(constraint(t)&&bount(t)) backtrack(t+1); swap(x[t],x[i]);}}}裝載問題有一批共n個集裝箱要裝上2艘重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且當(dāng)n=3，c1=c2=50，w=[10,40,40]時，可以裝船；如果w=[20,40,40]，無法裝船。劃分問題裝載問題基本策略：首先將第1艘船盡可能裝滿，然后將剩余的集裝箱盡可能裝到第二艘輪船。約束條件李白打酒話說大詩人李白，一生好飲。幸好他從不開車。一天，他提著酒壺，從家里出來，酒壺中有酒2斗。他邊走邊唱：無事街上走，提壺去打酒。逢店加一倍，遇花喝一斗。這一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。請你計算李白遇到店和花的次序，可以把遇店記為a，遇花記為b。則：babaabbabbabbbb就是合理的次序。像這樣的答案一共有多少呢？請你計算出所有可能方案的個數(shù)（包含題目給出的）。n后問題在n*n的棋盤上放置彼此不受攻擊的n個皇后，按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n*n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上?；梅绞前岩恍?shù)字填寫在方陣中，使得行、列、兩條對角線的數(shù)字之和都相等。歐洲最著名的幻方是德國數(shù)學(xué)家、畫家迪勒創(chuàng)作的版畫《憂郁》中給出的一個4階幻方。他把1,2,3,...16這16個數(shù)字填寫在4x4的方格中。16??13??11?9??*?15?1表中有些數(shù)字已經(jīng)顯露出來，還有些用?和*代替。請你計算出?和*所代表的數(shù)字。并把*所代表的數(shù)字作為本題答案提交?；梅綌?shù)素數(shù)環(huán)是一個計算機(jī)程序問題，指的是將從1到n這n個整數(shù)圍成一個圓環(huán)，若其中任意2個相鄰的數(shù)字相加，結(jié)果均為素數(shù)，那么這個環(huán)就成為素數(shù)環(huán)?，F(xiàn)在要求輸入一個n，求n個數(shù)圍成一圈有多少種素數(shù)環(huán)，規(guī)定第一個數(shù)字是1。14325616523412385674125834761476583216743852素數(shù)環(huán)問題數(shù)字排列

將1到20排一列，要求每相鄰兩位數(shù)的和是質(zhì)數(shù)，試求排列的種數(shù)。連續(xù)郵資問題假設(shè)某國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵箱問題要求對于給定的n和m，給出郵票面值的最佳設(shè)計，在1張信封上貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。例如當(dāng)n=5，m=4時，面值為1，3，11，15，32的5種郵票可以貼出郵資的最大連續(xù)區(qū)間是1到70?；厮莘ㄍㄓ玫慕忸}法核心在于構(gòu)造解空間樹：子集樹排列樹回溯法是優(yōu)化的暴力搜索：不滿足限制條件；當(dāng)前解與最優(yōu)解進(jìn)行預(yù)計算；學(xué)習(xí)回溯法：心中有樹動態(tài)規(guī)劃適合兩個連續(xù)步驟之間有聯(lián)系的問題；回溯法幾乎適用于所有的問題，但問題之間最好有明確的層次?？偨Y(jié)39級臺階問題小明看完電影《第39級臺階》，離開電影院的時候，他數(shù)了數(shù)視覺的臺階數(shù)，恰好是39級。

站在臺階前，他突然又想起一個問題：如果我每一步只能邁上1個或2個臺階，先邁左腳，然后左右交替，最后一步邁右腳，也就是說一共要邁偶數(shù)步。那么，上完39級臺階，有多少種不同的上法呢？

請利用計算機(jī)的優(yōu)勢，幫助小明尋找答案。數(shù)字排列問題今有7對數(shù)字：兩個1，兩個2，兩個3，...兩個7，把它們排成一行。要求，兩個1間有1個其它數(shù)字，兩個2間有2個其它數(shù)字，以此類推，兩個7之間有7個其它數(shù)字。如下就是一個符合要求的排列：17126425374635當(dāng)然，如果把它倒過來，也是符合要求的。請你找出另一種符合要求的排列法，并且這個排列法是以74開頭的。注意：只填寫這個14位的整數(shù)，不能填寫任何多余的內(nèi)容，比如說明注釋等。74****4*7*******squareproblem

Givenasetofsticksofvariouslengths,isitpossibletojointhemend-to-endtoformasquare?

4111151020304050817264435yesnoyes回溯法通用的解題法核心在于構(gòu)造解空間樹：子集樹排列樹回溯法是優(yōu)化的暴力搜索：不滿足限制條件；當(dāng)前解與最優(yōu)解進(jìn)行預(yù)計算；學(xué)習(xí)回溯法：心中有樹迷宮系列迷宮問題給定一個m×n(m行,n列)的迷宮，迷宮中有兩個位置，gloria想從迷宮的一個位置走到另外一個位置，當(dāng)然迷宮中有些地方是空地，gloria可以穿越，有些地方是障礙，她必須繞行，從迷宮的一個位置，只能走到與它相鄰的4個位置中，當(dāng)然在行走過程中，gloria不能走到迷宮外面去。令人頭痛的是，gloria是個沒什么方向感的人，因此，她在行走過程中，不能轉(zhuǎn)太多彎了，否則她會暈倒的。我們假定給定的兩個位置都是空地，初始時，gloria所面向的方向未定，她可以選擇4個方向的任何一個出發(fā)，而不算成一次轉(zhuǎn)彎。gloria能從一個位置走到另外一個位置嗎？迷宮問題55...***.**...........*....1113

155...***.**...........*....2113

1

3x3的格子中填寫了一些整數(shù)。剪格子我們沿著圖中的紅色線剪開，得到兩個部分，每個部分的數(shù)字和都是60。本題的要求就是請你編程判定：對給定的mxn的格子中的整數(shù)，是否可以分割為兩個部分，使得這兩個區(qū)域的數(shù)字和相等。如果存在多種解答，請輸出包含左上角格子的那個區(qū)域包含的格子的最小數(shù)目。如果無法分割，則輸出0。羅密歐與朱麗葉的迷宮問題

羅密歐與朱麗葉身處一個m*n的迷宮中，每一個方格表示迷宮中的一個房間。這m*n個房間中有一些房間是封閉的，不允許任何人進(jìn)入。在迷宮中任何位置均可沿8個方向進(jìn)入未封閉的房間。羅密歐位于迷宮的(p,q)方格中，他必須找出一條通向朱麗葉所在的(r,s)方格中的路。在抵達(dá)朱麗葉之前，他必須走遍所在所有未封閉的房間各一次，而且要使到達(dá)朱麗葉的轉(zhuǎn)彎次數(shù)最少。每改變一次前進(jìn)方向算作轉(zhuǎn)彎一次。請設(shè)計一個算法幫助羅密歐找出這樣一條道路。羅密歐與朱麗葉的迷宮問題

輸入：3(n行數(shù))4(m列數(shù))2(k封閉房間數(shù))1234以上k行表示被封閉房間所在行列1122最后2行分別表示羅密歐和朱麗葉所在的方格輸出：6（最少轉(zhuǎn)彎次數(shù)）7（不同的最少轉(zhuǎn)彎道路數(shù)）1-19821067345-1以上n行m列表示迷宮的一條最少轉(zhuǎn)彎道路。k表示第k步到達(dá)，-1表示封閉房間總結(jié)構(gòu)造心中的解空間樹是關(guān)鍵；回溯法與函數(shù)的局部變量；訪問解空間樹的優(yōu)化處理；迷宮問題中的回溯法四鄰域八鄰域圖論問題

最大團(tuán)問題無向圖：連通不連通有向圖：弱連通單向連通強(qiáng)連通連通子圖（分支）

給定無向圖G=(V,E)，如果U

V，且對任意的u,v

U，都有(u,v)

E，則稱U是G的完全子圖。G的完全子圖U是G的一個團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G中的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。

最大團(tuán)問題符號三角形問題++-+-+++----+-+++--++--+---+右圖所示的三角形中，有14個“+“和14個“-”。2個同號下面是+，兩個異號下面是-。在一般情況下，符號三角形的第一行有n個符號。符號三角形問題，要求對于給定的n，計算有多少個不同的符號三角形，使其所含的“+”和“-”相同。符號三角形問題++-+-+++----+-+++--++--+---+++-+-+++----+-+++--++--+---+填數(shù)字第五屆藍(lán)橋杯軟件類省賽B組第7題圖的m著色問題

給定無向連通圖和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的兩個頂點(diǎn)有不同的顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊相連接的兩個頂點(diǎn)著不同顏色，稱這個數(shù)m為這個圖的色數(shù)。求一個圖的色數(shù)m稱為圖的m可著色優(yōu)化問題。給定一個圖以及m種顏色，請計算出涂色方案數(shù)。圖的m著色問題壘骰子問題賭圣atm晚年迷戀上了壘骰子，就是把骰子一個壘在另一個上邊，不能歪歪扭扭，要壘成方柱體。經(jīng)過長期觀察，atm發(fā)現(xiàn)了穩(wěn)定骰子的奧秘：有些數(shù)字的面貼著會互相排斥！我們先來規(guī)范一下骰子：1的對面是4，2的對面是5，3的對面是6。假設(shè)有m組互斥現(xiàn)象，每組中的那兩個數(shù)字的面緊貼在一起，骰子就不能穩(wěn)定的壘起來。atm想計算一下有多少種不同的可能的壘骰子方式。兩種壘骰子方式相同，當(dāng)且僅當(dāng)這兩種方式中對應(yīng)高度的骰子的對應(yīng)數(shù)字的朝向都相同。第六屆藍(lán)橋杯A組第9題壘骰子問題「輸入格式」第一行兩個整數(shù)nmn表示骰子數(shù)目接下來m行，每行兩個整數(shù)ab，表示a和b數(shù)字不能緊貼在一起?！篙敵龈袷健挂恍幸粋€數(shù)，表示答案模10^9+7的結(jié)果?！笜永斎搿?112「樣例輸出」544總結(jié)動態(tài)規(guī)劃由小到大構(gòu)造，不能優(yōu)化；動態(tài)規(guī)劃適合數(shù)據(jù)規(guī)模較小的問題；回溯由大向小分解，可以優(yōu)化；回溯可以處理數(shù)據(jù)規(guī)模較大的問題。電路板排列

將n塊電路板以最佳排列方案插入帶有n個插槽的機(jī)箱中，n塊電路板的不同的排列方式對應(yīng)在于不同的電路板插入方案。設(shè)B={1,2,...,n}是n塊電路板的集合，集合L={N1,N2,...,Nm}是n塊電路板的m個連接塊。其中每個連接塊Ni是B的一個子集，且Ni中的電路板用同一根導(dǎo)線在一起。例如，設(shè)n=8,m=5，給定n塊電路板及其m個連接塊如下：B={1,2,3,4,5,6,7,8}，L={N1,N2,N3,N4,N5}N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}

電路板排列問題

設(shè)x表示n塊電路板的排列，即在機(jī)箱的第i個插槽中插入電路板x[i]，x所確定的電路板排列密度density(x)定義為跨越相鄰電路板插槽的最大連線數(shù)。在設(shè)計機(jī)箱時，插槽一側(cè)的布線間隙由電路板排列的密度所決定，因此電路板排列問題要求對于給定電路板連接條件（連接塊），確定電路板的最佳排列，使其具有最小密度。

電路板排列問題最小長度電路板問題

最小長度電路板排列問題是大規(guī)模電子系統(tǒng)設(shè)計中提出的實(shí)際問題。該問題是：將n塊電路板以最佳排列方案插入帶有n個插槽的機(jī)箱中。n塊電路板的不同的排列方式對應(yīng)于不同的電路板插入方案。設(shè)B={1,2,...,n}是n塊電路板的集合，集合L={N1,N2,...,Nm}是n塊電路板的m個連接塊，其中每個連接塊Ni是B的一個子集，且Ni中的電路板用同一根導(dǎo)線連在一起。在最小長度電路板排列問題中，連接塊的長度是指該連接塊中第1塊電路板到最后一塊電路板之間的距離。算法設(shè)計：設(shè)計一個回溯法，找出所有給n個電路板的最佳排列，使得m個連接塊中最大長度達(dá)到最小。最小長度電路板問題

輸入：8（n）5（m）1111101010011101011010100110100000101001輸出：454316287

第k行的第j個數(shù)為0表示電路板k不在連接塊j中，為1表示電路板k在連接塊中。布線問題假設(shè)要將一組元件安裝在一塊線路板上，為此需要設(shè)計一個線路板布線方案。各元件的連線數(shù)由連線矩陣conn給出。元件i和j之間的連線數(shù)為conn(i,j)。如果將i安裝在線路板上位置r處，將j安裝在位置s處，則元件i和j之間的距離為dist(r,s)。確定了n個元件的位置，就確定了一個布線方案，此方案相應(yīng)的成本為林含OK設(shè)計算法，對于給定的n個元件，計算最佳布線方案，使費(fèi)用最小。輸入：3（n）233輸出：10（最少費(fèi)用）132（最佳布線方案）寶石排列拉丁矩陣問題現(xiàn)有n種不同形狀的寶石，每種寶石有足夠多顆。欲將這些寶石排列成m行n列的一個矩陣，m<=n，使矩陣中每一行和每一列的寶石都沒有相同的形狀。試設(shè)計一個算法，計算出對于給定的m和n，有多少種不同的寶石排列方案。衣冠坤輸入： 33輸出： 12排列寶石問題現(xiàn)有n種不同形狀的寶石，每種寶石有n顆，共有n2。同一種形態(tài)的n棵寶石具有n種不同的顏色?，F(xiàn)將n2顆寶石排列成n行n列的一個方陣，使方陣中的每一行和每一列都具有n種不同形狀和n種不同顏色。試設(shè)計一個算法，計算出對于給定的n，有多少種不同的寶石排寶石列方案。劉士新OK輸入： 1輸出： 1重復(fù)拉丁矩陣問題現(xiàn)有k種不同價值的寶石，每種寶石有足夠多顆。欲將這些寶石排列成m行n列的一個矩陣，m<=n，使矩陣中每一行和每一列的寶石數(shù)都沒有超過規(guī)定的數(shù)量。另外規(guī)定，寶石陣列的第1行從左向右和第1列從上到下的寶石按寶石的價值最小字典序從小到大排列。試設(shè)計一個算法，計算出對于給定的k，m和n以及每種寶石的規(guī)定數(shù)量，有多少種不同的寶石排列方案。衣冠坤輸入：4(m)7(n)3(k)223（共k個數(shù)，第j個數(shù)表示第j種寶石在每行列出現(xiàn)的最多次數(shù)）輸出：84309

給定n個大小不等的圓，現(xiàn)要將這n個圓排列成一個矩形框中，且要求各圓與矩形框的底邊相切。圓排列問題要求從n個圓的所有排列中找出有最小長度的圓排列。例如，當(dāng)n=3時，且所給3個圓的半徑分別為1，1，2時，這3個圓的最小長度的圓排列如下圖所示，其最小長度為

圓排列問題批處理作業(yè)調(diào)度給定n個作業(yè)的集合J={J1,J2,…,Jn}。每一個作業(yè)有兩項任務(wù)分別在兩臺機(jī)器上完成。每個作業(yè)必須先由機(jī)器1處理，再由機(jī)器2處理。作業(yè)Ji需要機(jī)器j的處理時間為tji，i=1,2,…n，j=1,2。對于一個確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時間。則所有作業(yè)在機(jī)器2上完成處理的時間和f=F21+F22+…+F2n稱為該作業(yè)調(diào)度的完成時間和。批處理作業(yè)調(diào)度問題要求，對于給定的n個作業(yè)，制定最佳的作業(yè)調(diào)度方案，使其完成時間和最小。批處理作業(yè)調(diào)度tji機(jī)器1機(jī)器2作業(yè)121作業(yè)231作業(yè)3231，2，3：3+6+10=192，3，1：4+8+9=21數(shù)獨(dú)問題145327698839654127672918543496185372218473956753296481367542819984761235521839764課后習(xí)題子集和問題子集和問題的一個實(shí)例為<S,c>。其中S={x1,x2,…,xn}是一個正整數(shù)的集合，c是一個正整數(shù)。子集和問題判定是否存在S的一個子集S1，使得S1中所有元素的和為c。試設(shè)計一個解子集和問題的回溯法。魏云鵬OK樣例輸入： 510 22654樣例輸出： 226最小重量機(jī)器設(shè)計問題設(shè)某一機(jī)器由n個部件組成，每一種價格都可以從m個不同的供應(yīng)商處購得。設(shè)wij是從供應(yīng)商j處購得的部件i的重量，cij是相應(yīng)的價格。試設(shè)計一個算法，給出總價格不超過d的最小重量機(jī)器設(shè)計。曹琦OK3(n)3(m)4(d)1233212221233212224131價格重量運(yùn)動員最佳配對問題

羽毛球隊有男女運(yùn)動員各n人，給定2個n*n矩陣P和Q，P[i][j]是男運(yùn)動員i和女運(yùn)動員j組成混合雙打的男運(yùn)動員競賽優(yōu)勢，Q[i][j]是女運(yùn)動員i和男運(yùn)動員j配合的女運(yùn)動員競賽優(yōu)勢。由于技術(shù)配合和心理狀態(tài)等各種因素的影響，P[i][j]不一定等于Q[j][i]。男運(yùn)動員i和女運(yùn)動員j本隊組成混合雙打的男女雙方競賽優(yōu)勢為P[i][j]*Q[j][i]，設(shè)計一個算法，計算男女運(yùn)動員最佳配對法，使各組男女雙方競賽優(yōu)勢的總和達(dá)到最大。高揚(yáng)OK運(yùn)動員最佳配對問題輸入：3（n）1023234345222353451輸出：52PQ無分隔符字典問題

設(shè)

={a1,a2,...,an}是n個互不相同的符號組成的符號集。Lk={b1b2...bk|bi

}是中字符組成的長度為k的字符串全體。SLk是Lk的1個無分隔符字典是指對任意的a1a2...akS和b1b2...bkS，有{a2a3...akb1,a3a4...b1b2,...,akb1b2...bk-1}∩S=Φ

無分隔符字典問題要求對給定的n和及正整數(shù)k，計算Lk的最大無分隔符字典。張豪輸入：2（n）2（k）輸出：2n色方柱問題

設(shè)有n個立方體，每個立方體的每一面用紅、黃、藍(lán)、綠等n種顏色之一染色。要把這n個立方體疊成一個方形柱體，使得柱體的4個側(cè)面的每一側(cè)均有n種不同的顏色。設(shè)計一個回溯算法，計算出n個立體的一種滿足要求的疊置方案。王彬OK輸入：4（n）RGBY021300302101210213133022輸出：RBGYRRYRBGRGBGRBGYGYYRBB整數(shù)變換問題問題描述：對于整數(shù)i的變換f和g分別定義如下：f(i)=3i,g(i)=i/2。設(shè)計一個算法，對于給定的2個整數(shù)n和m，用最少的f和g變換次數(shù)將n變換為m。王鑫例如，可以將整數(shù)15用4次變換將它變換為整數(shù)4，4=gfgg(15)。輸入：15（n）4（m）輸出：4gfgg工作分配問題設(shè)有n件工作分配給n個人。將工作i分配給第j個人所需要的費(fèi)用為cij。試設(shè)計一個算法，為每個人分配1件不同的工作，并使總費(fèi)用達(dá)到最小。王浩丞OK輸入： 3 1023 234 345輸出： 9最佳調(diào)度問題設(shè)有n個任務(wù)由k個可并行工作的機(jī)器來完成，完成任務(wù)i需要的時間為ti。設(shè)計一個算法找出完成這n個任務(wù)的最佳調(diào)度，使得完成所有任務(wù)的時間最早。李珊珊OK輸入：7（n）3（k）214416653（完成n個任務(wù)的時間）輸出：17無優(yōu)先級運(yùn)算問題給定n個正整數(shù)和4個運(yùn)算符+、-、*、/，且運(yùn)算符無優(yōu)先級，如2+3*5=25。對于任意給定的整數(shù)m，試設(shè)計一個算法，用以上給出的n個數(shù)和4個運(yùn)算符，產(chǎn)生整數(shù)m，且用的運(yùn)算次數(shù)最少。給出的n個數(shù)中每個數(shù)最多只能用1次，但每種運(yùn)算符可