[發明專利]一種基于改進Dijkstra算法的景區路徑選擇方法及系統

在審

• 申請號: 201711385952.X
• 申請日: 2017-12-20
• 公開（公告）號: CN108256669A
• 公開（公告）日: 2018-07-06
• 發明（設計）人: 王瑾;梁晴晴;曾福江;吳讓仲;張曉鋒
• 申請（專利權）人: 中國地質大學（武漢）
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/26;G01C21/20
• 代理公司: 武漢知產時代知識產權代理有限公司 42238
• 代理人: 馮必發

1.一種基于改進Dijkstra算法的景區路徑選擇方法，其特征在于，包含下述步驟：

S1、獲取景區路徑模型，該景區路徑模型包含將岔路口作為節點的節點之間的各個選擇因素的權值，選擇因素包括路徑距離、擁擠度、用戶偏好度、交通方式及路徑通過時間；

S2、計算景區路徑模型各個節點之間的綜合權值，其中任意節點p與q之間的綜合權值通過下述公式計算所得：

f＝ω₁×f₁+ω₂×f₂+…+ω_n×f_n，

式中，f表示綜合權值，n表示選擇因素的總個數，f₁、f₂、…及f_n分別為節點p與節點q之間的各個因素的權值，ω₁、ω₂、…及ω_n分別為f₁、f₂、…及f_n對應的權重；

S3、以綜合權值替換Dijkstra算法中的相應路徑距離的權值來進行改進Dijkstra算法的運算，選擇出一條總的綜合權值最小的路徑。

2.根據權利要求1所述的景區路徑選擇方法，其特征在于，步驟S1中獲取景區路徑模型具體包括：

通過問卷調查的方式獲取用戶的景觀類型偏好，根據用戶的景觀類型偏好，計算出節點間用戶偏好度權值，其中用戶對某種的景觀類型偏好越高，對應的權值越小；和/或，

通過問卷調查的方式獲取用戶的交通方式偏好，根據用戶的交通方式偏好，計算出節點間交通方式偏好權值，其中用戶對某種的交通方式偏好越高，對應的權值越小；和/或

通過問卷調查的方式獲取用戶的擁擠度允許程度、景點內欲旅游路線總距離、景點內欲旅游時間總時長中一種或者多種作為所述景區路徑模型進行路徑選擇時的約束條件。

3.根據權利要求1所述的景區路徑選擇方法，其特征在于，第k個選擇因素的歸一化后的權重通過下述公式得到：

式中，k＝1、2、…、n，S_k是利用1～9級判斷矩陣標準度，分別求出第k個選擇因素分別相對于所有的選擇因素的矩陣標準度的值，然后將該選擇因素所有的矩陣標準度的值相加所得到的和。

4.根據權利要求3所述的景區路徑選擇方法，其特征在于，還包括下述步驟：

在利用1～9級判斷矩陣標準度進行處理之前，響應用戶的設置，更新各個選擇因素的優先級。

5.根據權利要求3所述的景區路徑選擇方法，其特征在于，路徑距離的權重為ω₁＝0.503，景點擁擠度的權重為ω₂＝0.26，用戶偏好度ω₃＝0.134，交通方式的權重為ω₄＝0.068，時間權值ω₅＝0.035。

6.根據權利要求3所述的景區路徑選擇方法，其特征在于，各個選擇因素的權重的得到過程中，還包括步驟：通過對歸一化后的權重進行一致性判斷來檢驗計算得到的歸一化后的權重是否符合權值類型之間的實際重要性，若是，則將本次計算的權重作為權重的最終值，否則，獲取重新選取矩陣標準度的值來計算權重；

進行一致性判斷的方法如下：

判斷的值是否小于0.1，若是則符合一致性，否則不符合一致性；

其中，R.I.等于平均隨機一致性表中n階矩陣的值，λ_max是判斷矩陣的最大特征根，判斷矩陣的第i行的第j列的元素為第i個選擇因素相對于第j個選擇因素的矩陣標準度的值，i＝1、2、…、n，j＝1、2、…、n。