基于群論的頻率圖在旅行商問題中的應(yīng)用

摘要： 針對最小生成樹（minimum spanning tree，MST）和旅行商問題（travelling salesman problem，TSP），介紹了完全圖上的兩類特殊圖并定義了這些圖上的交運算，每類特殊圖和交運算構(gòu)成一個半群。根據(jù)半群性質(zhì)計算出頻率圖，分析了最優(yōu)哈密頓圈（optimal Hamiltonian cycle，OHC）和MST中邊的頻率性質(zhì)，證明了頻率圖上OHC中邊的頻率下界，該頻率下界用于縮小OHC的搜索空間，降低了TSP的求解難度。此外，采用一些TSP算例驗證了頻率圖上OHC中邊的頻率性質(zhì)。

關(guān)鍵詞： 半群； 特殊圖； 頻率圖； 旅行商問題； 最小生成樹

中圖分類號： TP301.6

文獻(xiàn)標(biāo)志碼： A

文章編號： 1671-6841（2025）01-0074-07

DOI： 10.13705/j.issn.1671-6841.2023186

Application of Frequency Graph Based on Group Theory

in the Traveling Salesman Problem

WANG Yong

（School of New Energy， North China Electric Power University， Beijing 102206， China）

Abstract： For the minimum spanning tree （MST） and travelling salesman problem （TSP）， two kinds of special graphs in complete graph were introduced and the intersection operation for the graphs was defined. Each kind of special graphs and the intersection operation formed one semi-group. According to the property of semi-group， the frequency graph was computed. The frequency properties for edges in optimal Hamiltonian cycle （OHC） and MST were analyzed. The lower frequency bound for the OHC edges was proven，and it greatly reduced the search space of OHC and decreased the hardness of TSP.Furthermore， the frequency properties for the OHC edges in frequency graphs were verified with some TSP instances.

Key words： semi-group; special graph; frequency graph; travelling salesman problem;minimum spanning tree

0引言

圖是一種常用的離散結(jié)構(gòu)模型，廣泛應(yīng)用于很多的離散優(yōu)化問題和算法設(shè)計中，比如最小生成樹、最大網(wǎng)絡(luò)流、圖染色、旅行商問題等。它們有的屬于P問題，有的屬于NP問題，圖上NP問題及其求解方法是理論計算機和運籌學(xué)研究的焦點之一。

最小生成樹（minimum spanning tree，MST）和旅行商問題（travelling salesman problem，TSP）分別是圖上的P和NP問題。20世紀(jì)50年代已經(jīng)出現(xiàn)了MST的多項式時間算法^［1］，但至今還沒有發(fā)現(xiàn)一般TSP的多項式時間算法，多數(shù)算法易于陷入局部最優(yōu)解^［2］。TSP精確算法的計算時間為O（n²2ⁿ）^［3］，對于滿足三角不等式的TSP，有理論證明近似算法的近似比不小于123/122^［4］。

近20年來，學(xué)者們發(fā)現(xiàn)稀疏圖上TSP存在計算時間更小的算法。Bjrklund等^［5］證明了稀疏圖上TSP精確算法的計算時間為O（（2-ε）ⁿ），其中ε取決于圖上節(jié)點的最大度。對于3-正則圖上的TSP，Xiao等^［6］給出的計算時間為O（1.2312ⁿ）。因此，把TSP完全圖轉(zhuǎn)化為稀疏圖，會大幅度減小TSP的搜索空間和算法運行時間。

根據(jù)2-opt 規(guī)則，Jonker等^［7］

