一種全節(jié)點遍歷路徑優(yōu)化方法

基本信息

申請?zhí)?/td> CN201010594468.X 申請日 -
公開（公告）號 CN102004839A 公開（公告）日 2011-04-06
申請公布號 CN102004839A 申請公布日 2011-04-06
分類號 G06F17/50(2006.01)I 分類 計算；推算；計數(shù);
發(fā)明人 李鵬杰;鄭眾喜 申請（專利權(quán)）人 北京優(yōu)納金視科技有限公司
代理機構(gòu) 北京金闕華進專利事務(wù)所（普通合伙） 代理人 北京優(yōu)納科技有限公司;蘇州優(yōu)納科技有限公司
地址 100085 北京市海淀區(qū)上地五街7號昊海大廈402
法律狀態(tài) -

摘要

摘要 本發(fā)明提供了一種高效快速的全節(jié)點遍歷路徑優(yōu)化的方法，最終生成一個單向的節(jié)點隊列路徑。本方法包括以下幾個步驟：首先根據(jù)需要解決的實際問題構(gòu)建節(jié)點網(wǎng)絡(luò)，該網(wǎng)絡(luò)可以是全向網(wǎng)絡(luò)，以節(jié)點間的邊記錄路徑花費；然后對全部節(jié)點建立最小生成樹，針對生成樹上的所有分支和端點建立隊列；之后通過試探性的算法對有分支的節(jié)點逐一切斷各個分支，每切斷一個分支就根據(jù)端點隊列搜索距離最小的端點對進行連接，不斷進行這步操作，直到原最小生成樹中的所有分支都被斷開，所有節(jié)點連接成一個單向隊列。在建立新的端點連接時，本方法還提供一種檢測機制以避免新連接使節(jié)點隊列形成一個環(huán)，從而避免路徑中有節(jié)點丟失。此外本發(fā)明中還包括一個橫向或縱向優(yōu)先的路徑作為優(yōu)化路徑的備選，以提高整個方法的可靠性。