无码成人A片在线观看,性欧美videofree高清变态,中文字幕有码无码av,国产无人区卡一卡二扰乱码 ,最近高清日本免费

CNTXJ.NET | 通信界-中國通信門戶 | 通信圈 | 通信家 | 下載吧 | 說吧 | 人物 | 前瞻 | 智慧(區(qū)塊鏈 | AI
 國際新聞 | 國內(nèi)新聞 | 運營動態(tài) | 市場動態(tài) | 信息安全 | 通信電源 | 網(wǎng)絡融合 | 通信測試 | 通信終端 | 通信政策
 專網(wǎng)通信 | 交換技術 | 視頻通信 | 接入技術 | 無線通信 | 通信線纜 | 互聯(lián)網(wǎng)絡 | 數(shù)據(jù)通信 | 通信視界 | 通信前沿
 智能電網(wǎng) | 虛擬現(xiàn)實 | 人工智能 | 自動化 | 光通信 | IT | 6G | 烽火 | FTTH | IPTV | NGN | 知本院 | 通信會展
您現(xiàn)在的位置: 通信界 >> 工業(yè)自動化 >> 技術正文
 
基于深度優(yōu)先搜索的鐵路中轉路線規(guī)劃研究
[ 通信界 | 郭怡然 | m.k-94.cn | 2023/7/23 18:30:06 ]
 

摘要:目前,許多長距離鐵路出行沒有直達列車,或直達列車繞路,導致額外的時間和金錢花費。本文針對這一現(xiàn)象,將復雜的鐵路路線數(shù)據(jù)抽象成計算機方便處理的圖,使用帶有剪枝優(yōu)化的深度優(yōu)先搜索算法,對可能的乘車中轉方案進行遍歷,根據(jù)不同目標(如花費最少、耗時最短、到達時間最早等)挑選出不同中轉方案,供用戶出行參考。根據(jù)軟件設計的原則和方法,給出了使用實現(xiàn)該算法的系統(tǒng)的設計。

關鍵詞:鐵路中轉方案;深度優(yōu)先算法;剪枝優(yōu)化;軟件系統(tǒng)設計

一、引言

隨著我國鐵路行業(yè)的飛速發(fā)展,鐵路出行已經(jīng)成為很多人出行的首選。隨著高鐵、動車的車次越來越多,鐵路網(wǎng)變得愈加復雜。如何在錯綜復雜的鐵路線路中規(guī)劃出一條花費最少,或者到達時間最早,又或者是換乘次數(shù)最少的乘車方案愈發(fā)顯得重要。12306 官方網(wǎng)站提供的各種換乘方案無法讓用戶自己設定最早出發(fā)時間,最晚到達時間,以及最小換乘時間的限制,而且最多只能換乘一次,靈活性受限。提供的換乘方案又多又雜,用戶體驗不好。

本文以開發(fā)一個能夠幫助用戶更加靈活地規(guī)劃乘車方案的系統(tǒng)為目標,彌補 12306 官網(wǎng)提供的服務的缺點,支持用戶自己定制各種條件,包括最早出發(fā)時間、最晚到達時間、最小換乘時間、最大換乘次數(shù)。為用戶規(guī)劃出行路線提供一定參考。

二、算法設計

算法主要分為兩部分,一部分是根據(jù)鐵路數(shù)據(jù)構建出圖,另一部分是在圖上進行搜索。

(一)構建圖

將每個站點抽象成點,兩個站點之間的鐵路線路抽象成邊。設計站點的數(shù)據(jù)結構如下,后期可以方便地進行屬性的添加。設計路線的數(shù)據(jù)結構如下,維護了始發(fā)站、終點站、始發(fā)時間、到達時間、座位類型(二等座/硬座)、價格、編號等信息。

采用鄰接表數(shù)據(jù)結構存儲圖,即對于每個站點Station,存儲離開它的所有線路,圖的數(shù)據(jù)結構如圖1:

為了方便剪枝和輸出最終方案,創(chuàng)建方案的數(shù)據(jù)結構如下,即維護花費、到達時間、總用時、與期望時間差異程度等各項評價參數(shù):

方法:betterInAllAspects和atLeastBetterInOneAspect,分別用于對其他方案進行剪枝和決定是否對當前方案剪枝。

(二)圖的搜索

常用的搜索算法主要有兩類,深度優(yōu)先和廣度優(yōu)先。廣度優(yōu)先可以保證第一次搜索到站時可以保證在某方面最優(yōu),但空間復雜度較大。由于本系統(tǒng)是需要提供多個不同指標最優(yōu)化的方案,因此廣度優(yōu)先的這個性質(zhì)并不能很好地被利用。同時考慮到圖的點數(shù)和邊數(shù)較多,因此選用空間復雜度較小的深度優(yōu)先搜索算法來實現(xiàn)。

算法核心流程:構建一個Traveler對象模擬各種乘車方案,具體來講,當traveler到達某個站點后,看一下在當前時間所有可以乘坐的車次,依次嘗試各個可以乘坐的車次,同時更新花費和到達時間,到達下一個車站后重復上述過程。當?shù)竭_一個車站發(fā)現(xiàn)沒有任何一輛車次可以乘坐,則回退到上一個車站嘗試其他車次,具體實現(xiàn)如下:

