索紅軍

(渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，陜西渭南714000)

0 引言

圖是一種多對多的復(fù)雜的網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，當給圖的各條邊賦予具有一定實際意義的數(shù)值時，就成為賦權(quán)圖(也稱為網(wǎng))，賦權(quán)圖是解決一些實際問題的非常有效的工具.賦權(quán)圖中兩頂點之間的最短路徑、賦權(quán)圖的最小生成樹等都與解決實際問題密切相關(guān).在此，我們提出應(yīng)用賦權(quán)圖解決環(huán)路訪問的最小代價問題研究.

1 問題的提出

在賦權(quán)圖中，研究過圖的遍歷、最小生成樹、最短路徑［1］、哈密爾頓回路［2］等很多方面.其中圖的遍歷要求從圖的一個頂點開始，訪問完所有頂點且每個頂點只能訪問一次即可，圖的最小生成樹只要求各頂點之間有通路且路徑的權(quán)值之和最小即可，最短路徑研究的是兩頂點間的路徑，哈密爾頓回路要求每個頂點只能訪問一次.然而現(xiàn)實問題中存在與哈密爾頓回路和最短路徑相似但又不同的問題，即從圖中某一頂點出發(fā)，訪問完所有的頂點后又要回到起點，例如快遞員從快遞公司出發(fā)送完貨物后又要回到快遞公司等.這樣的問題不同于傳統(tǒng)旅行商問題［3］，不要求每個頂點只到達(訪問)一次，也不完全等同于中國郵遞員問題［2］(歐拉回路)，不要求所有的邊都走到，但必須要求訪問完所有的頂點后，又要回到出發(fā)頂點，并且在整個過程中經(jīng)過的邊的權(quán)值之和最小.對于這樣的問題，在比較龐大的賦權(quán)圖中，目前還沒有公認的比較好的完全解決方案.二邊逐次修正法［4］等方案只能是尋找相對好遍歷路徑(不一定是最優(yōu)路徑)的解決方案.為了分析研究此類問題，提出以下定義：

賦權(quán)連通圖的最小環(huán)路遍歷路徑：在一個賦權(quán)圖中從某一頂點出發(fā)，沿圖的邊到達其他頂點，訪問完所有的頂點后，又回到出發(fā)點，整個過程經(jīng)過的邊的權(quán)值之和最小.將該過程經(jīng)過的頂點按順序排列即為賦權(quán)連通圖的最小環(huán)路遍歷路徑.

2 問題的分析

賦權(quán)圖的最小生成樹研究代價問題，這樣的方法對于像架設(shè)通信線路、鋪設(shè)管道等只要頂點之間有路徑即可的問題比較適合，對于像運送貨物等運送人員或車輛等必須返回到出發(fā)點的問題不適合，因為人員或車輛返回時同樣需要代價，而按照最小生成樹的路徑訪問完所有頂點并沿該路徑回溯返回到出發(fā)點，在整個運送環(huán)節(jié)中代價一般都比較大.

圖的遍歷只要求訪問完所有頂點，不關(guān)心代價問題.賦權(quán)圖的遍歷在不考慮代價的情況下可用深度優(yōu)先搜索和廣度優(yōu)先搜索方法，其中應(yīng)用深度優(yōu)先搜索遍歷時，當與某個頂點相關(guān)聯(lián)的頂點訪問完后，必須回溯到上一個頂點，當訪問完所有頂點并回溯到出發(fā)點時，將回溯過程應(yīng)用的邊和訪問走向下一個頂點應(yīng)用的邊同樣看待，這時整個過程經(jīng)過的頂點序列就是賦權(quán)連通圖的環(huán)路遍歷路徑.現(xiàn)在將訪問時走向下一個頂點應(yīng)用的邊和回溯時應(yīng)用的邊權(quán)值相加，就涉及到了賦權(quán)連通圖的環(huán)路遍歷及其代價問題.當訪問完所有頂點又回到出發(fā)點，所有進入下一個頂點的邊和回溯的邊的權(quán)值相加，就得到了賦權(quán)圖的環(huán)路遍歷代價，但這個代價一般都較大，因為深度優(yōu)先搜索遍歷是嚴格按照回溯方式進行的，而圖中存在環(huán)路，不需要通過回溯方式亦可進行遍歷.如圖1所示(圖中帶括號序號實線為訪問順序，帶括號虛線為回溯順序，不帶括號數(shù)字為權(quán)值)，從A出發(fā)沿圖中標明的實線序號訪問并沿虛線返回，遍歷完成后回到A，其權(quán)值總和為84，顯然不是最小的，原因是訪問頂點的順序不同導(dǎo)致回溯經(jīng)過的邊次數(shù)較多;某些地方的回溯可以更改，不需要回溯可以減少費用.容易發(fā)現(xiàn)，當參考廣度優(yōu)先搜索遍歷圖的策略進行圖的環(huán)路遍歷時，其代價將會更高.故此可知，應(yīng)用深度優(yōu)先搜索和廣度優(yōu)先搜索方案均不能完成賦權(quán)圖的最小環(huán)路遍歷問題.

