1、1，()，繪畫(huà)理論，2，2.5旅行推銷員問(wèn)題1。旅行推銷員問(wèn)題：對(duì)正全圖g，找到最短的g循環(huán)。(將歐拉回路與h回路區(qū)分開(kāi)來(lái))2。求解算法：分支劃分方法分支劃分方法是用更好的方法進(jìn)行搜索的準(zhǔn)枚舉方法，本質(zhì)上是按字母順序列出所有可能的情況并結(jié)合修剪(過(guò)濾)的方法。示例A、B、C、D和E三個(gè)徐璐其他字母組成的完整字符串，按字母順序排序：ABC、Abd、Abe、ACD、ace、ade、BCD、bde、CDE、3、分支分割方法的初始步驟：1。按權(quán)重對(duì)所有邊進(jìn)行較小的排序；2.取前n邊為s，并設(shè)定d0:=。(d0是所調(diào)查h電路中最短的長(zhǎng)度)重復(fù)步驟：3。S配置h回路并配置其長(zhǎng)度d(S)d0時(shí)，d0:=d(

2、S)。如果跳過(guò)低于當(dāng)前d0的后續(xù)方案，則使用第一組未調(diào)查的邊作為s返回3。檢查所有情況時(shí)，d0是最短的h循環(huán)長(zhǎng)度，其值為s是問(wèn)題的解決方案。(將一個(gè)邊緣視為一個(gè)字符，并在步驟1中獲得了每個(gè)字符之間的先后關(guān)系。對(duì)于長(zhǎng)度為n且文字徐璐為其他所有字符串，此算法按字母順序逐個(gè)檢查每個(gè)字符串。4，1)邊按權(quán)重排序(小值到大值)，d0:=邊：a35 a24 a15 a14 a12 a13 a34 a23 a45 a25加權(quán)：3 4 9 10 11 13 16 20，5，邊：a35 a24S2: a35 a24 a15 a14 a13，鄭智薰h循環(huán)，d(S2)=30；S3: a35 a24 a15 a14

3、a34，鄭智薰h循環(huán)，d(S3)=31；S4: a35 a24 a15 a14 a23，H電路，d0:=33S5: a35 a24 a15 a12 a13，鄭智薰h循環(huán)，d(S5)=31；S6: a35 a24 a15 a12 a34，H循環(huán)，d(S6)=32，d0:=32S7: a35 a24 a15 a13 a34，鄭智薰h循環(huán)，d(S6)=32；S8: a35 a24 a14 a12 a13，鄭智薰h循環(huán)，d(S6)=36；如果繼續(xù)，則結(jié)果組長(zhǎng)度將小于S8，從而可以結(jié)束計(jì)算。6，因此最佳解決方案是S6，長(zhǎng)度為32。計(jì)算要把握兩個(gè)要點(diǎn)。1.按字母順序逐個(gè)調(diào)查每個(gè)變體。2.每次檢查一組邊后，

4、必須考慮是否可以作為過(guò)濾條件(當(dāng)前d0值)跳過(guò)某些不必要的檢查。因?yàn)槲覀儾豢紤]比當(dāng)前d0值差的情況。7，4。近似算法“便宜”算法分支和邊界法可以得到售貨員問(wèn)題的精確最優(yōu)解，但計(jì)算復(fù)雜度為O(n！)，因此需要尋找大問(wèn)題的近似算法。使用近似算法通常需要添加一些限制以提高計(jì)算速度和近似級(jí)別。(1) G是正法線圖。(2)在兩條邊之和大于第三條邊的圖中，由任意三個(gè)點(diǎn)組成的三角形。8，解決想法：給v1自己的環(huán)，得到第一個(gè)環(huán)。以后重復(fù)該過(guò)程，找到與已獲得回路最近的點(diǎn)，然后將其插入回路?；芈吠獠繘](méi)有節(jié)點(diǎn)時(shí)終止。插入方式：將插入點(diǎn)設(shè)定為j，并提供兩個(gè)選項(xiàng)： (1)加入(j，t1)和(j，t)，刪除(t，t1)。

