【教程】大學(xué)競(jìng)賽數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)行遍性問(wèn)題ppt-預(yù)覽頁(yè)
【正文】 一次的權(quán)最小的閉通路稱為 最佳推銷(xiāo)員回路 ． 一般說(shuō)來(lái)，最佳哈密爾頓圈不一定是最佳推銷(xiāo)員回路，同樣最佳推銷(xiāo)員回路也不一定是最佳哈密爾頓圈． H回路，長(zhǎng) 22 最佳推銷(xiāo)員回路，長(zhǎng) 4 定理１ 在加權(quán)圖 G =( V , E ) 中，若對(duì)任意 x,y ,z ? V ， z ? x, z ? y,都有 w(x ,y) ? w(x ,z ) + w(z ,y) ，則圖 G 的最佳 H 圈也是最佳推銷(xiāo)員回路． 最佳推銷(xiāo)員回路問(wèn)題可轉(zhuǎn)化為最佳 H 圈問(wèn)題．方法是由給定的圖 G =( V , E ) 構(gòu)造一個(gè)以 V 為頂點(diǎn)集的完備圖 G ’ =( V , E ’ ) ， E ’的每條邊 ( x,y ) 的權(quán)等于頂點(diǎn) x 與 y 在圖中最短路的權(quán)．即： ? x,y ? E ’ , w(x ,y) = m i nd G ( x,y ) 定理２ 加權(quán)圖 G 的最佳推銷(xiāo)員回路的權(quán)與 G ’ 的最佳 H 圈的權(quán)相同． 推銷(xiāo)員問(wèn)題近似算法： 二邊逐次修正法 ： ( 1 ) 任取初始 H 圈 : C 0 =v 1 ,v 2 , … ,v i , , … , v j , … , v n , v 1 ( 2) 對(duì)所有的 i ,j ， 1 i+ 1 j n, 若 w(v i , v j ) + w(v i+ 1 ,v j+ 1 ) w(v i ,v i+ 1 ) + w(v j ,v j+ 1 ) 則在 C 0 中刪去邊 ( v i ,v i+ 1 ) 和 ( v j ,v j+ 1 ) 而加入邊 ( v i , v j ) 和 ( v i+ 1 ,v j+ 1 ) ，形成 新的 H 圈 C ， 即 C= v 1 , v 2 , … ,v i , v j , v j 1 , … , v i+ 1 ,v j+ 1 , … , v n ,v 1 ( 3 ) 對(duì) C 重復(fù)步驟 ( 2 ) ，直到條件不滿足為止，最后得到的 C 即為所求． 例 對(duì)以下完備圖 ， 用二邊逐次修正法求較優(yōu) H圈 ． 返回
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1