資源描述：
《貨郎擔(dān)問題的實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、貨郎擔(dān)問題的實現(xiàn)上機實踐要求：題目：在計算機上求解貨郎擔(dān)問題和哈密頓圖判定問題,并分析算法性能要求：1以文件方式輸入問題，你的程序首先讀入該文件，并將結(jié)果保存在你的程序采用的數(shù)據(jù)結(jié)構(gòu)中。通過編輯或者修改文件，可以改變輸入的問題。2語言不限3提交實驗報告。報告應(yīng)該包括以下內(nèi)容：a)題目b)算法c)運行情況d)測試算法性能或者改善算法性能的嘗試、分析、結(jié)果e)認(rèn)識與體會f)程序一、題目：利用分枝限界法求解貨郎擔(dān)問題二、算法：給定一個圖的代價矩陣，例如下圖，找出有最小代價的周游路線。確定解的表示形式：(X1,X2,…,Xn),各頂點分別編號1,2,…,n,Xi表
2、示第i步經(jīng)過的頂點號?！?54031275∞1730251915∞6195024∞6228710∞三、算法：ProcedureTS_reduced_matrix_LCBBBegin1輸入代價矩陣A[aij]把矩陣A歸約成A1，設(shè)約數(shù)為r1U:=∞E:＝1，X:=1^C(1):=r1L:=ΦCurrentcity(1):=1Citytrveled(1):=1While^C(E)屬于AE則beginADD(X+1)
3、;X:=X+1;parent(X):=E;currentcity(X):=jCitytraveled(X):=Citytraveled(E)∪{j}endAx:=AE把Ax的I行j列以及Ax(j,i)置成無窮大歸約Ax,得到約數(shù)rx^C(X):=^C(E)+AE((I,j))+rxend3如果L非空thenbegin4E:=Least(L)如果
4、
5、Citytraveled(E)
6、
7、=n且(currentcity(E),1)屬于AEthenbegin5ans:=E;U:=min{U,rE+AE(currentcity(E),1)}end5對活節(jié)點表中所有節(jié)點
8、，如越界則刪除end4else^C(E):=無窮大end2輸出U輸出Citytraveled(ans)end1四、三、運行情況運行環(huán)境：PII800256MB內(nèi)存。節(jié)點較少的情況下運行速度很快。五、結(jié)果正確。輸出的回路為：1、2、3、5、4、1測試算法性能或者改善算法性能的嘗試、分析、結(jié)果通過在原圖代價矩陣上增加結(jié)點的方法來測試算法性能，當(dāng)結(jié)點數(shù)N=5時運行速度很快在1秒以內(nèi)，當(dāng)N=40時，約需5秒。開始我在找代價最小的活結(jié)點，只考察了它們的代價，后來發(fā)現(xiàn)當(dāng)有多個具有相同最小代價的節(jié)點存在時，它們會依次都被展開。這樣導(dǎo)致活節(jié)點表的長度增長非?？?，為了避免這
9、種情況，我又增加了一個條件：找那些已經(jīng)使用節(jié)點數(shù)目最多的活節(jié)點。這樣不僅使速度加快同時也使得活節(jié)點表的長度不會增長得太長。這里還有一個問題：我使用的活節(jié)點表的長度定為node*node或node*node*node。不知道到底是否合適，雖然目前還沒有發(fā)現(xiàn)任何問題。內(nèi)存使用我采用動態(tài)申請，但沒有及時釋放，這只有通過關(guān)閉程序來釋放了。六、認(rèn)識與體會由于分枝限界法的時間復(fù)雜性在最壞情況下是O(n22n)，由實驗結(jié)果知，當(dāng)N增大時，所需運行時間增加很快。在這種解決NP問題的程序中，我認(rèn)為設(shè)計一種合適的算法與如何合理利用計算機資源同樣非常重要。七、程序