找到一部分非最優(yōu)哈密頓圈（optimal Hamiltonian cycle，OHC）中邊，當(dāng)把這些邊刪除后，求解保留圖上一些歐氏TSP的計算時間會縮短一半左右。Hougardy等^［8］采用3-opt規(guī)則設(shè)計出三階段算法，把TSP完全圖轉(zhuǎn)化為稀疏圖，實驗發(fā)現(xiàn)，某些稀疏圖上TSP的求解時間大幅度縮短。Wang等^［9］采用完全圖上給定端點的最優(yōu)路徑計算頻率圖，頻率圖中一條邊的頻率是包含這條邊的給定端點的最優(yōu)路徑的數(shù)量。當(dāng)采用給定端點的最優(yōu)4-節(jié)點路徑計算頻率圖時，OHC中邊的最小頻率大于所有邊的平均頻率和大部分其他邊的頻率。OHC結(jié)構(gòu)保證其中的邊位于很多局部點集組成的凸集對應(yīng)的凸包上，根據(jù)這些凸集中的點構(gòu)造出的頻率四邊形內(nèi)OHC中邊具有較大的頻率。相反，其他多數(shù)邊位于凸包內(nèi)部，在這些頻率四邊形中的頻率較小。這些結(jié)果解釋了某些短邊不屬于OHC而有些長邊屬于OHC的原因。

同時發(fā)現(xiàn)，根據(jù)邊的頻率刪除一部分頻率較小的邊后，采用保留圖內(nèi)的頻率四邊形計算邊的頻率，OHC中邊的頻率仍然大于大部分其他邊的頻率。進(jìn)一步說明OHC中邊位于多數(shù)凸集的凸包上，當(dāng)凸集內(nèi)部的邊被刪除后，雖然邊的數(shù)量變小，但凸包上的邊沒有改變。因此，在保留圖上OHC中邊仍然具有較大的頻率。根據(jù)這些發(fā)現(xiàn)，文獻(xiàn)［9］設(shè)計出稀疏圖計算方法。實驗結(jié)果顯示，生成的稀疏圖大概率包含OHC，OHC的搜索空間大幅度降低，TSP的求解時間也隨之減少^{［5，7-8］}。

一般采用完全賦權(quán)圖K表示TSP，但賦權(quán)圖上OHC中邊的權(quán)值并沒有特殊的特征，通常不能根據(jù)邊的權(quán)值判斷一條邊是否屬于OHC。為了降低TSP的求解難度，文獻(xiàn)［9］提出了頻率圖及其計算方法，主要研究了采用給定端點的最優(yōu)4-節(jié)點路徑計算出的頻率圖上OHC中邊的頻率特點。雖然發(fā)現(xiàn)OHC中邊的頻率與其他大多數(shù)邊的頻率不同，但選用的方法比較簡單。采用包含更多節(jié)點的給定端點的最優(yōu)路徑計算出的頻率圖上OHC中邊的頻率，其特點尚不清楚。為了解決這個問題，本文定義了MST和給定端點的最優(yōu)路徑上的交運算及其運算規(guī)則，使之構(gòu)成半群，為頻率圖的特殊性質(zhì)奠定了基礎(chǔ)。根據(jù)群論提出一種保證邊的頻率性質(zhì)的頻率圖計算方法，當(dāng)采用給定端點的最優(yōu)k-節(jié)點路徑（k≥5）計算頻率圖時，證明了頻率圖上OHC中邊的頻率下界。

1兩類特殊圖及其交運算

1.1MST和給定端點的最優(yōu)路徑

完全圖K包含多種圖，有些圖具有特殊的性質(zhì)，比如MST和OHC。如果多個圖具有相同的結(jié)構(gòu)和性質(zhì)，則它們被當(dāng)作一類圖。對于一類圖，可以定義圖之間的運算。任給兩個或多個圖，如果某種運算的結(jié)果仍然屬于這類圖，稱這類圖上的這種運算是封閉的。如果這種運算又滿足結(jié)合律，那么這類圖和這種運算構(gòu)成一個半群。再者，如果這類圖中存在零元素、單位元素和逆元素，這類圖和運算形成一個群。針對MST和TSP，定義兩類特殊圖。

