[發明專利]基于追趕法求解圣維南方程組的樹狀河網智能搜索方法

在審

• 申請號: 201710102631.8
• 申請日: 2017-02-24
• 公開（公告）號: CN107016048A
• 公開（公告）日: 2017-08-04
• 發明（設計）人: 雷曉輝;曾志強;楊明祥;蔣云鐘;王浩;權錦;劉珂;田雨;張云輝;蔡思宇;秦韜;謝明超;王遷
• 申請（專利權）人: 中國水利水電科學研究院
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙)11201
• 代理人: 廖元秋

1.一種基于追趕法求解圣維南方程組的樹狀河網智能搜索方法，其特征在于，包括以下步驟：

1)準備階段；在搜索開始前，進行三個方面的前期準備工作，包括：河網概化、有向圖編碼、鄰接矩陣生成；具體步驟如下：

1-1)河網概化；

將需要進行搜索的樹狀河網概化為由節點N和邊E組成的有向圖G，記為G＝(N,E)；有向圖G中，一條帶有箭頭的邊代表一個河段，箭頭的指向為河段水流的方向，每一條邊兩端都連接著一個節點，節點分為源節點SN、內節點IN和終節點EN三類；

1-2)有向圖編碼；

將步驟1-1)得到的有向圖G中的節點從0開始用自然數進行編碼，將邊所對應的兩端節點的編碼進行組合形成邊的編碼，有向圖中邊上箭尾所對應的節點編碼在前，箭頭所指向的節點編碼在后；

1-3)鄰接矩陣生成；

編碼后的節點用鄰接矩陣a_ij表示節點i和節點j的到達關系，i和j表示兩個節點的編碼：如果節點i和節點j為同一條邊ij上的兩個節點，且節點i到節點j的方向與箭頭方向同向，則表示節點i能夠達到節點j，記為鄰接矩陣a_ij＝1，否則為0；節點本身不能到達自己本身，即a_ii≡0；利用各節點的拓撲關系，構建出河網的鄰接矩陣，用鄰接矩陣a_ij表示節點i和節點j的到達關系如式(1)所示：

2)搜索路徑計算階段，具體包括以下步驟：

2-1)計算每個節點的出度和入度；

LD(i)表示節點i節的出度，ED(i)表示節點i的入度；如果某一節點j能夠到達i，即a_ji＝1，則節點i的入度ED(i)增加1；如果某一節點i能夠達j(j＝0,1,…,n)，即a_ij＝1，則節點i的出度LD(i)增加1；遍歷所有節點，計算得到每個節點的出度和入度；

2-2)對節點分類；

設置SN源節點、IN內節點、EN終節點和Sort四個集合；將滿足ED(i)＝0且LD(i)＝1的所有節點放入SN集合中；將滿足ED(i)＞0且LD(i)＝1的所有節點放入IN集合中；將滿足ED(i)＞0且LD(i)＝0的所有節點放入EN集合中；Sort集合用于存放搜索得到的邊的編碼；

2-3)在SN集合中任意選取一個節點i作為搜索的起始節點，并執行步驟2-4)；

2-4)根據條件對步驟2-3)選定的起始節點進行判定，選擇執行相應的步驟：如果搜索起始節點i∈SN或i∈IN且ED(i)＝0時，則執行步驟2-5)；如果搜索起始節點i∈IN且ED(i)≥1或節點i∈EN且ED(i)＞0時，則執行步驟2-6)；如果搜索起始節點i∈EN且ED(i)＝0時，則執行步驟2-8)；

2-5)循環遍歷所有節點，搜索起始節點i能夠到達的節點m，直到首次搜索到a_im＝1時則循環終止；如果搜索到的節點m∈EN且ED(m)＝0，則無節點返回，將邊mi所對應的編碼放入Sort集合中，并執行步驟2-8)；如果搜索到的節點m∈IN且ED(m)≥1或者m∈EN且ED(m)≥1，則將鄰接矩陣a_im置為0，同時將節點m的入度ED(m)減1，并將邊im所對應的編碼放入Sort集合中，返回節點m，執行步驟2-7)；

2-6)循環遍歷所有節點，搜索能夠達到搜索起始節點i的節點，直到首次搜索到節點k且a_ki＝1時則循環終止；返回節點k，執行步驟2-7)；

2-7)將返回得到的節點作為新的搜索起始點，重新返回步驟2-4)；

2-8)搜索結束，返回Sort集合，Sort集合中按先后順序依次排列所得到的邊的編碼，即為搜索得到的路徑。