Can you summarize the following document?
        
  

  可以用無向加權圖來對TSP建模,則城市是圖的頂點,道路是圖的邊,道路的距離就是該邊的長度。它是起點和終點都在一個特定頂點,訪問每個頂點恰好一次的最小化問題。通常,該模型是一個完全圖(即每對頂點由一條邊連線)。如果兩個城市之間不存在路徑,則增加一條非常長的邊就可以完成圖,而不影響計算最優迴路。

  在"對稱TSP問題"中,兩座城市之間來回的距離是相等的,形成一個無向圖。這種對稱性將解的數量減少了一半。在"非對稱TSP問題"中,可能不是雙向的路徑都存在,或是來回的距離不同,形成了有向圖。交通事故、單行道和出發與到達某些城市機票價格不同等都是打破這種對稱性的例子。

  單鑽頭的運動可以看成是典型的TSP問題。TSP可以用整數線性規劃來形式化。 用數字 0,..., "n" 標記這些城市(打孔位置),並定義:  對於 "i" = 0,..., "n",令 formula_2 為一人工變數,最後把 formula_3 作為從城市 "i" 到 "j" 的距離。那麼TSP可以寫成下面的整數線性規劃問題:  第一組等式要求每個城市都能另一個城市前來,而第二組等式要求每個城市都能出發。最後的約束迫使覆蓋所有城市的路徑只有一條,而不是兩條或者多條分散的路徑在一起覆蓋的。要證明這一點,下面會去證 (1)每個可行解包含只有一條封閉城市序列,以及(2)對於每條覆蓋所有城市的單獨路徑,虛擬變數 formula_2 有值可以滿足約束。  證明可行解中的每個子迴路經過0號城市(注意到等式保證了只有一條這樣的路徑),就能證明所有可行解只包含一個封閉城市序列。對於若我們對所有 formula_6 對應的不等式求和的話,對 "k" 步不經過0號城市的任何子迴路,我們得到:  這構成矛盾。  必須證明對每個覆蓋所有城市的單獨迴路,虛擬變數 formula_2 有值可以滿足約束。  為了不失一般性,定義起始點為0號城市。如果在第 "t" 步訪問城市 "i" 後 ("i", "t" = 1, 2,..., n) 選取 formula_9。則  由於 formula_2 不大於 "n" 而 formula_12 不小於1;因此,每當 formula_13 時滿足約束。對於 formula_6,我們有:  滿足約束。
行商問題(最短路徑問題)(英語:travelling salesman problem, TSP)是這樣一個問題:給定一系列城市和每對城市之間的距離,求解訪問每一座城市一次並回到起始城市的最短迴路。它是組合優化中的一個NP困難問題,在運籌學和理論電腦科學中非常重要。 TSP是旅行購買者問題與車輛路徑問題的一種特殊情況。