定義1完全圖上的MST：任給一個包含k個節(jié)點v（1≤i≤k）的完全賦權(quán)圖K（V，E，W），連接圖中所有節(jié)點且邊上權(quán)值和最小的生成樹稱為圖K的最小生成樹，記為MST。其中點集V={v， v， …， v}，邊集E={（v， v） v， v∈V，1≤i≠j≤k}，所有邊的權(quán)值W={wv， v∈V，1≤i≠j≤k}。

K中一共有2ⁿ個子圖，除去空圖和單點圖，其余每個完全子圖均有一個MST，因此有2ⁿ-n-1個MST，所有MST構(gòu)成集合

S

T={MST1≤i≤2ⁿ-n-1}。而且，具有較多節(jié)點的MST包含具有較少節(jié)點的MST，只有一部分具有較少節(jié)點的MST被具有較多節(jié)點的MST包含。

定義2給定端點的最優(yōu)路徑（optimal path，OP）^［9］：任給一個包含k（k≥4）個節(jié)點v（1≤i≤k）的完全賦權(quán)圖K（V，E，W），假設(shè)兩個節(jié)點v，v（v≠v∈V）作為端點，其余k-2個節(jié)點作為中間節(jié)點，構(gòu)成的權(quán)值最小的路徑稱為給定端點v，v的最優(yōu)路徑，簡稱為最優(yōu)路徑，記為OP，其中V，E，W的含義與MST定義中的含義相同。包含k個節(jié)點的完全圖中一共有k（k-1）/2條最優(yōu)路徑。

當(dāng)k≥2時，K中給定端點的最優(yōu)路徑有n（n-1）2^n-3條，K中的邊和3-節(jié)點路徑也屬于給定端點的最優(yōu)路徑。不考慮空圖和單點圖，所有OP的數(shù)量為n（n-1）2^n-3，構(gòu)成最優(yōu)路徑集合O

P=

{OP1≤i≤n（n-1）2^n-3}。同樣，只有部分具有較少節(jié)點的OP被具有較多節(jié)點的OP包含。

1.2MST和OP上的交運算

下面定義集合

S

T

和O

P

中元素的交運算。為方便描述，兩個集合及其圖元素統(tǒng)一用符號

G

={G， G， …， G，…， G， …}表示。

G上二元交運算定義如下。

定義3

圖集合G上的二元交運算：給定集合

G

中的兩個圖G和G，G和G交運算的結(jié)果為G，記為G=GG。

需說明一點，MST和OP均為連通圖，G和G交運算的結(jié)果可能為非連通圖和空圖，為確保運算的封閉性，增加非連通圖、零圖。指定非連通圖為G、零圖為。

另外，指定完全圖K為單位圖。所指定的非連通圖、零圖和單位圖均不具備MST和OP的性質(zhì)，但對于一個具體實例，零圖和單位圖都隱含著自身權(quán)值固定的性質(zhì)。非連通圖G是G

中某兩個圖交運算后的一個結(jié)果，與任何一個MST或OP的性質(zhì)不同，可用一個元素代表。G與其他非零圖運算的結(jié)果仍然為自身，確保G

上運算的封閉性。增加零圖、非連通圖和單位圖后，

G

={， G， G， G， …， G，…， G， …， K， …}。

G

中元素的二元運算遵循的運算定律為

GG=G，（1）

GG=GG，（2）

G（GG）=（GG）G，（3）

G=，（4）

GK=G。（5）

無論對于

S

T

還是O

P

，定義的二元運算均具有封閉性，且滿足交換律和結(jié)合律。因此，

〈

ST

，〉和〈O

P

，〉構(gòu)成兩個半群，統(tǒng)一記為

=〈G

，〉。

2基于半群的頻率圖

