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

基本信息

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

摘要

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