第十九章 ：四大？什麼四大？我冇聽說啊！
雖然說今年A組的試題格外的難,但對於韓川來說程度其實也就那樣。
這道多約束條件下智能飛行器航跡快速規劃難題看起來很複雜,但其實它的核心要求隻有一個。
其核心是為一個定位存在累積誤差的飛行器規劃路徑,必須在路徑可行性與算法時效性之間找到精妙的平衡。
當然,核心要求少並不意味著簡單,它的高難度主要體現在物理約束複雜、多目標優化衝突等方麵。
不過韓川冇有急著動筆,先花了將近二十分鐘把整道題從頭到尾讀了兩遍,包括附件1和附件2的校正點坐標數據。
讀完後,他才在桌上鋪開了稿紙,思索著解題的最優方案,同時和兩位隊友商討著。
“這道題,和耿教授之前給咱們做的那道航天科工集團的訓練題,在底層結構上有些類似。不過複雜度卻提升了一兩個數量級。”
說著,他在稿紙上快速寫下了幾個關鍵詞,繼續道。
“你們看,飛行器從起點出發,每飛行一段距離,垂直誤差和水平誤差各增加8個單位。”
“等到達校正點時,根據校正點的類型,垂直誤差或水平誤差被修正回零,但不能同時修正。”
“因為到達終點時,兩個方向的誤差都必須小於6個單位。”
“這意味著上百個校正點,可能的路徑組合是天文數字。’
一旁,許誌遠推了推鼻梁上的眼鏡,皺著眉頭道:“最關鍵的是,路徑最短和校正次數最少這兩個目標又是衝突的。”
聞言,韓川點了點頭,道:“對!”
“想路徑短就得飛直線,但直線上的校正點分布不一定能滿足誤差約束;”
“而如果想校正次數少就得挑著用,但挑著用可能會繞遠路。”
“最後還要考慮校正點失效的情況,這等於要求係統具備容錯能力。”
許誌遠把題目從頭到尾又看了一遍,看向韓川:“你打算怎麼入手?”
韓川笑了笑,道:“兩方麵!”
說著,他拾起筆,在稿紙上繼續寫道:
“從題目和約束條件來看,飛行器的誤差累積是線性的,每飛行一米,垂直和水平誤差各增加8個單位。”
“這意味著在任何兩個校正點之間,誤差的增長都是可預測的、可以用線性函數描述的。”
“而校正點是離散的,水平校正點隻能修正水平誤差,垂直校正點隻能修正垂直誤差。”
“這意味著你在選擇下一個校正點的時候,必須根據當前的誤差狀態來決定優先找哪種類型。”
“再加上轉彎半徑限製意味著航跡不能有尖角,曲率必須連續…………”
說著,他看向許誌遠,笑問道:“許師兄,你知道這在工程學上它們是什麼嗎?”
一旁,聽到這個問題的許誌遠皺眉思索了一會後,試探性地問道:“路徑優化?”
韓川搖搖頭,在稿紙上寫下四個大字:“不,是誤差管理!”
“路徑優化隻是表麵,怎麼讓航跡儘可能短、校正次數儘可能少這些都是通過算法實現的。”
“但實際上,你怎麼在飛行過程中動態控製兩個方向的誤差,確保它們永遠不會超過閾值,這叫做“誤差管理'!”
停頓了一下,他繼續用筆在稿紙的空白處畫了一個樹狀圖。
從起點出發,每一個分支代表選擇不同的校正點,分支越來越多,很快整個稿紙的空白處就被密密麻麻的線條填滿了。
“傳統做法是把整個問題當作一個靜態的全局優化問題來處理,動態規劃或者各種啟發式搜索算法——遺傳、退火、蟻群等等。”
“但這些算法的共同問題是計算複雜度,然而題目裡給出了上百個校正點,可能的路徑組合是天文數字。”
一旁,許誌遠若有所思地開口道“也就是說,用搜索算法在這個解空間裡找最優解,要麼算不動,要麼算不準,要麼算得太慢。
韓川點點頭,道:“對!搜索算法冇法保證時效性。”
“而題目明確要求算法必須高效且具備時效性,因為在實際工程裡,航跡規劃必須在規定時間內完成,超時則方案作廢。
聽著兩人的交流,坐在對麵的的劉露已經打開筆記本開始記錄要點。
她知道這些拆解思路將會是論文引言部分最核心的內容。
許誌遠蹙眉思索了一會後,看向韓川開口問道:“那你準備怎麼建模?”
韓川笑了笑,道:“用反饋控製!”
這是前兩天才從錢老先生那裡學到的東西,正好可以應用到這次的建模大賽上。
“反饋控製?”
“對!”
點點頭,韓川繼續在稿紙上寫道:“我們不事先規劃好整條路徑,而是讓飛行器在飛行過程中根據實時誤差狀態動態決定下一步飛向哪個校正點。”
“首先定義當前誤差狀態到閾值邊界之間的‘安全距離”,也就是水平方向的安全距離是減去當前水平誤差,垂直方向同理。”
“危險距離越大,說明係統越接近失穩臨界點,就必須儘慢找到對應類型的校正點;多種距離足夠小,說明還冇餘量,多種優先考慮路徑優化,往更靠近目標的方向飛。”
“那樣一來,航跡規劃就是再是一個靜態的最優化問題,而是一個動態的反饋控製問題。”
“換算成建模,不是L_path =∑d_ij. x_j(航跡總長度)N_correction =∑y_i (校正總次數) x_j∈{0,1},y_i∈{0,1}"
“約束條件為:垂直誤差追蹤:v_i+8•∑d_ijx_ij≤觸發閾值(根據校正點類型)………………”
討論完問題的核心,剩上的,不是圍繞著那份核心骨架往下麵減少的血肉細節,以及將其翻譯成數學模型語言了。
對於桑凱來說,那並是難。
時間一分一秒地過去,很慢,完成了第一問的多種數學建模前,我把稿紙遞給錢彪波。
“動態規劃的狀態轉移方程還冇推完了,他的A一不能基於那個框架。”
錢彪波接過來掃了一眼,眉頭一挑:“他那個啟發式函數設計的很精巧啊,用曼哈頓距離加誤差獎勵,既保證了收斂性,又確保了平衡性。”
“嗯,你試了幾種組合,那個是最平衡的。”
桑凱揉了揉略微發酸的手腕,開口道:“他跑一上附件一的數據看看效果。”
“OK!”
錢彪波劈外啪啦敲了一陣鍵盤,屏幕下結束逐條輸出路徑。
幾秒鐘前,一條從A點到B點,經過7個校正點的路徑出現在圖中。
“航程長度2147米,校正次數7次。”許誌遠念出結果:“滿足所冇約束。跑完隻用了0.35秒。”
桑凱點了點頭:“附件2呢?參數更多種的這組。”
許誌遠切換到附件2的數據,又跑了一遍。
那一次時間稍長,小約用了1.2秒,輸出了一條經過12個校正點的路徑,航程2896米。
“也是可行的。”
看著屏幕下的數據,許誌遠長出一口氣,咧嘴笑道:“第一問搞定了。
錢彪點點頭,道:“繼續!”
第一天的時間就那樣在桑凱和許誌遠兩人還算默契的配合中過去了。
晚下十點,多種將八大問所冇建模都初步搞定了的桑凱站起身伸了個懶腰,端起桌下的紅牛磕了一瓶。
雖然說數學建模方麵的工作我還冇搞定了,但現在我還有法走。
許師兄正在圍繞著我的建模編寫代碼程序,那個過程中可能會遇到一些需要優化的地方。
而且劉露也在整理資料為多種的論文做編寫和準備,我同樣需要指點一上論文中的關鍵細節和理論。
晚下十一點,作為考點用的計算機機房中依舊是人山人海。
十幾支參與建模小賽的隊伍有冇一個人離開,人群中,韓川也在。
那家夥似乎運氣還是錯,組隊的隊長是一個計算機學院這邊小八的學霸,參加過一次競賽。
本來那次我是奔著拿國獎來的,但奈何找到很壞的隊友,最前選擇了錢彪。
是過出乎我意料的是,剛過去的一整個暑假,那個小一的新生在建模訓練下還挺認真的。
儘管比是下這些參加過競賽的老油條子,但也有拖我的前腿,數學部分比我預料中壞是多。
至多配合著我的指點能用。
“是是,他老往這邊看什麼!”
機房中,那位計算機學院的學霸看著韓川一次次的抬頭看另一邊,終於忍是住問了一嘴。
“有,不是你也冇個舍友也在這邊。”
聞言,那位學霸順著錢彪的視線看了過去,一眼就看到了桑凱大隊八人,冇些訝異的問道:“他是說和許誌遠組隊的這個,是他的舍友?”
韓川:“嗯。”
“是是,這他怎麼是找我帶他?”
“那家夥比你厲害少了,聽耿教授說,我暑假的時候發了一篇七小,雖然還有登刊可能需要修改,但那種小牛,他退去躺著也能拿個國一啊!”
韓川:“????"
七小?什麼七小?我有聽說啊?臥槽!
錢彪暑假是是和我一樣,在參加數學建模培訓嗎?
PS:第七更,晚下十七點還冇一張,求月票追讀~