給定一個完全圖K，其中某些小規(guī)模MST和OP被大量的大規(guī)模MST和OP包含。并且，大多數(shù)小規(guī)模MST和OP被數(shù)量不多的大規(guī)模MST和OP包含。對于被大量的大規(guī)模MST和OP包含的小規(guī)模MST和OP，從概率角度分析，它們對構(gòu)成所有MST和OP的貢獻(xiàn)更大。因此，可以從一組已知的MST和OP中枚舉出小規(guī)模MST和OP的頻率，從而為尋找特定的大規(guī)模MST和OP提供指引信息。

定義4

一個圖的頻率：定義一類圖和交運算構(gòu)成半群=

〈G

，〉，給定G

中一個圖G，對于

G

中其他所有圖G，枚舉出公式GG=G成立的次數(shù)，作為G的頻率。

定義5頻率圖（frequency graph，F(xiàn)G）：對于K中的一條邊e=（v， v），它在

S

T

或O

P

內(nèi)其他圖中出現(xiàn)的次數(shù)當(dāng)作邊e的頻率，記為f（e）=f（v， v）。當(dāng)每條邊的頻率從

S

T

或O

P

內(nèi)的圖中枚舉出來后，所有邊和邊上的頻率形成一個頻率圖，記為FG。

當(dāng)K和圖的性質(zhì)確定后，可以從K中提取出這類圖G

。對于MST或OP，G

和構(gòu)成一個半群

=

〈G

，〉。對于其中每個圖G∈G

，都有一個頻率圖FG與之對應(yīng)。所有的FG構(gòu)成一個頻率圖集合

FG

。根據(jù)FG的定義可知，G

到FG

的映射是一個雙射，即FG=T（G），T為基于半群

的一種變換。

半群

=〈G

，〉中每個圖G具有相同的性質(zhì)，由于這種性質(zhì)的作用，大規(guī)模圖僅包含少部分小規(guī)模圖。根據(jù)

中兩個圖交運算的結(jié)果衡量圖之間的接近程度，對于兩個圖G和G，

它們的運算結(jié)果

G=GG越大，這兩個圖越靠近，其中

G為G的模（不考慮非連通圖的情況）。

對于K

上的MST和OP，邊是具有意義的最小的圖元素。取出G

中包含i個節(jié)點的所有圖{G}，如果某條邊e與每個圖都相交，即

eG=1成立，則e一定屬于最大規(guī)模的圖中邊。在這種情況下，e從{G}中枚舉出的頻率達(dá)到最大。因此，F(xiàn)G中邊的頻率反映了一條邊與大規(guī)模圖的接近程度。由于

中圖的總數(shù)有限，而且大規(guī)模圖僅包含少部分小規(guī)模圖，因此大頻率的邊一定被多數(shù)圖包含，它們對構(gòu)成更大規(guī)模的圖甚至最大規(guī)模的圖具有重要作用。

對于MST和OP，G

中圖的數(shù)量隨問題規(guī)模n呈指數(shù)增長。當(dāng)n足夠大時，采用全部圖計算小規(guī)模圖或邊的頻率是行不通的。因此，有必要從

G

中選一部分圖構(gòu)成一個半群計算圖的頻率和FG。給定K上一個半群

=〈G

，〉，對于其中一個圖G，

G

被分為k個子集S， S，…， S，根據(jù)每個子集S（1≤i≤k）計算出的G的頻率（或FG）相同。如果把〈｛G｝，〉當(dāng)作

=〈G

，〉的一個正規(guī)半群，那么〈S，〉，〈S，〉，…，〈S，〉就是計算出的圖G的頻率或FG的陪集，具體定義如下。

定義6

〈｛G｝，〉的陪集：給定一個半群

=〈G

，〉，對于一個圖G∈G

，G

被分為k個子集S， S，…， S，且采用每個子集中的圖計算出的G的頻率（或FG）相同。那么，

〈S，〉，〈S，〉，…，〈S，〉稱為〈｛G｝，〉的陪集，記為

G

/G。

〈｛G｝，〉的陪集代表對G

中圖元素的一個劃分，k值越大，每個陪集中的圖越少，計算FG越容易。下面介紹一種尋找一個圖G的陪集的近似方法。

