TSP問(wèn)題之動(dòng)態(tài)規(guī)劃法

1、旅行商問(wèn)題的動(dòng)態(tài)規(guī)劃方法，概述，旅行商問(wèn)題的一般解決方案，窮舉方法，動(dòng)態(tài)解決方案，動(dòng)態(tài)規(guī)劃方法，有條件的動(dòng)態(tài)規(guī)劃方法，解決共同的問(wèn)題，旅行商問(wèn)題，旅行商問(wèn)題描述：旅行者需要旅行到n個(gè)城市，他們只需要通過(guò)每個(gè)城市一次，然后返回到出發(fā)城市，并要求最短的距離。用窮舉法求解旅行商問(wèn)題，旅行商問(wèn)題是動(dòng)態(tài)規(guī)劃的，并假設(shè)找到一個(gè)最短的循環(huán)：S0S1S2 S3S0。我們可以得出這樣的結(jié)論：“S1S2 S3S0”一定是從S1到S0通過(guò)其他點(diǎn)的最短路徑。(如果沒(méi)有，就會(huì)有矛盾)，Length(總循環(huán))=Length(S0S1) Length(S1 S2 S3S0)，這樣可以簡(jiǎn)化問(wèn)題：為了求解從某個(gè)(任意)點(diǎn)到循環(huán)

2、中最后一點(diǎn)的最短路徑，TSP問(wèn)題動(dòng)態(tài)規(guī)劃，總循環(huán)長(zhǎng)度是從上面的公式分解而來(lái)的：Length(循環(huán))=Min Length(01) Length(10)，Length(02) Length(20)，Length(03) Length(30)，以標(biāo)準(zhǔn)化的方式表達(dá)上面的公式d(i)。V)表示通過(guò)點(diǎn)集的每個(gè)點(diǎn)一次后，從點(diǎn)I到起點(diǎn)的最短距離d(i，V) min Cik d(k，Vk) (kV) d(k)，Cik (ki)，其中ik表示ik的距離，從城市0到城市1，2，3然后回到城市0的最短路徑長(zhǎng)度為：d (0，1，3)，C02 d(2，1，3)，C03 d(3，1，2)這是最終決定。 其中必須基于d(1

3、，2，3)，d(2，1，3)和d(3，1，2)的計(jì)算結(jié)果，而：D (1，1，2) 3)=最小c21d (1，3)，c23d (3，1) d (3，1，2)=最小c31d (1，2)，c32d (2，1)繼續(xù)寫(xiě)：d (1，2)=c12 d (2，2) d (2，2) 3)=C13D (3)，d (2，1)=C23D 思考：這個(gè)過(guò)程讓人想起什么？理解了原理后，首先手工將結(jié)果寫(xiě)在表格中。結(jié)果如下：從偽代碼來(lái)看，我們應(yīng)該繼續(xù)解決以下問(wèn)題：如何在偽代碼中表達(dá)集合j？如何生成這樣的集合j？集合表示模型，動(dòng)態(tài)規(guī)劃方法(一)，動(dòng)態(tài)規(guī)劃方法：定義：每個(gè)子問(wèn)題只求解一次，并將其解保存在表中。當(dāng)需要再次求解這個(gè)子問(wèn)

4、題時(shí)，這個(gè)子問(wèn)題的解只需查表就可以得到，從而避免了大量的重復(fù)計(jì)算。特點(diǎn)：最優(yōu)子結(jié)構(gòu)，自底向上遞歸和重疊子問(wèn)題。使用動(dòng)態(tài)規(guī)劃方法的條件：?jiǎn)栴}符合最優(yōu)性原則，而動(dòng)態(tài)規(guī)劃方法(2)，最優(yōu)性原則：對(duì)于一個(gè)有n個(gè)輸入的優(yōu)化問(wèn)題，其求解過(guò)程通?？梢苑譃閹讉€(gè)階段，每個(gè)階段的決策只取決于前一階段的狀態(tài)，而決策所采取的行動(dòng)使?fàn)顟B(tài)發(fā)生變化，這就成為下一階段決策的基礎(chǔ)。不管過(guò)程的初始狀態(tài)和決策，其余的決策必須形成相對(duì)于由初始決策產(chǎn)生的狀態(tài)的最優(yōu)決策序列。該原理告訴我們，最優(yōu)問(wèn)題的任何實(shí)例的最優(yōu)解都是由該實(shí)例的子實(shí)例的最優(yōu)解組成的。一般來(lái)說(shuō)，如果最優(yōu)化原理成立，它表明通過(guò)動(dòng)態(tài)規(guī)劃解決問(wèn)題是可能的。解決問(wèn)題的關(guān)鍵在于獲得各階段的遞推關(guān)系。動(dòng)態(tài)規(guī)劃方法(3)，動(dòng)態(tài)規(guī)劃方法步驟(1)分段：將原問(wèn)題分解成幾個(gè)重疊的子問(wèn)題；(2)分析：分析問(wèn)題是否滿足最優(yōu)性原則，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞推公式；(3)解決方案：采用遞歸自底向上計(jì)算實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過(guò)程。動(dòng)態(tài)規(guī)劃法解決的常見(jiàn)問(wèn)題(1)、斐波那契數(shù)、動(dòng)態(tài)規(guī)劃法解決的常見(jiàn)問(wèn)題(2)、多段圖的最短路徑問(wèn)題、動(dòng)態(tài)規(guī)劃法解決的常見(jiàn)問(wèn)題(3)、POJ 1163數(shù)字三角形問(wèn)題描述：在上述數(shù)字三角形中從上到下尋找一條路徑，使通過(guò)該路徑的數(shù)字之和最大化。道路上的每一步只能走到左下方或右下方。我們只需要找到這個(gè)最大和，不給出具