5、(2)添加(j，t2)和(j，t)，刪除(t，t2)。選擇并插入回路長(zhǎng)度較小的方法。9，是，10，11，2.6最短路徑1。最短路徑1。最短路徑問(wèn)題權(quán)重圖將權(quán)重視為邊長(zhǎng)，指定兩個(gè)節(jié)點(diǎn)之間的最短路徑和路徑。在正權(quán)重圖中，對(duì)于V1到每個(gè)點(diǎn)的最短路徑正權(quán)重圖g，如果l是點(diǎn)到點(diǎn)vt的最短路，l通過(guò)點(diǎn)VJ，l到VJ到vt的部分路徑為l，則l是VJ到vt的最短短路。(否則，路徑(vsvj) L 比L短且矛盾)，12，2。正權(quán)也最短路徑問(wèn)題解決Dijkstra算法問(wèn)題：尋找從起點(diǎn)v1到其他點(diǎn)的最短路徑。記號(hào)：s表示最短路的一組節(jié)點(diǎn)，e表示s中每個(gè)點(diǎn)最短路的一組邊。在算法中，d(i)(在點(diǎn)VI中稱為標(biāo)簽)表示起

6、點(diǎn)v1到VI的長(zhǎng)度，d(i)表示VI在s中時(shí)v1到VI的最短長(zhǎng)度。，13，Dijkstra算法：1)允許d (1) :=0，s :=1，k :=1，e :=；D (I)=w11，I=2，3，n .(如果圖形中沒(méi)有邊(vi，vj)，則在wij=) 2) s以外的所有點(diǎn)處尋找最小標(biāo)示點(diǎn)。d(k0)=min d(j): VJ不在s中；(3) s :=sk0，k :=k0，e :=eek0(到值d(k0)的邊)，然后修改與vk0相鄰的點(diǎn)的標(biāo)簽。如果d(j):=min d(j)，d(k) wkj，jS |S|=n，則迭代結(jié)束。否則，請(qǐng)返回步驟2。(注意理解jS時(shí)間標(biāo)簽d(j)的含義)，14，證明此算法的

7、理解和算法的正確性：(實(shí)線表示圖中的一條邊，虛線表示由多條邊組成的一條路)，查找從15，v1到另一點(diǎn)的最短路徑。d(v1)=0時(shí)(表示s的紅點(diǎn)集合)，16，3。權(quán)重為1時(shí)，最短路徑故障診斷是正權(quán)重，因此可以直接使用Dijkstra方法。但是，在這種情況下，Dijkstra算法可能會(huì)簡(jiǎn)化。每個(gè)迭代都具有要包含在s中的相同節(jié)點(diǎn)標(biāo)簽。修改所有直接后綴節(jié)點(diǎn)的標(biāo)簽(全部相同)，以便下次將所有節(jié)點(diǎn)導(dǎo)入到s中。即可從workspace頁(yè)面中移除物件。也就是說(shuō)，當(dāng)每個(gè)節(jié)點(diǎn)進(jìn)入s時(shí)，所有直接后繼節(jié)點(diǎn)都將成為下一個(gè)進(jìn)入s的所有節(jié)點(diǎn)。重復(fù)|S|=n。17，v1到其他點(diǎn)的最短路徑的范例。如果D(v1)=0，則(S):18，2。當(dāng)權(quán)重為負(fù)值時(shí)，解決最短路問(wèn)題的Ford算法中存在負(fù)值時(shí)，Dijkstra算法將失敗。-為什么？)圖沒(méi)有負(fù)循環(huán)的情況下，可以解決最短路徑問(wèn)題。Ford算法迭代逼近，得到最優(yōu)解。在算法中，在第k次迭代后，d(i)表示從起點(diǎn)v1到VI的一條道路的長(zhǎng)度，d(i)等于或小于邊數(shù)不超過(guò)k的最短路長(zhǎng)度。因此，算法的迭代次數(shù)不超過(guò)n。19，F(xiàn)ord算法1)