// 嘗試從當前站乘車

for (Line line : graph.map.get(currentStation.id)) {

if (!path.empty() && !path.peek().id.equals(line.id) &&

(line.startTime.getTime() - currentDate.getTime()) <

(long) minMinutesForSameStationTransfer * 60 * 1000)

continue;

if (line.startTime.compareTo(currentDate) < 0) continue; // 防止跨天

// 更新?lián)Q乘次數(shù)

int newTransferTimes = transferTimes;

if (!path.isEmpty() && 。╬ath.peek().id).equals(line.id)) newTransferTimes++;

if (newTransferTimes > maxTransferTimes) continue;

path.push(line);

travel(line.endStation, line.endTime, currentCost + line.price, newTransferTimes);

path.pop();

}

(三)剪枝優(yōu)化

為了縮短用戶查詢時間,需要對上述算法進行優(yōu)化。通過之前定義的Scheme數(shù)據(jù)結構可以方便地對搜索過程進行剪枝。剪枝可以分為兩部分,一部分根據(jù)用戶的限制條件進行剪枝,例如當前時間已經(jīng)超出用戶設置的可以接受的最晚到達時間,則沒有必要繼續(xù)擴展當前搜索子樹。另一種是通過和歷史經(jīng)過該站點的方案進行比較,如果當前方案在所有方面均比歷史方案差,則沒有必要在此方案的基礎上繼續(xù)嘗試。

(四)方案評價與復雜度分析

曾考慮過效率更高的動態(tài)規(guī)劃算法,但為了更高的靈活性和可擴展性以及易實現(xiàn)性選用了搜索算法。搜索算法在最壞情況下時間復雜度將是指數(shù)級別。但由于乘車問題具有時間限制其復雜度遠遠低于指數(shù)。在最初測試時對于用戶查詢大概可以在幾分鐘內(nèi)返回結果。這樣的表現(xiàn)顯然不盡如人意。于是采用“剪枝”對算法進行優(yōu)化,優(yōu)化之后,通過測試,平均可以在5s內(nèi)可以返回查詢結果。

三、系統(tǒng)設計

本文所設計的系統(tǒng)是一個后端系統(tǒng),為前端提供查詢服務接口,主要借助Spring平臺。

系統(tǒng)分為四個模塊:數(shù)據(jù)獲取模塊、核心算法處理模塊、數(shù)據(jù)庫交互模塊、WEB模塊。各模塊之間的依賴關系如圖3。

WEB模塊負責處理前端發(fā)送的請求,將請求傳遞給算法處理模塊,并將處理結果返回給前端。

核心算法模塊在初始化時從數(shù)據(jù)庫中將鐵路路線信息加載進內(nèi)存,接受請求,通過搜索,將結果返回給WEB模塊。

