動態(tài)規(guī)劃的關(guān)鍵算法.docx

動態(tài)規(guī)劃的關(guān)鍵算法Mf1432075許耀峰組號：201. 背景介紹1.1 PostgresSQL中的動態(tài)規(guī)劃算法所謂基于代價的動態(tài)規(guī)劃算法，就是窮舉所有可能的查詢的可執(zhí)行的方法，估算它們的代價，找出一個代價嘴角的來執(zhí)行，這是物理層次的優(yōu)化。在PostgresSQL中，基于代價的動態(tài)規(guī)劃算法應(yīng)用在物理查詢優(yōu)化階段求解最優(yōu)的多表連接路徑。1.2 物理查詢優(yōu)化在查詢優(yōu)化器實現(xiàn)的早期，使用的是邏輯優(yōu)化技術(shù)，即使用關(guān)系代數(shù)規(guī)則和啟發(fā)式規(guī)則對查詢進行優(yōu)化后，認為生成的執(zhí)行計劃就是最優(yōu)的。在引入了基于代價的查詢優(yōu)化方式后，對查詢執(zhí)行計劃做了定量的分析，對每一個可能的執(zhí)行方式進行評估，挑出代價最小的作為最優(yōu)的計劃。目前，數(shù)據(jù)庫的查詢優(yōu)化器通常融合了這兩種方式。2. 多表連接查詢多表連接算法實現(xiàn)的是在查詢路徑生成的過程中，根據(jù)代價估算，從各種可能的候選路徑中找出最優(yōu)的路徑（最優(yōu)路徑是代價最小的路徑）。多表連接算法需要解決兩個問題：（1） 多表連接的順序：表的不同的連接順序，會產(chǎn)生許多不同的連接路徑；不同的連接路徑有不同的效率。（2） 多表連接的搜索空間：因為多表連接的順序不同，產(chǎn)生的連接組合會有多種，如果這個組合的數(shù)目巨大，連接次數(shù)會達到一個很高的數(shù)量級，最大可能的連接次數(shù)是N ！（N 的階乘）2.1多表連接順序多表間的連接順序表示了查詢計劃樹的基本形態(tài)。一棵樹就是一種查詢路徑，SQL 的語義可以由多棵這樣的樹表達，從中選擇花費最少的樹，就是最優(yōu)查詢計劃形成的過程。而一棵樹包括左深連接樹、右深連接樹、緊密樹3 種形態(tài)。另外，即使是同一種樹的生成方式，也有細節(jié)需要考慮。在圖3-1a 中，A，B 和B，A 兩種連接方式花費可能不同。比如最終連接結(jié)果是A，B，C，但是需要驗證是A，B，C、A，C，B、B，C，A、B，A，C、C，A，B、C，B，A 中哪一個連接方式得到的結(jié)果，這就要求無論是哪種結(jié)果，都需要計算這6 種連接方式中每一種的花費，找出最優(yōu)的一種作為下次和其他表連接的依據(jù)。人們針對以上樹的形成、形成的樹的花費代價最少的，提出了諸多算法。樹的形成過程，主要有以下兩種策略：（1）至頂向下。從 SQL 表達式樹的樹根開始，向下進行，估計每個結(jié)點可能的執(zhí)行方法，計算每種組合的代價，從中挑選最優(yōu)的。（2）自底向上。從 SQL 表達式樹的樹葉開始，向上進行，計算每個子表達式的所有實現(xiàn)方法的代價，從中挑選最優(yōu)的，再和上層（靠近樹根）的進行連接，周而復(fù) 始直至樹根。2.2 常用的多表連接算法表與表進行連接，對多表連接進行搜索查找最優(yōu)查詢樹，通常有多種算法，比如啟發(fā)式、分枝界定計劃枚舉、爬山法、動態(tài)規(guī)劃、System R 優(yōu)化方法等。3. 動態(tài)規(guī)劃算法3.1 簡介20 世紀40 年代，Richard Bellman 最早使用了動態(tài)規(guī)劃這一概念，用以表述通過遍歷尋找最優(yōu)決策解問題?！皠討B(tài)規(guī)劃”（dynamic programming）中的programming 來自“數(shù)學(xué)規(guī)劃”（mathematical programming，又稱規(guī)劃），與“計算機編程”（computer programming）中的programming 沒有關(guān)系。規(guī)劃的含義是指生成活動的優(yōu)化策略，規(guī)劃意味著找到一個可行的活動計劃。動態(tài)規(guī)劃，是指決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，這就是“動態(tài)”的含義?！皠討B(tài)規(guī)劃”將待求解的問題分解為若干個子問題（子階段），按順序求解子問題，前一子問題的解為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。3.2 動態(tài)規(guī)劃的概念i. 階段。把求解問題的過程分成若干個相互聯(lián)系的階段，以便于求解。在多數(shù)情況下，階段變量是離散的。ii. 狀態(tài)。表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。iii. 無后效性。狀態(tài)應(yīng)該具有的性質(zhì)，如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響。iv. 決策。一個階段的狀態(tài)確定后，從該狀態(tài)演變到下一階段某個狀態(tài)的選擇（行動）稱為決策。v. 策略。由每個階段的決策組成的序列稱為策略。對于每一個實際的多階段決策過程，可供選取的策略有一定的范圍限制，這個范圍稱為允許策略集合。允許策略集合中達到最優(yōu)效果的策略稱為最優(yōu)策略。vi. 最優(yōu)化原理。如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。最優(yōu)化原理實際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)的。3.3 動態(tài)規(guī)劃的具體實現(xiàn)在數(shù)據(jù)庫領(lǐng)域，動態(tài)規(guī)劃算法主要解決的是多表連接的問題。動態(tài)規(guī)劃算法是從底向上進行的，即從葉子（單個表）開始算作一層，然后由底層開始對每層的關(guān)系做兩兩連接（如果滿足內(nèi)連接則兩兩連接，不滿足內(nèi)連接則不可對全部表進行兩兩連接操作），構(gòu)造出上層，逐次遞推到樹根。下面介紹具體步驟。步驟1初始狀態(tài)。構(gòu)造第一層關(guān)系，即葉子結(jié)點，每個葉子對應(yīng)一個單表，為每一個待連接的關(guān)系計算最優(yōu)路徑（單表的最優(yōu)路徑就是單表的最佳訪問方式，通過評估不同的單表的數(shù)據(jù)掃描方式花費，找出代價最小的作為每個單表的局部最優(yōu)路徑）。步驟2歸納。當(dāng)層數(shù)從第1 到n-1，假設(shè)已經(jīng)生成，則如何求解第n 層的關(guān)系方法有：（1）左深樹連接方式：將第n-1層的關(guān)系（有多個關(guān)系）與第一層中的每個關(guān)系連接，生成新的關(guān)系（對新關(guān)系的大小進行估算），放于第n 層，且每一個新關(guān)系，均求解其最優(yōu)路徑。（2）緊密樹連接方式：將第k層的關(guān)系每個關(guān)系，與第other_level層中的每個關(guān)系連接，生成新的關(guān)系（新的關(guān)系就存儲著形成這個關(guān)系的多種局部路徑，從中選出最優(yōu)的一個局部路徑）放于第n層，且每一個新的關(guān)系，均求解其最優(yōu)路徑。其中other_level = level k，level為要連接的基表個數(shù)。以上雖然分為兩步，但實際上步驟2 多次執(zhí)行，每一次執(zhí)行后生成的結(jié)果被下一次使用，即每層（k層）路徑的生成都是基于下層（k-1層）生成的最優(yōu)路徑的，這滿足最優(yōu)化原理的要求。動態(tài)規(guī)劃算法與System R 算法相比，增加了中間關(guān)系的大小估算。還有的改進算法，在生成第n 層的時候，除了通過第n-1 層和第一層連接外，還可以通過第n-2 層和第2 層連接，通過第n-3 層和第3 層連接3.4 緊密樹處理流程4. 遺傳算法4.1 概念遺傳算法（Genetic Algorithm，GA）是美國學(xué)者Holland 于1975 年首先提出來的。它是一種啟發(fā)式的優(yōu)化算法，是基于自然群體遺傳演化機制的高效探索算法。遺傳算法拋棄了傳統(tǒng)的搜索方式，模擬自然界生物進化過程，采用人工進化的方式對目標空間進行隨機化搜索。它將問題域中的可能解看作是群體的一個個體（染色體），并將每一個個體編碼成符號串形式，模擬達爾文的遺傳選擇和自然淘汰的生物進化過程，對群體反復(fù)進行基于遺傳學(xué)的操作（選擇、交叉、變異），根據(jù)預(yù)定的目標適應(yīng)度函數(shù)對每個個體進行評價，依據(jù)“適者生存，優(yōu)勝劣汰”的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。遺傳算法可以有效地利用已經(jīng)有的信息處理來搜索那些有希望改善解質(zhì)量的串，類似于自然進化，遺傳算法通過作用于“染色體”上的“基因”，尋找好的“染色體”來求解問題（對算法所產(chǎn)生的每個“染色體”進行評價，并基于適應(yīng)度值來改造“染色體”，使適用性好的“染色體”比適應(yīng)性差的“染色體”有更多的“繁殖機會”）。4.2 遺傳算法的具體實現(xiàn)遺傳算法主要步驟如下：1）隨機初始化種群；2）評估初始的種群，即為種群計算每個個體的適應(yīng)值且對所有個體排序；3）如果沒有達到預(yù)定演化數(shù)（可以是一個確定的、與連接的表的個數(shù)無關(guān)的值，這樣保證搜索空間一定