旅游線路回路問題算法研究

甘偉雄

（陽江廣播電視大學，廣東 陽江 529500）

一、旅游回路問題

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

把 A理解為一個點即為尋找一個最佳組合構成一個回路：

二、問題分析

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

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

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

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

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

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

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

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

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

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

三、算法研究

算法舉例如下：

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

算法約束條件：

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

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

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

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

四、算法描述與總結

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

算法最難的部分主要是如何強設置0或者1，這樣通過比較最后值的大小來決定是否為最佳選擇，這部分的判斷非常重要，因為不同的子回路的強行設置為不通或者通，最終的答案都不一樣，只有把所有的可能形成的回路全部列舉，通過比較得出最接近的答案，這就成了一個NP問題。

[1]余文芳.計算機應用基礎[M].北京：人民郵電出版社，2004.

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

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