數(shù)據(jù)庫交互模塊使用Mybatis框架,負責將數(shù)據(jù)庫數(shù)據(jù)映射成Java對象。

數(shù)據(jù)獲取模塊使用并發(fā)優(yōu)秀的WebMagic框架,負責訪問接口獲取鐵路信息,并將信息存入數(shù)據(jù)庫。同時使用Spring Task做定時任務框架,每日定時更新鐵路信息。

同時系統(tǒng)采用分布式架構,各個服務之間使用Dubbo進行通信。整個系統(tǒng)的部署圖如圖4。

四、結論

基本實現(xiàn)了預期功能。

五、解決方案持有的問題

①暫時無法提供跨天乘車方案,一是因為數(shù)據(jù)不充足,二是算法處理時間較長,無法在5s內(nèi)返回用戶想要的方案。

②雖然在爬蟲系統(tǒng)方面采取種種措施保證數(shù)據(jù)完整性,但還會丟失0.2%的數(shù)據(jù)。難以在數(shù)據(jù)完整性和爬取速度方面達到平衡。

③由于采用將整條路線拆分成一段段的路徑類和求花費,使用這種方案計算出的價格和實際價格可能有0.5元或者1元的誤差。

六、后續(xù)研究方向

①增加跨天乘車方案的功能。

②加強對數(shù)據(jù)獲取的控制,爭取達到更高的數(shù)據(jù)完整性和更快的獲取速度。

作者單位:郭怡然 重慶市重慶郵電大學2019級軟件工程學院

參  考  文  獻

[1]林開欽,白羽,王倩,柴強. 一種改進的星間鏈路深度優(yōu)先路由搜索算法[C]//第十二屆中國衛(wèi)星導航年會論文集——S06 時間基準與精密授時.[出版者不詳],2021:98-101.DOI:10.26914/c.cnkihy.2021.002192.

[2]https://redis.io/documentation [2021.10.2]

[3]https://www.rabbitmq.com/getstarted.html [2021.10.3]

[4]https://dubbo.apache.org/zh/docs/ [2021.10.5]

[5]http://webmagic.io/docs/zh/ [2021.10.1]

 

1作者:郭怡然 來源:中國新通信 編輯:顧北

 

