旅行商問題最小搜索空間研究

　　摘要： TSP問題之所以復(fù)雜，一個(gè)很重要的方面就是搜索空間中有大量的冗余環(huán)路，降低了搜索的效率。通過對普通搜索空間中冗余環(huán)路表達(dá)出現(xiàn)原因的分析和研究，構(gòu)造出了新的搜索空間－最小搜索空間（LSS），在最小搜索空間中每個(gè)環(huán)路的表達(dá)形式是唯一的，從而消除了環(huán)路表達(dá)冗余現(xiàn)象，使搜索得以在只相當(dāng)于原搜索空間2N分之一（N為結(jié)點(diǎn)數(shù)目）的空間內(nèi)進(jìn)行。然后進(jìn)一步的對最小搜索空間的構(gòu)造展開研究，實(shí)現(xiàn)了基于問題規(guī)模遞推的最小搜索空間獲得方式，掃清了最小搜索空間的應(yīng)用障礙。在TSP問題求取最優(yōu)解的確定性算法中與常用的Uniformcost Search算法進(jìn)行了對比，效率相應(yīng)提高了2N倍。
　　關(guān)鍵詞： 最優(yōu)化；搜索空間；冗余環(huán)路；空間結(jié)構(gòu)；旅行商問題（TSP）
　　中圖分類號：O157.6 文獻(xiàn)標(biāo)示碼： A
　　
　　一、引 言
　　
　　旅行商問題（Traveling Salesman Prob