給定一個半群=〈G

，〉和G∈G

，假設(shè)G

有N個圖元素，G被N個圖包含，那么G被任一個圖包含的概率記為p（G）=N/N。從

G

中隨機采樣I個圖構(gòu)成集合S，那么有X≤I個圖包含G的情況遵循一個二項分布。當(dāng)X=i時，二項分布表示為

P（X=i）=C（I，i）（p（G））ⁱ（1-p（G））^（I-i）。（6）

當(dāng)I足夠大時，根據(jù)大數(shù)定律，依據(jù)采樣圖計算出的G被任一個圖包含的概率逼近期望概率p（G）。因此，〈S，〉可以當(dāng)作〈｛G｝，〉

的一個近似陪集。接下來，如果IN-I，可以在剩余圖構(gòu)成的集合{

G

-S}中繼續(xù)上述采樣，陸續(xù)獲得其他陪集。

特殊情況下，當(dāng)G變成一條邊e時，（6）式仍然成立。因此，可以采樣一定數(shù)量的圖計算每條邊的頻率，從而得到FG，進(jìn)而通過邊的頻率分析小規(guī)模圖和大規(guī)模圖之間的轉(zhuǎn)換規(guī)律。如果通過FG尋找KgkbgBAbmQYfC/QDFMHR/1A==上的MST和OHC，計算FG的代價是一樣的。

原則上可以采用任何G計算FG，如果一個圖上有N個不同的子圖，對應(yīng)的FG有2^N個。事實上，任何G都是

F

G

中的一個元素。

3OHC和MST中邊的頻率性質(zhì)

采用最優(yōu)4-節(jié)點路徑計算邊的頻率，OHC中邊的最小頻率大于所有邊的平均頻率和大部分其他邊的頻率^［10］。K上每個K包含6條最優(yōu)4-節(jié)點路徑，每條邊被（n-2）（n-3）/2個K包含，在包含OHC中某邊的一個K中，平均情況下，該邊被2條或以上最優(yōu)4-節(jié)點路徑包含。當(dāng)采用最優(yōu)i-節(jié)點路徑（i≥5）計算邊的頻率時，具有下面相同的規(guī)律。

定理1任給K上一個包含OHC中某條邊e的K（i≥5），K中有i（i-1）/2條最優(yōu)i-節(jié)點路徑。兩種最壞情況下，e分別被7i（i-1）/36條和i（i-1）/4條這樣的路徑包含。

首先說明下OHC中一條邊被K中最優(yōu)4-節(jié)點路徑包含的情況。設(shè)e是OHC中一條邊，e被K上（n-2）（n-3）/2個K包含，由文獻(xiàn)［11］可知，至少有（n-2）（n-3）/6個K，在每個K內(nèi)e被5條最優(yōu)4-節(jié)點路徑包含；又有（n-2）（n-3）/6個K，在每個K內(nèi)e被3條最優(yōu)4-節(jié)點路徑包含；在其余每個K內(nèi)，e被1條最優(yōu)4-節(jié)點路徑包含。考慮第1種最壞情況，假設(shè)e被5條最優(yōu)4-節(jié)點路徑包含的K的數(shù)量為0，即存在（n-2）（n-3）/3個K，e在每個K內(nèi)被3條最優(yōu)4-節(jié)點路徑包含，對于剩余的（n-2）（n-3）/6個K，e在每個K內(nèi)被1條最優(yōu)4-節(jié)點路徑包含。那么平均情況下，e被一個K中2+1/3=7/3（>2）條最優(yōu)4-節(jié)點路徑包含。已知一個K有6條最優(yōu)4-節(jié)點路徑，因此e被K中1條最優(yōu)4-節(jié)點路徑包含的概率為7/18（>1/3）。