聲明:①凡本網(wǎng)注明“來源:通信界”的內(nèi)容,版權均屬于通信界,未經(jīng)允許禁止轉載、摘編,違者必究。經(jīng)授權可轉載,須保持轉載文章、圖像、音視頻的完整性,并完整標注作者信息并注明“來源:通信界”。②凡本網(wǎng)注明“來源:XXX(非通信界)”的內(nèi)容,均轉載自其它媒體,轉載目的在于傳遞更多行業(yè)信息,僅代表作者本人觀點,與本網(wǎng)無關。本網(wǎng)對文中陳述、觀點判斷保持中立,不對所包含內(nèi)容的準確性、可靠性或完整性提供任何明示或暗示的保證。請讀者僅作參考,并請自行承擔全部責任。③如因內(nèi)容涉及版權和其它問題,請自發(fā)布之日起30日內(nèi)與本網(wǎng)聯(lián)系,我們將在第一時間刪除內(nèi)容。 
熱點動態(tài)
普通新聞 中信科智聯(lián)亮相2023中國移動全球合作伙伴大會
普通新聞 全球首個基于Data Channel的新通話商用網(wǎng)絡呼叫成功撥通
普通新聞 中國聯(lián)通:以優(yōu)質(zhì)通信服務 助力“一帶一路”共建繁華
普通新聞 楊杰:未來五年,智算規(guī)模復合增長率將超過50%
普通新聞 長沙電信大樓火災調(diào)查報告發(fā)布:系未熄滅煙頭引燃,20余人被問責
普通新聞 鄔賀銓:生態(tài)短板掣肘5G潛能發(fā)揮,AI有望成“破局之劍”
普通新聞 工信部:加大對民營企業(yè)參與移動通信轉售等業(yè)務和服務創(chuàng)新的支持力
普通新聞 摩爾線程亮相2023中國移動全球合作伙伴大會,全功能GPU加速云電腦體
普通新聞 看齊微軟!谷歌表示將保護用戶免受人工智能版權訴訟
普通新聞 聯(lián)想王傳東:AI能力已成為推動產(chǎn)業(yè)升級和生產(chǎn)力躍遷的利刃
普通新聞 APUS李濤:中國的AI應用 只能生長在中國的大模型之上
普通新聞 外媒:在電池競賽中,中國如何將世界遠遠甩在后面
普通新聞 三星電子預計其盈利能力將再次下降
普通新聞 報告稱華為5G專利全球第1 蘋果排名第12
普通新聞 黨中央、國務院批準,工信部職責、機構、編制調(diào)整
普通新聞 榮耀Magic Vs2系列正式發(fā)布,刷新橫向大內(nèi)折手機輕薄紀錄
普通新聞 GSMA首席技術官:全球連接數(shù)超15億,5G推動全行業(yè)數(shù)字化轉型
普通新聞 北京聯(lián)通完成全球首個F5G-A“單纖百T”現(xiàn)網(wǎng)驗證,助力北京邁向萬兆
普通新聞 中科曙光亮相2023中國移動全球合作伙伴大會
普通新聞 最高補貼500萬元!哈爾濱市制定工業(yè)互聯(lián)網(wǎng)專項資金使用細則
通信視界
鄔賀銓:移動通信開啟5G-A新周期,云網(wǎng)融合/算
普通對話 中興通訊徐子陽:強基慧智,共建數(shù)智熱帶雨
普通對話 鄔賀銓:移動通信開啟5G-A新周期,云網(wǎng)融合
普通對話 華為輪值董事長胡厚崑:我們正努力將5G-A帶
普通對話 高通中國區(qū)董事長孟樸:5G與AI結合,助力提
普通對話 雷軍發(fā)布小米年度演講:堅持做高端,擁抱大
普通對話 聞庫:算網(wǎng)融合正值挑戰(zhàn)與機遇并存的關鍵階
普通對話 工信部副部長張云明:我國算力總規(guī)模已居世
普通對話 鄔賀銓:我國互聯(lián)網(wǎng)平臺企業(yè)發(fā)展的新一輪機
普通對話 張志成:繼續(xù)加強海外知識產(chǎn)權保護工作 為助
普通對話 吳春波:華為如何突破美國6次打壓的逆境?
通信前瞻
亨通光電實踐數(shù)字化工廠,“5G+光纖”助力新一
普通對話 亨通光電實踐數(shù)字化工廠,“5G+光纖”助力新
普通對話 中科院錢德沛:計算與網(wǎng)絡基礎設施的全面部
普通對話 工信部趙志國:我國算力總規(guī)模居全球第二 保
普通對話 鄔賀銓院士解讀ChatGPT等數(shù)字技術熱點
普通對話 我國北方海區(qū)運用北斗三號短報文通信服務開
普通對話 華為云Stack智能進化,三大舉措賦能政企深度
普通對話 孟晚舟:“三大聚力”迎接數(shù)字化、智能化、
普通對話 物聯(lián)網(wǎng)設備在智能工作場所技術中的作用
普通對話 軟銀研發(fā)出以無人機探測災害被埋者手機信號
普通對話 AI材料可自我學習并形成“肌肉記憶”
普通對話 北斗三號衛(wèi)星低能離子能譜儀載荷研制成功
普通對話 為什么Wi-Fi6將成為未來物聯(lián)網(wǎng)的關鍵?
普通對話 馬斯克出現(xiàn)在推特總部 收購應該沒有懸念了
普通對話 臺積電澄清:未強迫員工休假或有任何無薪假
普通對話 新一代載人運載火箭發(fā)動機研制獲重大突破
推薦閱讀
Copyright @ Cntxj.Net All Right Reserved 通信界 版權所有
未經(jīng)書面許可,禁止轉載、摘編、復制、鏡像