|
論最優(yōu)路徑——走遍全中國摘要
（作者未知） 2010/12/13
摘要
本文討論的是一個所謂“最優(yōu)路徑”問題，乍看之下，此問題與“旅行商問題”極為相似，但在仔細(xì)研究過后，我們發(fā)現(xiàn)兩個問題存在本質(zhì)上的差別。“旅行商問題”更接近于一個理想化的數(shù)學(xué)游戲，而本題更多的涉及到實際情況。再三考慮之下，我們決定拋棄“旅行商問題”的經(jīng)典解題思路，用其他方法解決問題。
在查閱了大量真實數(shù)據(jù)之后，我們發(fā)現(xiàn)本問題更接近于一個數(shù)據(jù)處理問題。于是，我們嘗試用MATLAB和編程來輔助我們處理數(shù)據(jù)，我們建立了歷程和票價的矩陣，并通過自編的程序處理數(shù)據(jù)以獲得最優(yōu)路徑，最優(yōu)票價。最后，我們通過引用“權(quán)值”來平衡路程和票價間的關(guān)系，這使得我們的模型更接近實際情況。在第一個建模完成后，我們試圖更深入了解關(guān)于“最優(yōu)路徑”問題的相關(guān)信息。通過圖書館、網(wǎng)絡(luò)等媒介搜集了大量信息后，我們發(fā)現(xiàn)，“遺傳算法”方面已經(jīng)有了一套完整的關(guān)于解決“最優(yōu)路徑”問題的方案。我們將此方案引入，并進行簡單修改，使其更適合解決本題。我們的假設(shè) 起到了“單親演化過程”在“遺傳算法”中提高初始群體適應(yīng)度的作用。該假設(shè)又減少了基因庫中元素的數(shù)量，使計算量大大降低。之后，再利用“群體演化過程”，在保證了算法快速收斂的同時也注重搜索空間的全局性。最后，引入收斂準(zhǔn)則。當(dāng)滿足收斂準(zhǔn)則時，運算終止，輸出優(yōu)化結(jié)果。
本文中的假設(shè)不僅使運算簡化，且符合實際情況。其中又大量引入真實數(shù)據(jù)，使模型更具實際意義。
一、 問題的重述
走遍全中國
周游先生退休后想到各地旅游。計劃走遍全國的省會城市、直轄市、香港、澳門、臺北。請你為他按下面要求制定出行方案：
1．按地理位置（經(jīng)緯度）設(shè)計最短路旅行方案；
2．如果2010年5月1日周先生從哈爾濱市出發(fā)，每個城市停留3天，可選擇航空、鐵路（快車臥鋪或動車），設(shè)計最經(jīng)濟的旅行互聯(lián)網(wǎng)上訂票方案；
3．要綜合考慮省錢、省時又方便，設(shè)定你的評價準(zhǔn)則，建立數(shù)學(xué)模型，修訂你的方案；
......
附件下載：點擊論文吧下載閱讀全文
|