[發明專利]基于反饋的自適應多約束的路徑搜索方法

有效

• 申請號: 201210118658.3
• 申請日: 2012-04-20
• 公開（公告）號: CN102664802A
• 公開（公告）日: 2012-09-12
• 發明（設計）人: 張大陸;匡增美;胡治國
• 申請（專利權）人: 同濟大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 上海光華專利事務所 31219
• 代理人: 李儀萍

1.一種基于反饋的自適應多約束的路徑搜索方法，其特征在于，所述基于反饋的自適應多約束的路徑搜索方法至少包括：

1)基于單源最短路徑算法搜索第一節點至第二節點的滿足第一加性約束條件的第一路徑；判斷所述第一路徑的第二加性約束是否滿足第二加性約束條件；若所述第一路徑的第二加性約束滿足第二加性約束條件，則結束搜索并將所述第一路徑作為第一節點至第二節點的可行路徑；反之，若所述第一路徑的第二加性約束不滿足第二加性約束條件時，則進入步驟2)；

2)基于單源最短路徑算法搜索所述第二節點至第一節點的滿足所述第二加性約束條件的第二路徑，判斷所述第二路徑的第一加性約束是否滿足第一加性約束條件；若所述第二路徑的第一加性約束滿足第一加性約束條件，則結束搜索并將所述第二路徑作為第一節點至第二節點的可行路徑；反之，若所述第二路徑的第一加性約束不滿足所述第一加性約束條件，則進入步驟3)；

3)基于所述第一路徑的第一加性約束、所述第二路徑的第二加性約束、預設的第一加性約束、預設的第二加性約束來確定搜索所述第一節點至第二節點之間的第三路徑的度量函數，以單源最短路徑算法來搜索所述第三路徑；在確定所述第三路徑同時滿足所述第一加性約束條件和所述第二加性約束條件的情形下，將所述第三路徑作為第一節點至第二節點的可行路徑。

2.根據權利要求1所述的基于反饋的自適應多約束的路徑搜索方法，其特征在于：若所述第一路徑與所述第二路徑中存在除第一節點和第二節點以外的至少一個共有節點，所述步驟3)還包括：

3-1)基于所述第一路徑的第一加性約束、所述第二路徑的第二加性約束、預設的第一加性約束、預設的第二加性約束來確定搜索所述第一路徑與第二路徑不重疊的共有節點之間的子路徑的第一加性約束的權重以及所述子路徑的第二加性約束的權重；

3-2)基于所述第一路徑與第二路徑不重疊的共有節點之間的子路徑的第一加性約束的權重和第二加性約束的權重所得到的度量函數以單源最短路徑算法來搜索所述子路徑，并用所述子路徑替換所述第一路徑和第二路徑中對應節點之間的路徑部分，以確定替換后的第一路徑或第二路徑是否同時滿足所述第一加性約束條件和所述第二加性約束條件；在確定替換后的第一路徑或第二路徑同時滿足所述第一加性約束條件和所述第二加性約束條件的情形下，將所述替換后的第一路徑或第二路徑作為第一節點至第二節點的可行路徑。

3.根據權利要求2所述的基于反饋的自適應多約束的路徑搜索方法，其特征在于：若所述替換后的第一路徑和第二路徑均不滿足所述第一加性約束條件和所述第二加性約束條件，所述步驟3)還包括：

基于替換后的第一路徑和第二路徑中最小的第一加性約束和最小的第二加性約束、以及預設的第一加性約束、預設的第二加性約束來重復步驟3-1)和步驟3-2)。

4.根據權利要求2或3所述的基于反饋的自適應多約束的路徑搜索方法，其特征在于：當搜索的每一條路徑都不能同時滿足第一加性約束條件和第二加性約束條件，所述基于反饋的自適應多約束的路徑搜索方法還包括：

步驟4)：基于各路徑中共有節點之間的每兩條子路徑的第一加性約束差值和第二加性約束差值的比值的絕對值進行排序，并基于排序結果來逐個交換所述兩條子路徑，直至確定交換后的路徑同時滿足所述第一加性約束條件和所述第二加性約束條件，并將同時滿足所述第一加性約束條件和所述第二加性約束條件的交換后的路徑作為第一節點至第二節點的可行路徑。

5.根據權利要求1所述的基于反饋的自適應多約束的路徑搜索方法，其特征在于：所述步驟1)還包括：

當基于單源最短路徑算法搜索以第一節點為起點的一條路徑的第一加性約束大于第一閾值，且該條路徑當前的最后一個節點并非所述第二節點時，終止沿該條路徑繼續搜索，并剪斷該條路徑當前的最后一個節點與其下一跳節點之間的路徑。

6.根據權利要求5所述的基于反饋的自適應多約束的路徑搜索方法，其特征在于：所述步驟2)還包括：

基于單源最短路徑算法從剪斷后的各節點路徑中搜索所述第二節點至第一起點的滿足所述第二加性約束條件的第二路徑，并確定所述第二路徑是否滿足所述第一加性約束條件。