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

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

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

中圖分類號(hào)： TP301.6

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

文章編號(hào)： 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è)計(jì)中，比如最小生成樹、最大網(wǎng)絡(luò)流、圖染色、旅行商問題等。它們有的屬于P問題，有的屬于NP問題，圖上NP問題及其求解方法是理論計(jì)算機(jī)和運(yùn)籌學(xué)研究的焦點(diǎn)之一。

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

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

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

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

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

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

1兩類特殊圖及其交運(yùn)算

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

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

定義1完全圖上的MST：任給一個(gè)包含k個(gè)節(jié)點(diǎn)v（1≤i≤k）的完全賦權(quán)圖K（V，E，W），連接圖中所有節(jié)點(diǎn)且邊上權(quán)值和最小的生成樹稱為圖K的最小生成樹，記為MST。其中點(diǎn)集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ⁿ個(gè)子圖，除去空?qǐng)D和單點(diǎn)圖，其余每個(gè)完全子圖均有一個(gè)MST，因此有2ⁿ-n-1個(gè)MST，所有MST構(gòu)成集合

S

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

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

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

P=

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

1.2MST和OP上的交運(yùn)算

下面定義集合

S

T

和O

P

中元素的交運(yùn)算。為方便描述，兩個(gè)集合及其圖元素統(tǒng)一用符號(hào)

G

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

G上二元交運(yùn)算定義如下。

定義3

圖集合G上的二元交運(yùn)算：給定集合

G

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

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

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

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

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

G

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

G

中元素的二元運(yùn)算遵循的運(yùn)算定律為

GG=G，（1）

GG=GG，（2）

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

G=，（4）

GK=G。（5）

無論對(duì)于

S

T

還是O

P

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

〈

ST

，〉和〈O

P

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

=〈G

，〉。

2基于半群的頻率圖

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

定義4

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

〈G

，〉，給定G

中一個(gè)圖G，對(duì)于

G

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

定義5頻率圖（frequency graph，F(xiàn)G）：對(duì)于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)的圖中枚舉出來后，所有邊和邊上的頻率形成一個(gè)頻率圖，記為FG。

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

。對(duì)于MST或OP，G

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

=

〈G

，〉。對(duì)于其中每個(gè)圖G∈G

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

FG

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

到FG

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

的一種變換。

半群

=〈G

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

中兩個(gè)圖交運(yùn)算的結(jié)果衡量圖之間的接近程度，對(duì)于兩個(gè)圖G和G，

它們的運(yùn)算結(jié)果

G=GG越大，這兩個(gè)圖越靠近，其中

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

對(duì)于K

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

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

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

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

對(duì)于MST和OP，G

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

G

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

=〈G

，〉，對(duì)于其中一個(gè)圖G，

G

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

=〈G

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

定義6

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

=〈G

，〉，對(duì)于一個(gè)圖G∈G

，G

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

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

G

/G。

〈｛G｝，〉的陪集代表對(duì)G

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

給定一個(gè)半群=〈G

，〉和G∈G

，假設(shè)G

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

G

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

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

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

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

G

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

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

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

F

G

中的一個(gè)元素。

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

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

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

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

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

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

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

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

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

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

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

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

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

4算例分析

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

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

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

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

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

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

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

5結(jié)語(yǔ)

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