1
銆婄畻娉曡璁′笌鍒嗘瀽銆嬪疄楠屾姤鍛?/p>
瀛?/p>
鍙凤細
濮?/p>
鍚嶏細
鏃?/p>
鏈燂細
寰?/p>
鍒嗭細
涓�銆佸疄楠屽唴瀹癸細
TSP
闂銆?/p>
浜屻�佹墍鐢ㄧ畻娉曠殑鍩烘湰鎬濇兂鍙婂鏉傚害鍒嗘瀽锛?/p>
1
銆?/p>
铔姏娉?/p>
1
锛?/p>
鍩烘湰鎬濇兂
鎵惧嚭鎵�鏈夊彲鑳界殑鏃呰璺嚎锛?/p>
鍗充互娆¤�冭檻鍥句腑鎵�鏈夐《鐐圭殑鍏ㄦ帓鍒楋紝
浠庝腑閫?/p>
鍙栬矾寰勯暱搴︽渶鐭殑鍝堝瘑椤垮洖璺紙涔熺О涓虹畝鍗曞洖璺級
銆?/p>
2
锛?/p>
澶嶆潅搴﹀垎鏋?/p>
铔姏娉曟眰瑙?/p>
TSP
闂蹇呴』渚濇鑰冨療椤剁偣闆嗗悎鐨勬墍鏈夊叏鎺掑垪锛屼粠涓壘鍑?/p>
璺緞闀垮害鏈�鐭殑绠�鍗曞洖璺紝鍥犳锛屽叾鏃堕棿涓嬬晫鏄?/p>
(n!)
銆?/p>
2
銆?/p>
鍔ㄦ�佽鍒掓硶
1
锛?/p>
鍩烘湰鎬濇兂
TSP
闂婊¤冻鏈�浼樻�у師鐞嗐�傚浜庡浘
G=(V
,E)
锛屽亣璁句粠椤剁偣
i
鍑哄彂锛屼护
V
鈥?/p>
=V-I
锛屽垯
d(i,V
鈥?/p>
)
琛ㄧず浠庨《鐐?/p>
i
鍑哄彂缁忚繃
V
鈥欎腑鍚勪釜椤剁偣涓�娆′笖浠呬竴娆★紝鏈�
鍚庡洖鍒板嚭鍙戠偣
i
鐨勬渶鐭矾寰勯暱搴︺�傛樉鐒跺垵濮嬪瓙闂涓?/p>
d(k,{ })
锛屽嵆浠庨《鐐?/p>
i
鍑?/p>
鍙戝彧缁忚繃椤剁偣
k
鍥炲埌椤剁偣
i
銆傜幇鍦ㄨ�冭檻鍘熼棶棰樼殑涓�閮ㄥ垎锛?/p>
d(k,V
鈥?/p>
-{k})
琛ㄧず浠?/p>
椤剁偣
k
鍑哄彂缁忚繃
V
鈥?/p>
-{k}
涓悇涓《鐐逛竴娆′笖浠呬竴娆★紝鏈�鍚庡洖鍒板嚭鍙戠偣
i
鐨勬渶
鐭矾寰勯暱搴︼紝鍒欙細
d(k,{ })=Cki
d(i,V
鈥?/p>
)=min{Cik+d(k,V
鈥?/p>
-{k})}(k
鈭?/p>
V
鈥?/p>
)
2
锛?/p>
澶嶆潅搴﹀垎鏋?/p>
绠楁硶闇�瑕佸椤剁偣闆嗗悎
{1,2
锛屸�︼紝
n-1}
鐨勬瘡涓�涓瓙闆嗚繘琛屾搷浣滐紝鍥犳锛屾椂
闂村鏉傛�т负惟
(2n)
銆?/p>
3
銆?/p>
鍥炴函娉?/p>