回溯問(wèn)題適合于解由向量的形式來(lái)構(gòu)成的，這個(gè)向量空間中使用搜索的方法進(jìn)行搜索，搜索使用寬度優(yōu)先的方法。貨郎問(wèn)題又名旅行商問(wèn)題，但其實(shí)更多教科書(shū)中更通用的叫法叫旅行商問(wèn)題，下面來(lái)對(duì)旅行商問(wèn)題使用回溯算法證明。

一、問(wèn)題描述

有n個(gè)城市，已知任兩個(gè)城市之間的距離，求一條每個(gè)城市恰好經(jīng)過(guò)一次的回路，使得總長(zhǎng)度最小 。

分析：
有n個(gè)城市，城市與城市之前有距離的，任意兩個(gè)城市之間的距離是已知的，現(xiàn)在需要找一條回路，經(jīng)過(guò)每一個(gè)城市1次，使得總長(zhǎng)度最小，就相當(dāng)于這個(gè)貨郎在路途，或者旅行商的行路，遍歷所有的城市去各個(gè)城市走一趟，但是城市不能重復(fù)，所以怎么走下來(lái)才能夠使得總長(zhǎng)度達(dá)到最小。

其實(shí)相當(dāng)于把這些城市做一個(gè)排列，第一個(gè)城市指向k1所指向的城市，由城市k1走向城市k2，一直往下走，走到kn以后再回到k1形成一個(gè)閉環(huán)

二、數(shù)學(xué)建模

數(shù)學(xué)表達(dá)式中的C k1到C k2，這兩個(gè)城市的距離用d來(lái)表示，走到最后一個(gè)城市再倒回來(lái)(從C kn到C k1)，這個(gè)距離達(dá)到最小，就是我們要做的事情。

這個(gè)問(wèn)題是有選擇的，一定程度上講，TSP也是優(yōu)化問(wèn)題，只要是涉及到有選擇，選擇的不同導(dǎo)致結(jié)果的不同，結(jié)果的不同要想法設(shè)法找出最好的選擇，不管是調(diào)度問(wèn)題、背包的裝法問(wèn)題還是這個(gè)城市排列的問(wèn)題，現(xiàn)代的智能優(yōu)化算法不再使用精確的解，而是找到一個(gè)近似最精確的解就可以了。

三、實(shí)例

1、傳統(tǒng)經(jīng)典做法

從第1個(gè)城市走到第2個(gè)城市，從第2個(gè)城市走到第4個(gè)城市，從第4個(gè)城市到第3個(gè)城市然后再回來(lái)。

C={1,2,3,4}
d(1,2)=5, d(1,3)=9,
d(1,4)=4, d(2,3)=13,
d(2,4)=2, d(3,4)=7

解：< 1,2,4,3 > ,
長(zhǎng)度= 5 + 2 + 7 + 9 = 23

這是其中一個(gè)解，最后的解得到的是城市的排列向量，上面原始的數(shù)據(jù)每?jī)蓚€(gè)城市之間的距離都是給出的。

2、回溯算法

假定每個(gè)城市都有連接，回溯算法的實(shí)現(xiàn)也是一種搜索，首先對(duì)于第一個(gè)城市出發(fā)，第1個(gè)城市和2，3，4城市相連，這個(gè)時(shí)候做選擇，選擇任何一條路徑往下走，走到第2個(gè)城市，又有兩種選擇：到第4個(gè)城市，或者到第3個(gè)城市。每走到一個(gè)城市就選相當(dāng)于前面已經(jīng)走過(guò)的城市就不用再選擇了，就從剩下的城市中去選。

一開(kāi)始選定任何一個(gè)出發(fā)點(diǎn)出發(fā)，接下來(lái)又n-1個(gè)城市可以去選擇，當(dāng)你走到任何一個(gè)點(diǎn)之后，接下來(lái)又有n-2個(gè)城市可以去選擇，……一直到最后只有1種選擇，就是唯一的選擇：回去。所以總的路徑有(n-1)!種，每到葉結(jié)點(diǎn)的路徑就是城市間的路徑。

表示為樹(shù)，稱之為排列樹(shù)，有(n-1)!片樹(shù)葉

其實(shí)我們要找的就是在所有的排列樹(shù)葉結(jié)點(diǎn)中去找最小的那個(gè)，所以搜索空間是相當(dāng)大的。

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-461482.html

四、總結(jié)

• 解：向量
• 搜索空間：樹(shù)，可能是n叉樹(shù)、子集樹(shù)、排列樹(shù)等等，樹(shù)的結(jié)點(diǎn)對(duì)應(yīng)于部分向量，可行解在葉結(jié)點(diǎn)
• 搜索方法：深度優(yōu)先, 寬度優(yōu)先, …
  跳越式遍歷搜索樹(shù)，找到解

到了這里，關(guān)于旅行商問(wèn)題（回溯算法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！