對第1種最壞情況松弛，變?yōu)榈?種最壞情況。即假設(shè)e分別在（n-2）（n-3）/6個K內(nèi)被5條和1條最優(yōu)4-節(jié)點路徑包含。同理可以證明，e將被一個K中一半以上的最優(yōu)4-節(jié)點路徑包含（即e在K內(nèi)被任意一條最優(yōu)4-節(jié)點路徑包含的概率大于等于1/2）。根據(jù)以上結(jié)論，下面證明定理1。

證明首先給出說明，e：OHC中一條邊；K（i≥5）：K上包含e的一個K。

對于第1種最壞情況，當(dāng)i=5時，K包含5個K。5個K一共包含30條最優(yōu)4-節(jié)點路徑，并且有7×30/18條以上的最優(yōu)4-節(jié)點路徑包含e。

每條最優(yōu)4-節(jié)點路徑都有可能構(gòu)成最優(yōu)5-節(jié)點路徑，因此每條最優(yōu)4-節(jié)點路徑等概率地被每條最優(yōu)5-節(jié)點路徑包含。從30條最優(yōu)4-節(jié)點路徑中選取10條生成K內(nèi)最優(yōu)5-節(jié)點路徑，有7×10/18條以上的最優(yōu)5-節(jié)點路徑包含e。因此，e被7×10/18=35/9（>3）條以上的最優(yōu)5-節(jié)點路徑包含。

同理，當(dāng)i>5時，可以證明e被K內(nèi)7i（i-1）/36條以上最優(yōu)i-節(jié)點路徑包含。當(dāng)i=n時，e被7n（n-1）/36條以上最優(yōu)n-節(jié)點路徑包含。

對于第2種最壞情況，同理可以證明，e被K內(nèi)i（i-1）/4條或以上最優(yōu)i-節(jié)點路徑包含。當(dāng)i=n時，e被n（n-1）/4條或以上最優(yōu)n-節(jié)點路徑包含。（證畢）

K上一條邊被C（n-2，i-2）（C是組合數(shù)符號）個K包含，每個K有i（i-1）/2條最優(yōu)i-節(jié)點路徑。根據(jù)定理1可知，當(dāng)采用最優(yōu)i-節(jié)點路徑計算邊的頻率時，OHC中邊的頻率大于LB=7i（i-1）×C（n-2，i-2）/36或大于LB=i（i-1）×C（n-2，i-2）/4。

采用有10個節(jié)點的小型TSP算例來驗證定理1。首先計算出OHC，然后計算出所有的最優(yōu)i-節(jié)點路徑（4≤i≤10），最后從每種最優(yōu)i-節(jié)點路徑中枚舉出OHC中各邊的頻率，結(jié)果如表1所示。表1中列出了采用每種最優(yōu)i-節(jié)點路徑計算出的OHC中邊的兩個最小頻率，并對比了兩個最小理論頻率LB和LB。可以看出，對應(yīng)每種最優(yōu)i-節(jié)點路徑，OHC中邊的最小頻率均大于LB。雖然OHC中邊的最小頻率小于LB，但第2最小頻率值均顯著大于LB，說明OHC中絕大多數(shù)邊的頻率大于LB。對于稍大規(guī)模TSP算例的實驗結(jié)果表明^［9-10］，OHC中邊的最小頻率大于LB，TSP規(guī)模越大，最小頻率與LB的差距越大。

對于K（n≥4）上MST中一條邊，可以證明它在任意一個K（i≥4）的MST上。如果從每個MST

4算例分析

