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

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

E(T(k))用替換法求解上面的遞歸式：假設(shè)對(duì)滿足這個(gè)遞歸式初始條件的某個(gè)常數(shù)cE(T(n)cn，同時(shí)設(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 當(dāng)c4a時(shí)，且n 得到E(T(n))O(n)c4a解：算法基本思想：對(duì)于多項(xiàng)式p(x)q(x)r(x)，如果p(x)q(x)r(x，則其介數(shù)必定相等mnl，所以首先mnl是否成立，如果成立mn個(gè)數(shù)進(jìn)試，如果相等則判斷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之間的隨機(jī)數(shù)mnl時(shí)假設(shè)有p(x)q(x)r(x)此時(shí)p(x)q(x)和r(x)都是mn介多項(xiàng)式，設(shè)二者的公共解的個(gè)數(shù)為h，則得到錯(cuò)誤解的概PC11)mnC21)mnCh(1)mn2h(1h h h P1P12h(1解：算法基本思想：對(duì)于prC，共有pr個(gè)元素，當(dāng)pr10000時(shí)，直接用先求解AB再與C比較，如果pr10000，則使用隨機(jī)算法pr個(gè)數(shù)中隨機(jī)RANDOMIZE-MATRIX-ifprthenusenomalmethodtojudgeelsethenfori1to(prmrand(1,k=ifkC[j,m]thenreturnfalsereturnture算法時(shí)間復(fù)雜度T(nOp1 1證明1.kmin-cut的大小,Gkn/2條邊。證.如果|G(E)|<kn/2,則存在一個(gè)度小于k的節(jié)點(diǎn)p.pk條,G劃分為兩個(gè)連通分量,p的連通分量.于是,與p相關(guān)連的邊集合是一個(gè)cut.但是這個(gè)cut的大小<k,與min-cut大小為kk最后得到的最小割必定是最小生成樹中的一條邊，再加上出去生成樹中的其它邊,,2步,A1發(fā)生,k(n-1)/2條邊(少一個(gè)節(jié)點(diǎn)C2/(n-1),Pr(A2|A11-2/(n-i步,A1Ai-1發(fā)生,n-i+1個(gè)節(jié)點(diǎn),即至少2k(n-i+1)/2條邊于是Pr(Ai|1ji1Aj

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

11

n211故總E(b12n1n(n

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