圖1 圖的深度優(yōu)先搜索遍歷

3 問題解決的分析與研究

經(jīng)過分析，我們發(fā)現(xiàn)，參考深度優(yōu)先搜索策略進行圖的環(huán)路遍歷，要使環(huán)路遍歷總權(quán)值最小，應(yīng)該從兩方面考慮：首先不能按照深度優(yōu)先搜索策略完全回溯，可以通過權(quán)值小的環(huán)路邊取消一部分回溯;其次，若需要回溯，回溯的邊權(quán)值盡可能小.如在圖1所示的賦權(quán)圖中，若按照圖中順序訪問到頂點G時，先訪問H、I，再回溯到G，然后訪問D，再沿邊＜A，D＞直接回到出發(fā)點A，其中減少了標號為9、14、15、16的回溯邊，增加了邊＜A，D＞，按照這樣的路線訪問總權(quán)值為63，實現(xiàn)了最小.

對于任意一個賦權(quán)連通圖，如何進行環(huán)路遍歷，使其總的權(quán)值盡可能小.依據(jù)狄杰斯特拉(Dijkstra)算法［5］，提出以下賦權(quán)連通圖的最小環(huán)路遍歷方案：

(1)確定始點V1(也是終點);

(2)應(yīng)用狄杰斯特拉算法求出從始點 V1到其余各頂點 V2，V3，…，Vn的最短路徑權(quán)值 Dist1－2，Dist1－3，…，Dist1－n以及相應(yīng)的最短路徑 Path1－2，Path1－3，…，Path1－n;

(3)在各最短路徑權(quán)值 Dist1－2，Dist1－3，…，Dist1－n中查找最小路徑值 Dist1－i，并求出 Vi到 V1的次短路徑頂點序列Pathi－1;

(4)檢查兩個路徑序列Path1－i和Pathi－1中是否包含賦權(quán)圖的全部頂點，若已經(jīng)全部包含，則這兩個路徑的頂點序列順序即為在賦權(quán)連通圖中要找的環(huán)路遍歷路徑.否則，保持Path1－i不變，求出Vi到V1的下一個次短路徑頂點序列Pathi－1'，若路徑序列Path1－i和Pathi－1'包含賦權(quán)圖的全部頂點，則這兩個路徑的頂點序列順序即為在賦權(quán)圖中要找的環(huán)路遍歷路徑，若這兩個路徑仍然未包含完賦權(quán)圖的全部頂點，繼續(xù)檢查下一個次短路徑序列Pathi－1″，直到找到包含全部頂點的環(huán)路遍歷路徑或者Vi到V1的路徑已經(jīng)到達最大;

(5)若Vi到V1的路徑已經(jīng)到達最大時還未求出包含全部頂點的環(huán)路遍歷路徑序列，則從V1到Vi的次短路徑開始，繼續(xù)重復(fù)應(yīng)用上述過程，求出從Vi到V1的下一個次短路徑頂點序列并檢查，直到找到賦權(quán)圖中包含全部頂點的環(huán)路遍歷路徑序列為止.

經(jīng)分析，該方案不一定能找到權(quán)值總和最小的環(huán)路遍歷路徑，但可以找到權(quán)值總和比較小的環(huán)路遍歷路徑，在實際應(yīng)用中有一定的參考價值.同時比起二邊逐次修正法等方法實現(xiàn)起來簡單，容易理解，可以為相關(guān)的問題解決提供理論參考和借鑒.

4 結(jié)論

本文參考狄杰斯特拉(Dijkstra)算法，根據(jù)實際問題的具體情況，提出賦權(quán)連通圖中最小環(huán)路遍歷路徑以及求解最小環(huán)路遍歷路徑的方案，為現(xiàn)實中最優(yōu)行程方案設(shè)計及相關(guān)問題建立數(shù)學(xué)模型提供一定的理論基礎(chǔ)，以供大家在處理分析類似問題時參考和借鑒.

［1］耿國華.數(shù)據(jù)結(jié)構(gòu)［M］.北京：高等教育出版社，2005.

［2］喬維聲.離散數(shù)學(xué)［M］.西安：西安電子科技大學(xué)出版社，2005.

［3］李飛，白艷萍.用遺傳算法求解旅行商問題［J］.中北大學(xué)學(xué)報(自然科學(xué)版)，2007，28(1)：49－52.

［4］王締.最佳旅行問題的一種求解方法［J］.科教文匯(上旬刊)，2011，(8)：1 －3.

［5］嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)［M］.北京：清華大學(xué)出版社，2011.10.