算法作業(yè)第七、八章-14s

7章作解：由題中所給的圖可以得到如下的樹來表示解空間a、從根節(jié)點1開始，沿著一條枝干進行搜索，首先搜索到1-2-6-5-4-b、發(fā)現(xiàn)已到葉節(jié)點且不符合環(huán)，退回到上一個節(jié)點4，搜索右孩子a、從根節(jié)點1開始，每一層依次搜索，即1-2-7-6-6-...-2-b、在搜索到1后找到符合條件的環(huán)，輸出為1-2-6-5-4-3-4-7-1解構(gòu)造一個由根構(gòu)成的單元素棧 Top(S)是目標節(jié)點 停止Pop(S)，把Top(S)的所有子節(jié)點壓入棧頂 S空Then失敗 goto將圖中所示的例子，沿著某一條枝干一直搜索下去，直到到達目標節(jié)點或者搜索完構(gòu)造一個由根構(gòu)成的單元素隊列 head(S)是目標節(jié)點 停止deqeue(S)，把enqueue(S)的所有子節(jié)點壓入隊列 S空Then失敗 goto將圖中所示的例子，沿著某一層一直搜索下去，直到到達目標節(jié)點或者搜索完畢構(gòu)造由根組成的單元素棧 Top(S)是目標節(jié)點 停止S的子節(jié)點按照其啟發(fā)測度由大到小的順序壓入 S空 失敗 goto使用評價函數(shù)構(gòu)造一個堆 首先構(gòu)造由根組成的單元素堆 H的根r是目標節(jié)點 停止從H中刪除r,把r的子節(jié)點 H空 失 goto解算法步驟：在這里，我們通過貪心的思想來產(chǎn)生界限，然后每個分支和這個界限進行比較 通過貪心策略得到最短路徑的一個一個上界v0v13v21v31T從根節(jié)點開始搜索，當遇到大于13的路徑時，停止搜索，剔除剩當遇到小于23的路徑時，更新上界，繼續(xù)搜索直到搜索完所Best-first策略搜索樹nf(n)=g(n)+h(n),g(n)n的路徑代價,h(n)n到某個目對于所有n, 當選擇到的節(jié)點是目標節(jié)點時算法停止,具體步驟如下首先算出每個節(jié)點的h(V11)min{1,4}7h(V12)min{7,9}7h(V13)min{3,4}3h(V14)min{4,7}4h(V21)min{6,7}6h(V22)min{3,4,5}h(V31)min{3}3h(V32)min{1}1h(V33)min{2}2h(V34)min{5)}5拓展setpg(V11)2,g(V12)5,g(V13)1,g(V14)f(V11)3,f(V12)12,f(V13)4,f(V14)step2：拓展g(V21)3,g(V22)6f(V31)9,f(V32)9step3：拓展 ..直到拓展到目標節(jié)點得到最短路徑v0v11v22v32T解：算法基本思想：用爬山法遞歸地劃分解空間得到二叉樹Cost(i,1)=max{Cost(k,1)| Cost(i,使右子樹代價下界增加最所有包含(i,j)所有不包含(i,j)計算出左右子樹的代價下在上述二叉樹建立算法中增加如下策略:最終結(jié)果為5->3->4->1->2->5，代價為回，所以得到處理后的集合為S{7,4,6,13,8}以起始節(jié)點0為根，構(gòu)造樹結(jié)構(gòu)，并求出根節(jié)點到每個節(jié)點的和，若大于K，則分支限界法：不存在這個方法，和深度優(yōu)先搜索類似，若大于 ，則舍解：分析每步移動最多只能使和目標狀態(tài)重復1.每步移動只可能產(chǎn)生三種結(jié)果，和目標狀態(tài)重11或不變。所以仍然A*算法解決。建立兩個度量f，h。f為到當前節(jié)點和目標重復的數(shù)目，h為當前節(jié)點的子節(jié)點和目標每次在當前節(jié)點可選集里選擇 入可選集8章作解這個算法只處理一邊。首先通過隨機選一個集`合S中的數(shù)sSsS1和大s的集S2，通過計算兩個集合中的集合個數(shù)來找k小的元素，最后一定以找到一個正確的解，只是算法的時間復雜度和選取s有關(guān)，故該算Sherwood算 對于集合S{s1,s2,...,sn}，隨機選定一個數(shù)s，劃分為兩個集合S1和S2，則有S1nS2n且S1S2nESin，從而存在常數(shù)b1，使E(Si)bn設(shè)所需的時間為T(n)Sn，劃分的集合中可能含有1n都相等

，則得到如下遞歸式：T(n) max(k1,nk))T k1取期望得到E(T(n))E(n max(k1,nk)) T

E(T

k1k1,nk k1

k

kn又max(k1,nkn

2kn2n是偶數(shù)時，從T(n)到T(n1)的每一項在總和中剛好2次，如n是奇數(shù)，2有的這些項都會出現(xiàn)兩次，而T(n)1次，故有E(T(n))n

E(T(k))用替換法求解上面的遞歸式：假設(shè)對滿足這個遞歸式初始條件的某個常數(shù)cE(T(n)cn，同時設(shè)O(nan，則可以得2 2c 2E(T(n))

kn

E(ck)an (kk)nk kn

((n1)n

(n1)n 2) (

2c((n1)n )nc(

n2)an

12) 3ncancn(cnc 當c4a時，且n 得到E(T(n))O(n)c4a解：算法基本思想：對于多項式p(x)q(x)r(x)，如果p(x)q(x)r(x，則其介數(shù)必定相等mnl，所以首先mnl是否成立，如果成立mn個數(shù)進試，如果相等則判斷p(x)q(x)r(x，否p(x)q(x)r(x)；如mnl，則p(x)q(xr(x)。POLYNOMIAL-ifmnlthenreturnfalseelsethenfori1tomx0rand(k,kreturn

p(x0)q(x0)r(x0thenreturn得到正確解的x0是從-k到k之間的隨機數(shù)mnl時假設(shè)有p(x)q(x)r(x)此時p(x)q(x)和r(x)都是mn介多項式，設(shè)二者的公共解的個數(shù)為h，則得到錯誤解的概PC11)mnC21)mnCh(1)mn2h(1h h h P1P12h(1解：算法基本思想：對于prC，共有pr個元素，當pr10000時，直接用先求解AB再與C比較，如果pr10000，則使用隨機算法pr個數(shù)中隨機RANDOMIZE-MATRIX-ifprthenusenomalmethodtojudgeelsethenfori1to(prmrand(1,k=ifkC[j,m]thenreturnfalsereturnture算法時間復雜度T(nOp1 1證明1.kmin-cut的大小,Gkn/2條邊。證.如果|G(E)|<kn/2,則存在一個度小于k的節(jié)點p.pk條,G劃分為兩個連通分量,p的連通分量.于是,與p相關(guān)連的邊集合是一個cut.但是這個cut的大小<k,與min-cut大小為kk最后得到的最小割必定是最小生成樹中的一條邊，再加上出去生成樹中的其它邊,,2步,A1發(fā)生,k(n-1)/2條邊(少一個節(jié)點C2/(n-1),Pr(A2|A11-2/(n-i步,A1Ai-1發(fā)生,n-i+1個節(jié)點,即至少2k(n-i+1)/2條邊于是Pr(Ai|1ji1Aj

n-i2最后我們有Pr(1in2Ai1in2(12(ni1))2n(n1)1故輸出最小割的概率為( 證明：題中感覺有點問題：通過如下算法，輸出的應(yīng)該是一個頂點覆蓋集合其中有如下公式成立：最小頂點覆蓋+最大獨立集 所以一個頂點覆蓋集I怎么會等于獨立集證明：對于如下圖所示的無向圖解：對于na1a2an，冒泡排序是先從a1開始，依次拿前面比較過最小的數(shù)與后面的數(shù)進行比較，在這里首先考慮a1a2an中最大元素b1所在的位置：n0；若最大元素的位置為n-1，則交換次數(shù)為1；1若最大元素的位置為1，則交換次數(shù)為n-1則此時最大元素b1的交換次數(shù)期望E(b1(12n1)n

11

n211故總E(b12n1n(n

n2 找出一定被篡改的函數(shù)值，即找出所有的x,y對進試，如果不滿足上面的等式，則認為函數(shù)值被篡改，添加進保存被篡改的自變量X集合和保存因變量的函數(shù)值Y中，假設(shè)兩個集合元素個數(shù)為k，所有的點對都測試完后，將X和Y中