資源描述：
《算法分析解析與設(shè)計-2016-第3講.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、算法分析與設(shè)計第3講-2016山東大學上次內(nèi)容：(1)5個算法設(shè)計技術(shù)，分而治之，貪心法，回溯搜索(?,?-刪除,分支定界)，動態(tài)規(guī)劃，局部搜索(2)局部搜索設(shè)計近似算法，現(xiàn)在也有了。(3)說明什么是好算法，什么是壞算法。多項式時間算法是好算法，指數(shù)時間算法叫壞算法。(4)許多問題設(shè)計不出多項式時間求解算法，也有很多問題能找到多項式算法，以前的算法絕大多數(shù)都是多項式時間的。告訴人們正面的東西。(5)企圖把問題分類，能否分為兩類，一類可以設(shè)計多項式時間算法，另一類不能設(shè)計多項式時間算法。前人建立了一種模型，說明問題很難，怎樣說明。也是多年思考認識的結(jié)果。應用
2、背景：硬件測試，軟件測試，知識庫表達，推理SAT問題一般描述：實例：布爾變量集合：U={u1,u2,…,un}，項集合C={c1,c2,…,cm}，ck={yk1,yk2,…,ykt},ykj?{u1,u2,…,un,}.詢問：是否存在U的真值指派，使c1?c2?…?cm=1，就是為真(T)，ck=yk1?yk2?…?ykt在人工智能的搜索求解中，推理規(guī)則均采用合取范式表示。芯片測試，測試條件都表示為邏輯表達式。SatisfiabilityProblem不需要求出解來，只需要判定是或否。TSP問題：貨郎問題實例：城市集合：C={c1,c2,…,cm},d(
3、ci,cj)?Z+，ci,cj?C，正整數(shù)K.詢問：是否存在城市排列?c?(1),c?(2),…,c?(m)?，使Hamilton回路問題：實例：無向簡單圖G=(V,E)，
4、V
5、=n。詢問：是否存在V的頂點排列v?(1),v?(2),…,v?(n)，使(v?(i),v?(i+1))?E(G),i=1,…,n，v?(n+1)=v?(1)。上述三個問題均是詢問解的存在性，判斷是否具有滿足條件的解。這三個問題都找不到多項式時間算法，但都能找到指數(shù)時間算法。什么是多項式時間？什么是指數(shù)時間？輸入長度：問題實例的規(guī)模。問題的算法時間復雜性有很多，什么樣的好呢？每秒1
6、百萬次/運算速度T(n)問題輸入長度n102030405060n0.000010.000020.000030.000040.000050.00006n20.00010.00040.00090.00160.00250.0036n30.0010.0080.0270.0640.1250.216n510.132012431.7分25.2分130分2n0.001117.9分12.7天35.7年366世紀3n0.05958分6.5年3855世紀表說明多項式時間復雜度與指數(shù)時間復雜度，區(qū)別大。主要是增長速度區(qū)別。多項式時間算法是好算法，指數(shù)時間算法是壞算法。這樣的說法未
7、必絕對合理，很多人接受。從頭所起，從定義圖靈機開始?！?.2確定型圖靈機與P類前面定義的時間復雜度概念還比較模糊，模糊就說不清楚。下面要說明什么是多項式時間可以求解的問題，實際要定義多項式時間復雜度，什么是時間復雜度，什么是空間復雜度，重新精確定義。自圓其說，說明自然界中的問題，解決問題。英文名字：DTM(1)一個硬殼存儲帶：一個方格存一個符號；讀寫頭在那里，可以左右移動，一次移動一個方格。狀態(tài)控制器可以讀寫帶方格中的內(nèi)容；(2)硬殼中放入數(shù)據(jù)；帶上放的符號：有限個，其中包括空白符號b，?=??，?是輸入符號集合。符號有限個，不能無限多個。(3)有限
8、個狀態(tài)；狀態(tài)個數(shù)不隨問題實例長度變化而變化。Q={q0,q1,q2,…,qy,qn}，q0：起始狀態(tài)，qy,qn都是停機狀態(tài)，qy表示停機時回答yes，qn表示停機時回答no。qf={qy,qn}q0q1qy(4)狀態(tài)轉(zhuǎn)換規(guī)則。什么是狀態(tài)，三要素表示DTM狀態(tài)：(1)q;(2)讀寫頭指向位置;(3)帶符號s，現(xiàn)在不關(guān)心讀寫頭位置，只關(guān)心讀寫頭指定帶方格的符號。在造計算機時，有一個地址寄存器，即讀寫頭。狀態(tài)轉(zhuǎn)換規(guī)則就是程序：(Q-{qf})???Q????：這是一個映射，程序語句，怎么改變狀態(tài)。?(qi,si)?()：含義，當前狀態(tài)qi，當前讀寫頭所指方格中
9、的符號si，則下一個狀態(tài)，將帶方格中的符號修改為，讀寫頭移動一個位置：?={L,R,S}程序?qū)嶋H就是狀態(tài)轉(zhuǎn)換規(guī)則：初始狀態(tài)q0，按照程序轉(zhuǎn)換狀態(tài)，到結(jié)束時狀態(tài)qf，回答yes或no。我們編的程序就是告訴計算機怎樣改變狀態(tài)。真正實現(xiàn)計算機，還有很多工作，怎樣用語言的形式描述狀態(tài)轉(zhuǎn)換規(guī)則。哪些硬件，哪些軟件，電子計算機怎樣實現(xiàn)。先有模型，后有計算機。例子：利用Turing機判斷正整數(shù)的奇偶性。實例：二進制正整數(shù)B，詢問：B是否為偶數(shù)？(1)?={0,1,b}；(2)Q={q0,q1,q2,qy,qn}(3)狀態(tài)轉(zhuǎn)換規(guī)則如下：想法，找到最后一位，判斷0或1Q01
10、bq0(q0,0,r)(q0,1,r)(q1,b,l)q1(q2,