通過TSPLIB^［12］中一些TSP算例，驗證了所提方法和定理1。已知每個算例的一個OHC^［13］，從K中分別隨機選取包含OHC中每條邊的1 000個K（4≤i≤7），通過枚舉法計算出所包含的最優(yōu)i-節(jié)點路徑，然后再從中計算出OHC中邊的頻率f，采用p=2f/［1 000i（i-1）］表示一條邊被最優(yōu)i-節(jié)點路徑包含的概率。當(dāng)i≥8時，為節(jié)省時間，為每條邊選取200個K，其他計算過程相同。表2給出了OHC中邊被最優(yōu)路徑包含的最小概率和平均概率（按照算例規(guī)模從小到大排列）。第1列為TSP名稱，字母符號后的數(shù)字代表節(jié)點數(shù)，以后各列代表采用最優(yōu)i-節(jié)點路徑計算的概率p（4≤i≤8）（保留到小數(shù)點后兩位）。每個算例給出兩個實驗數(shù)據(jù)，前一個數(shù)據(jù)代表OHC中邊的最小概率，斜杠后的數(shù)據(jù)代表OHC中邊的平均概率。

從表2可以看出，無論采用哪種最優(yōu)i-節(jié)點路徑，OHC中邊的最小概率均大于定理1中的第1個理論最小值7/18=0.389；除了kroA100，OHC中邊的最小概率均大于第2個理論最小值0.5。并且隨著i的增加，大T+xHRXA9EU9OkQj55X46xw==多數(shù)算例的最小概率也逐漸變大。與最小概率相比，OHC中邊的平均概率明顯變大，說明大多數(shù)OHC中邊被大量最優(yōu)i-節(jié)點路徑包含。而且平均概率隨著i的增加逐漸變大，說明OHC中多數(shù)邊被更多比例且更長的最優(yōu)i-節(jié)點路徑包含。無論對于最小頻率還是平均頻率，都隨著TSP規(guī)模的增加而逐漸變大，這種現(xiàn)象已經(jīng)根據(jù)最優(yōu)4-節(jié)點路徑進(jìn)行了證明^［14］。因此，對于每一列的最小概率和平均概率，均有隨TSP規(guī)模變大而上漲的趨勢。

由于邊的權(quán)值并不遵循一定的規(guī)律，這些算例的圖結(jié)構(gòu)各不相同，所包含的OHC結(jié)構(gòu)也不一樣。6個算例（kroA100，bier127，ch150，d198，a280，rat575）的OHC結(jié)構(gòu)如圖1中虛線所示。可以看出，有些OHC中邊的權(quán)值比較接近，比如kroA100和a280；但有些OHC中邊的權(quán)值差別很大，比如bier127和d198。并且，很多邊有時位于某些點集對應(yīng)的凸包上，有時又位于另外一些點集對應(yīng)的凸包內(nèi)部。因此，很難根據(jù)邊的權(quán)值判斷一條邊是否屬于OHC。當(dāng)采用最優(yōu)i-節(jié)點路徑把權(quán)重圖轉(zhuǎn)化為頻率圖后，無論OHC中邊的權(quán)值大小如何，它們被最優(yōu)i-節(jié)點路徑包含的概率均很大，幾乎不受邊的權(quán)值的影響。

圖2用黑實線顯示了采用最優(yōu)4-節(jié)點路徑計算的算例bier127的 OHC中最小概率的邊。可見該邊位于圖的內(nèi)部，與其他OHC邊相比，該邊處于較多點集對應(yīng)的凸包內(nèi)部，雖然其權(quán)值并不很大，但邊的頻率偏小。然而，由于該邊屬于OHC，與一般邊相比，它仍然位于很多點集對應(yīng)的凸包上，因此被大量的最優(yōu)4-節(jié)點路徑包含。表2中顯示，該邊被最優(yōu)4-節(jié)點路徑包含的最小概率為0.65。

另外，對于規(guī)模相近的不同TSP，平均概率接近相等，最小概率少許不同。說明OHC中邊整體上會被大量的最優(yōu)i-節(jié)點路徑包含，但個別邊會有區(qū)別。

由于TSP變化多樣，OHC中某些邊在圖中出現(xiàn)的位置對最小概率有一定的影響。K上任意兩點（一條邊）位于C（n-2，i-2）個i-節(jié)點集合內(nèi)，如果連接這兩點的邊位于較多點集對應(yīng)的凸包上，該邊被最優(yōu)

