甘偉雄

（陽江廣播電視大學(xué)，廣東 陽江 529500）

一、旅游回路問題

城市居民的旅游大都遵循同一事實(shí)：從一個城市出發(fā)，經(jīng)過若干旅游景點(diǎn)后，最終回到出發(fā)的城市。有數(shù)學(xué)模型的角度來說，就是從A城市出發(fā)，要去BCDE…X（BCDE…X，分別代表景點(diǎn)）景點(diǎn)游玩，最終回答A城市。把A作為出發(fā)點(diǎn)構(gòu)圖如下：

把 A理解為一個點(diǎn)即為尋找一個最佳組合構(gòu)成一個回路：

二、問題分析

旅游回路問題具備兩個基本的特征：

1.具有最優(yōu)子結(jié)構(gòu)特征?？梢杂梅醋C法得到證明，一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。通過對最優(yōu)子結(jié)構(gòu)特征的理解，旅游回路問題具有這樣的特征。

2.二是不具有后效性。而無后效性的特征，主要表現(xiàn)在當(dāng)計算完第k個狀態(tài)值，進(jìn)入到處理第k+1個狀態(tài)時，之前的所有1…k狀態(tài)的值都不會改變。

動態(tài)規(guī)劃是求解決策過程最優(yōu)的數(shù)學(xué)算法，也是運(yùn)籌學(xué)最為重要分支。1951年美國數(shù)學(xué)家貝爾曼（R.Bellman）團(tuán)隊(duì)，根據(jù)一類可以分為多階段子問題的特征，把一系列多階段決策問題轉(zhuǎn)換成一組互相聯(lián)系的分階段問題，按照一定的順序把子問題逐個加以解決。

使用動態(tài)規(guī)劃算法的題目必須同時具有兩個特點(diǎn)，一是具有最優(yōu)子結(jié)構(gòu)，二是不具有后效性。最優(yōu)子結(jié)構(gòu)的目的是該類問題需要計算出極值，在當(dāng)前狀態(tài)下的極值。最優(yōu)化原理可以用數(shù)學(xué)化語言表達(dá)就是：如果在處理某一優(yōu)化問題，需要依次作出一系列的決策 S1，S2，…，Sn，如果這個決策序列是最優(yōu)系列，那么任何一個整數(shù)k（1 < k < n），不管之前的k個決策結(jié)果是什么，往后的最優(yōu)決策根據(jù)前面決策的結(jié)果決定當(dāng)前的結(jié)果，不需要改變之前的結(jié)果，那么以后的決策系列Sk+1，Sk+2，…，Sn也是最優(yōu)系列。最優(yōu)化原理的特征是動態(tài)規(guī)劃的基礎(chǔ)和前提條件，沒有具備最優(yōu)子問題的題目，就相當(dāng)于沒有使用動態(tài)規(guī)劃方法解決問題的條件。動態(tài)規(guī)劃的過程中把每個決策系列的結(jié)果記錄在一個二維表中，通過不斷的比較和選擇得到原始問題的解。動態(tài)規(guī)劃的根本思想就是空間換時間。用動態(tài)規(guī)劃法解決問題通常分成三個階段：

第一，分段過程，將原始問題分解成若干個相互之間存在重疊關(guān)系的子問題；

第二，分析過程，分析原始問題是否具有最優(yōu)性原理，列出動態(tài)規(guī)劃數(shù)學(xué)表達(dá)式，也就是函數(shù)遞推式。

第三，求解過程，利用函數(shù)遞推式自底向上求解，真正實(shí)現(xiàn)動態(tài)規(guī)劃過程。逐步構(gòu)造出整個原始問題的最優(yōu)解。

在線路決策問題中，路線i或者被選入實(shí)際路線，或者不被選入，設(shè)xi表示路線 i選入旅游線路中的情況，則當(dāng)xi=0時，表示線路i沒有被選入真正旅游線路中，xi=1時，表示線路i被選入真正線路中。根據(jù)旅游線路選擇的要求，有如下約束條件以及函數(shù)遞推式：

通過這個函數(shù)遞推式，線路決策問題轉(zhuǎn)化為尋找一組系列，讓使目標(biāo)函數(shù)式（1）達(dá)到小的解向量X=(x1, x2, …, xn)。

三、算法研究

算法舉例如下：

表1 景點(diǎn)間里程數(shù)

算法約束條件：

第一，目標(biāo)唯一性：從表格看出從一個景點(diǎn)到另外一個景點(diǎn)，目的地必須唯一。理論上也不存在一個人同時到兩個或者兩個以上的景點(diǎn)參觀，反映到數(shù)學(xué)上來說，就是 A景點(diǎn)到F景點(diǎn)所在的列之和必須是“1”，而且只能是“1”。從算法的角度來說，保證的目的地的唯一性。

第二，來源地唯一性：從表格看出從一個景點(diǎn)到另外一個景點(diǎn)，出發(fā)地必須唯一。理論上也不存在一個人同時從兩個或者兩個以上的景點(diǎn)出發(fā)到另外一個景點(diǎn)，反映到數(shù)學(xué)上來說，就是A景點(diǎn)到F景點(diǎn)所在的行之和必須是“1”，而且只能是“1”。從算法的角度來說，保證的來源地的唯一性。

第三，必須構(gòu)成一個回路：舉例來說 A景點(diǎn)作為出發(fā)的，我們可以理解成自己的家，因?yàn)閺某＠韥碚f，人們出門旅游都是從家鄉(xiāng)出發(fā)，把家鄉(xiāng)理解成 A景點(diǎn)，旅行完了以后，最后回家，也就是回到 A景點(diǎn)，構(gòu)成一個回路。用字母表示：ABCDEFA。

第四，表格中的數(shù)據(jù)是二進(jìn)制數(shù)字，因?yàn)檫x擇只有兩種可能，要不選擇該條線路，要不舍去。最后也是最為關(guān)鍵的就是必須包含所有的景點(diǎn)，一個都不能落下。

四、算法描述與總結(jié)

當(dāng)沒有出現(xiàn) ABCDEFA的情況下，系統(tǒng)自動強(qiáng)行設(shè)定一些路線，比如出現(xiàn)ABEFA，和CD兩個回路，這時算法自動把C和D切斷，設(shè)置成不可通行的狀態(tài)，重新計算，直到可行為止。

算法最難的部分主要是如何強(qiáng)設(shè)置0或者1，這樣通過比較最后值的大小來決定是否為最佳選擇，這部分的判斷非常重要，因?yàn)椴煌淖踊芈返膹?qiáng)行設(shè)置為不通或者通，最終的答案都不一樣，只有把所有的可能形成的回路全部列舉，通過比較得出最接近的答案，這就成了一個NP問題。

[1]余文芳.計算機(jī)應(yīng)用基礎(chǔ)[M].北京：人民郵電出版社，2004.

[2]王曉東.計算機(jī)算法設(shè)計與分析[M].北京：電子工業(yè)出版社.

[3]夏昕，曹曉剛，唐勇.深入淺出Hibernate[M].北京：電子工業(yè)出版社，2007.