【文章內(nèi)容簡介】 12303 12302 13232 13908 11169 12929 12083 11538 13547 10609 10483 10604 12650 13470 12619 12340 13162 12181 10073Elapsed time is seconds.三 回溯算法分析評價 基本狀態(tài)空間決策樹高效規(guī)劃流程及回溯算法由于問題一、二、三的模型用lingo軟件直接編程求解比較困難，因而運用回溯法，進而結(jié)合遞歸法、深度優(yōu)先搜索法并利用剪枝函數(shù)等算法求解。具體過程如下：Step1：輸入起始站A終點站B，假定A、B對應(yīng)于狀態(tài)決策樹的根，沿著決策樹，運用深度最優(yōu)算法進行搜索，記錄當(dāng)前最短時間(或最少費用)到變量time(或cost)，并且將當(dāng)前最優(yōu)路線記錄到數(shù)組luxian中；Step2：從公交線路與站點信息庫里面從頭至尾依次搜索A，搜索一個后，轉(zhuǎn)至第3步。Step3：在A所在當(dāng)前路線上，搜索A能否直達到B，若能，并且所花時間小于time(或cost)，則花費時間賦值于變量time(或cost)，并記錄當(dāng)前路線，存于數(shù)組luxian中；無論A在當(dāng)前路線能否直達B，則都轉(zhuǎn)至第4步。Step4：依次以A所在當(dāng)前路線的后續(xù)站，作為中轉(zhuǎn)站C，再將C視為起點站，B為終點站，重復(fù)2—3步驟；Step5：從2—4步中，采用每遞歸一次換乘一次車，使用了深度優(yōu)先搜索法，以及回溯法思想，遍歷所有可能情況，始終將當(dāng)前最優(yōu)存于time(或cost)和luxian中，結(jié)束后，time(或cost)存的是最優(yōu)時間(或最少費用)，luxian存的是最優(yōu)路線。3. 2 轉(zhuǎn)乘3次以上的近似算法以上方法使用剪枝函數(shù)減少了搜索上限，使得轉(zhuǎn)車在02次時能很快找出全局最優(yōu)路線。但是大量實踐表明，當(dāng)轉(zhuǎn)車次數(shù)在3次以上時，搜索求解的時間將明顯延長。針對這種情況，提出解決措施與方案如下：對于02次的轉(zhuǎn)車，完全可以利用深度優(yōu)先搜索遍歷一切可能的情況；當(dāng)最多的轉(zhuǎn)車次數(shù)達到3次以上時，用一個回溯算法執(zhí)行次數(shù)的上界用來控制搜索次數(shù)，以達到當(dāng)前局部最優(yōu)，經(jīng)多次反復(fù)調(diào)試。，該值設(shè)為107，并且將時間大約控制在10秒內(nèi)。當(dāng)累加次數(shù)達到107次時，搜索還未遍歷完所有路線，便記錄下當(dāng)前以找到的所有可行路線中的最優(yōu)路線。最后用該最優(yōu)路線與最多轉(zhuǎn)乘2次的全局最優(yōu)路線進行比較，將兩者的最優(yōu)作為該近似算法的結(jié)論。3. 3 回溯算法的復(fù)雜度狀態(tài)空間樹：描述優(yōu)化問題解空間的樹行結(jié)構(gòu)。樹中的每一個結(jié)點稱為一個問題狀態(tài)。如果從根到樹中的某個狀態(tài)的路徑代表一個作為侯選的元組，則稱該狀態(tài)為解狀態(tài)。所有的葉結(jié)點都是解狀態(tài)。如果從根到某個狀態(tài)的路徑代表一個可行解的元組，則稱該解狀態(tài)為答案狀態(tài)。（形象的狀態(tài)空間樹見圖910）圖910 狀態(tài)空間樹剪枝函數(shù)：指剪去不必要狀態(tài)生成樹的搜索子樹，減少問題求解所需實際生成的狀態(tài)點數(shù)為目標(biāo)約束函數(shù)與有界函數(shù)的統(tǒng)稱。具體而言，當(dāng)問題的解空間可以用一棵狀態(tài)空間樹來描述，為了提高搜索效率以尋找狀態(tài)樹的答案狀態(tài)，在搜索過程中使用約束函數(shù)，可以避免無謂地搜索那些已知不含答案狀態(tài)的子樹；如果是最優(yōu)化問題，可以使用限界函數(shù)，剪去不可能包含最優(yōu)答案結(jié)點的子樹。回溯算法的效率分析[2](注釋：引用于[2]書中的178頁。)：回溯法的時間通常取決于狀態(tài)空間樹上實際生成的那部分問題狀態(tài)的數(shù)目，在本文要求的最優(yōu)選擇路線的限制下，其取決于公眾出行過程中經(jīng)過的公交站點數(shù)目。對于元組長度為n的問題實例，若其狀態(tài)空間樹中的結(jié)點總數(shù)為n!(或或)，則回溯算法的最壞情況時間復(fù)雜度可達()(或或), 這里是n 的多項式，是生成一個結(jié)點所需要的時間。下面，我們采用蒙特卡羅算法思想來計算回溯算法求解模型的大致時間，并對回溯算法的時效性做出評價。首先，蒙特卡羅方法的基本思想是在狀態(tài)樹中隨機的選擇一條路徑。設(shè)X是這條隨機路徑上，代表部分向量的結(jié)點，如果在X處不受限制的孩子數(shù)目為。也就是說，若不受限制的,的取值有個，則第2層上有個結(jié)點(根是第一層)；若不受限制的取值有個，則第3層上有個結(jié)點；其余類推。由于認為在同一層上不受限制的結(jié)點數(shù)目相同，因此，整個狀態(tài)空間樹上將實際生成的結(jié)點數(shù)估計為其次，結(jié)合公交最佳選擇路線的市場實際情況，將公交站點映射為蒙特卡羅方法中的狀態(tài)空間數(shù)結(jié)點，并記起始站A、終點站B分別對應(yīng)于結(jié)點、。于是，欲建立高效率的公交線路選擇自主查詢計算機系統(tǒng)，必須提高回溯算法的時效性。換乘次數(shù)不超過2時，可以直接按照深度優(yōu)先的逐層搜索算法，在有限的時間內(nèi)(單個路線計算時，不超過1分鐘)求得最優(yōu)出行乘車方式。當(dāng)轉(zhuǎn)車次數(shù)大于2時，利用以上的計算方式，搜索難度較大。因此，根據(jù)公眾對出行時間的滿意度需求，我們設(shè)定搜索次數(shù)的上界為，進而限定的值在一定的范圍之內(nèi)，實現(xiàn)回溯算法的有限搜索，尋找局部最優(yōu)解，提高算法的時間效率。四 模型評價 模型分析與檢驗?zāi)Ｐ褪强紤]公眾乘車滿意程度的主要出行耗時、換乘次數(shù)、乘車總費用三個因素，并分別以這3個因素為目標(biāo)函數(shù)的優(yōu)化模型，首先，對各模型的敏感性進行了分析，通過程序調(diào)試，發(fā)現(xiàn)減少多條線路或站點對各模型的結(jié)果沒有太大的影響；其次，對各模型進行了強健性分析，通過改變發(fā)現(xiàn)是發(fā)現(xiàn)各模型具有很強的穩(wěn)定性，符合實際情況的。主要考慮公眾出行耗時最少，經(jīng)過計算，換乘次數(shù)對公眾出行耗時影響較大，但充分考慮公眾心理感受和社會實際情況，換乘次數(shù)不可能太多，同時兼顧求解的復(fù)雜程度，將換乘次數(shù)確定一個上界，故模型具有合理性。同時以出行耗時最少、換乘次數(shù)最少、乘車總費用最少綜合考慮，作為公眾的滿意度，來選擇最佳路線是符合實際情況的。 通過對模型進行了敏感性和強健性分析，減少一些線路或者站點，對題目中的6對起始站耗時沒有影響，說明模型具有很強的適用性。對社會今后城市的發(fā)展需要增加一些線路，站點或者由于一些突發(fā)事件進行封路以及拆站，該模型具有長期的適用性，所以模型具有合理性。 模型改進在建立以滿意度為目標(biāo)函數(shù)的模型中，用出行耗時、換乘次數(shù)、乘車總費用乘積的倒數(shù)來刻畫滿意度，不是十分準確，故該模型可以改進為層次分析模型。建立層次結(jié)構(gòu)模型：以追求滿意度最大為目標(biāo)層，以出行耗時、換乘次數(shù)、乘車總費用為準則層，在所有可行路線中選取最佳路線為方案層。構(gòu)造成對比較陣：通過對公眾在乘車時的不同需求進行調(diào)查研究，反饋的問卷信息實行打分，得出其權(quán)重，構(gòu)造成對比較陣。計算權(quán)向量并做一致性檢驗。最后，計算組合權(quán)向量并做組合一致性檢驗，從而得出滿意度函數(shù)。 模型評價與推廣優(yōu)點：根據(jù)查詢者不同的需求，設(shè)計的公交查詢系統(tǒng)能快速地找到相應(yīng)的最佳路線，具有很大的靈活性。考慮了各因素之間的相關(guān)關(guān)系，給出了各因素之間的綜合滿意度模型，方便查詢者能夠綜合自身不同需求來選擇最佳路線。減少多條線路或站點對各模型的結(jié)果沒有太大的影響，對社會今后城市發(fā)展的需要增加一些線路，站點或者由于一些突發(fā)事件進行封路以及拆站，該模型具有長期的適用性和地域推廣性。在模型中盡量考慮了實際情況，在設(shè)計計算機查詢系統(tǒng)時，充分考慮其時效性 ，使公眾對計算機查詢系統(tǒng)能夠接受。缺點：在考慮出行耗時、換乘次數(shù)、乘車總費用的綜合模型中，對這三者相關(guān)關(guān)系時沒有充分考慮其數(shù)量級問題，進行直接相乘作為滿意度是不太合理的。在考慮綜合模型時，沒有對出行耗時、換乘次數(shù)、乘車總費用的權(quán)重進行分析討論，這是我們的不足之處。由模型設(shè)計的計算機查詢系統(tǒng)具有高時效性，能夠在全國列車站點，網(wǎng)絡(luò)站點進行推廣和應(yīng)用。由于模型設(shè)計的計算機查詢系統(tǒng)具有很強的穩(wěn)定性，可以長期使用。由模型而設(shè)計的計算機查詢系統(tǒng)不僅適用于北京公交系統(tǒng)，而且還適用于其它城市公交系統(tǒng)。實驗四 小行星軌道問題（2學(xué)時）【實驗?zāi)康摹?. 掌握線性方程組求解2. 加深對正交變換的理解3. 掌握Matlab軟件中的ezplot、zplot命令的區(qū)別和適用范圍【實驗要求】掌握繪制隱函數(shù)曲線ezplot命令和彗星狀軌跡圖et命令【實驗內(nèi)容】天文學(xué)家要確定一顆小行星繞太陽運行的軌道，在軌道平面內(nèi)建立以太陽為原點的直角坐標(biāo)系，在兩坐標(biāo)軸上取天文測量單位（一天文單位為地球到太陽的平均距離：9300萬里）。在五個不同的時間點對小行星作了觀察，測得軌道上五個點的坐標(biāo)數(shù)據(jù)如下: 表1 小行星觀測數(shù)據(jù) xy由開普勒第一定律知，小行星軌道為一橢圓。設(shè)方程為試確定橢圓的方程并在軌道的平面內(nèi)以太陽為原點繪出橢圓曲線。并應(yīng)用坐標(biāo)平移變換和正交變換將上例題中的二次曲線方程化為標(biāo)準方程，繪橢圓軌道圖，完成小行星運行的動態(tài)模擬?！緦嶒灧桨浮浚?）二次曲線方程中有五個待定系數(shù)：，。將觀察所得的五個點坐標(biāo)數(shù)據(jù)，代入二次曲線方程得到關(guān)于，，的線性方程組 求解該方程組得橢圓方程的系數(shù)：[，，] 。（2）將橢圓的一般方程寫成矩陣形式通過變量變換（平移變換和旋轉(zhuǎn)變換）化為橢圓標(biāo)準方程。首先化去一次項，然后將二次型化為標(biāo)準型。為了用平移變換消去一次項，令，（，待定），代入方程整理，得其中。要化簡消去一次項，只須選擇，使?jié)M足二階線性方程組