i-節(jié)點路徑包含的概率會比較大。反之，該邊被最優(yōu)i-節(jié)點路徑包含的概率會變小，但不會偏離定理1。

5結(jié)語

針對完全圖上的兩個問題MST和TSP，分別定義了兩類特殊圖，與其上的交運算構(gòu)成半群，分析了生成的頻率圖中邊的頻率性質(zhì)。對于MST中的邊，它們的頻率一直保持最大；對于OHC中的邊，它們的頻率存在下界。由于多數(shù)邊大概率被OP包含，因此大于大部分其他邊的頻率。通過實例驗證了OHC中邊的頻率性質(zhì)，并分析了影響邊的頻率的因素。當(dāng)把TSP權(quán)重圖轉(zhuǎn)化為頻率圖時，相當(dāng)于把求解OHC這樣一個函數(shù)極值問題變成一個泛函的極值問題，這個泛函就是邊的頻率，根據(jù)邊的頻率求出的最優(yōu)邊組合就是OHC。原則上K中一個OHC對應(yīng)每條邊的無窮多組賦值，未來將研究這個泛函極值的求解策略和在TSP算法設(shè)計中的應(yīng)用。

參考文獻(xiàn)：

［1］CORMEN T H，LEISERSON C E，RIVEST R L，et al. Introduction to algorithms［M］.2nd ed. Cambridge： MIT Press， 2006： 636-639.

［2］程亞南， 王曉峰， 劉凇佐， 等. 一種求解旅行商問題的信息傳播算法［J］. 鄭州大學(xué)學(xué)報（理學(xué)版）， 2022， 54（3）： 52-58.

CHENG Y N， WANG X F， LIU S Z， et al. An information propagation algorithm for solving traveling salesman problem［J］. Journal of Zhengzhou university （natural science edition）， 2022， 54（3）： 52-58.

［3］KARP R M. On the computational complexity of combinatorial problems［J］. Networks， 1975， 5（1）： 45-68.

［4］KARPINSKI M， LAMPIS M， SCHMIED R. New inapproximability bounds for TSP［J］. Journal of computer and system sciences， 2015， 81（8）： 1665-1677.

［5］BJURKLUND A， HUSFELDT T， KASKI P， et al. The traveling salesman problem in bounded degree graphs［J］. ACM transactions on algorithms， 2012， 8（2）： 1-13.

［6］XIAO M Y， NAGAMOCHI H. An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure［J］. Algorithmica， 2016， 74（2）： 713-741.

［7］JONKER R， VOLGENANT T. Nonoptimal edges for the symmetric traveling salesman problem［J］. Operations research， 1984， 32（4）： 837-846.

［8］HOUGARDY S， SCHROEDER R T. Edge elimination in TSP instances［C］∥ International Workshop on Graph-Theoretic Concepts in Computer Science. Cham： Springer International Publishing， 2014： 275-286.

［9］WANG Y， REMMEL J B. A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals［J］. Journal of graph algorithms and applications， 2016， 20（2）： 411-434.

［10］WANG Y， REMMEL J. A method to compute the sparse graphs for traveling salesman problem based on frequency quadrilaterals［C］∥International Workshop on Frontiers in Algorithmics. Cham： Springer International Publishing，2018： 286-299.

［11］WANG Y. The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals［C］∥National Conference of Theoretical Computer Science. Berlin： Springer Press， 2022： 77-95.

［12］REINHELT G. TSPLIB： a library of sample instances for the TSP （and related problems） from various sources and of various types［EB/OL］. ［2023-06-13］.http：∥comopt.ifi.uni-heidelberg.de/software/TSPLIB95.

［13］MITTELMANN H. Neos server for concorde［EB/OL］.［2023-06-13］. https：∥neos-server.org/neos/solvers/co： concorde/TSP.

［14］WANG Y. Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals［J］. Journal of optimization theory and applications， 2019， 181（2）： 671-683.