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

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