[發明專利]一種基于A星策略的最優多會合點路徑搜索方法及裝置

有效

• 申請號: 201511018390.6
• 申請日: 2015-12-30
• 公開（公告）號: CN105678054B
• 公開（公告）日: 2020-06-30
• 發明（設計）人: 李榮華;邱宇軒;毛睿;秦璐;鐘舒馨
• 申請（專利權）人: 深圳大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/29
• 代理公司: 深圳市興科達知識產權代理有限公司 44260
• 代理人: 王翀

1.一種基于A星策略的最優多會合點路徑搜索方法，其特征在于，該方法包括：

首先，獲取路徑搜索預設信息，包括：圖G＝(V,E,W)，點集U，α，出發點s，目的點t；其中，V、E和W分別為點集、邊集和權值的集合；為頂點的子集；參數α∈(0,1)，用于平衡圖G上s～t路徑P_st和U中的點到路徑P_st之間的距離和的比重；然后，再執行以下步驟：

(1)使用全集合路徑算法計算C(x,y,U),其中x,y∈U；

所述C(x,y,U)為狀態(x,y,X)的最優花費，狀態(x,y,X)表示一條從x出發、到y結束并且穿過集合X中所有節點的路徑，其中的且x,y∈X；

(2)當時，返回α×min_x∈U,y∈U(dist(s,x)+C(x,y,U)+dist(y,t))；

(3)求出從s到t的最短路徑P'；

(4)計算并賦值給best，該best為已經計算過的最優路徑的花費，而w(v_i,v_i+1)為節點v_i和v_i+1之間的邊上的權值；

(5)初始化隊列Q和集合D，將初始狀態和加入隊列Q，其中lb()是計算下界的操作，其結果lb是隊列Q的優先序；

(6)當隊列Q不為空時重復以下步驟：

(6.1)彈出隊列Q中第一個元素((label,v,X),cost,lb)；

(6.2)將label'標記為label的相反方向；

(6.3)X'為U-X；

(6.4)當v＝label'且X＝U的時候，返回當前的cost；

(6.5)將狀態((label,v,X),cost)加入集合D；

(6.6)對于集合E里的所有(v,u)邊循環：

(6.6.1)計算cost+α×w(v,u)并賦值給cost'，其中w(v,u)為邊(v,u)上的權值；

(6.6.2)更新(Q,D,best,label',X',(label,u,X),cost')；

(6.7)對于集合U-X里的所有x點循環:

(6.7.1)計算cost+(1-α)×dist(x,v)并賦值給cost'；

(6.7.2)更新(Q,D,best,label',X'-{x},(label,v,X∪{x}),cost')；

(7)所有上述循環結束還沒有找到最小花費，則返回∞。

2.如權利要求1所述的基于A星策略的最優多會合點路徑搜索方法，其特征在于，所述步驟(1)中，使用全集合路徑算法計算C(x,y,U)的方法為：

(A)初始化隊列Q和集合D，并對于所有的u∈U，將初始狀態((u,u,{u}),0)加入隊列Q；

(B)當隊列Q不為空時重復以下步驟：

(B.1)彈出隊列Q中第一個元素((x,y,X),cost)，其中cost表示狀態(x,y,X)的花費，狀態(x,y,X)表示從節點x出發，到達節點y，并且經過集合X中的所有節點的一條路徑，集合

(B.2)將cost賦值給狀態C(x,y,X)；

(B.3)將狀態(x,y,X)加入集合D；

(B.4)對于集合U-X里的所有點v循環：

(B.4.1)將集合X∪{v}賦值給臨時變量集合X”；

(B.4.2)將cost的值加上點v到點y的距離并賦值給臨時變量cost”；

(B.4.3)如果新的狀態(x,y,X”)存在于集合D中，則跳過本次循環繼續；

(B.4.4)如果新的狀態(x,y,X”)不屬于隊列Q，則將其加入隊列Q；

(B.4.5)如果臨時變量cost”比原來隊列Q中的相應狀態的cost要小，則更新隊列Q中該狀態的cost值。