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

甘偉雄

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

一、旅游回路問題

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

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

二、問題分析

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

1.具有最優子結構特征。可以用反證法得到證明，一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。通過對最優子結構特征的理解，旅游回路問題具有這樣的特征。

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

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

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

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

第二，分析過程，分析原始問題是否具有最優性原理，列出動態規劃數學表達式，也就是函數遞推式。

第三，求解過程，利用函數遞推式自底向上求解，真正實現動態規劃過程。逐步構造出整個原始問題的最優解。

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

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

三、算法研究

算法舉例如下：

表1 景點間里程數

算法約束條件：

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

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

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

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

四、算法描述與總結

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

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

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

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

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