摘要:本發明提供了一種高效快速的全節點遍歷路徑優化的方法,最終生成一個單向的節點隊列路徑。本方法包括以下幾個步驟:首先根據需要解決的實際問題構建節點網絡,該網絡可以是全向網絡,以節點間的邊記錄路徑花費;然后對全部節點建立最小生成樹,針對生成樹上的所有分支和端點建立隊列;之后通過試探性的算法對有分支的節點逐一切斷各個分支,每切斷一個分支就根據端點隊列搜索距離最小的端點對進行連接,不斷進行這步操作,直到原最小生成樹中的所有分支都被斷開,所有節點連接成一個單向隊列。在建立新的端點連接時,本方法還提供一種檢測機制以避免新連接使節點隊列形成一個環,從而避免路徑中有節點丟失。此外本發明中還包括一個橫向或縱向優先的路徑作為優化路徑的備選,以提高整個方法的可靠性。
- 專利類型發明專利
- 申請人北京優納科技有限公司;
- 發明人李鵬杰;鄭眾喜;
- 地址100085 北京市海淀區上地五街7號昊海大廈402
- 申請號CN201010594468.X
- 申請時間2010年12月17日
- 申請公布號CN102004839A
- 申請公布時間2011年04月06日
- 分類號G06F17/50(2006.01)I;