[發(fā)明專利]基于可行循環(huán)流的多狀態(tài)網(wǎng)絡(luò)極小路向量搜索方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202211070001.4
• 申請(qǐng)日: 2022-08-29
• 公開(kāi)（公告）號(hào): CN115766494A
• 公開(kāi)（公告）日: 2023-03-07
• 發(fā)明（設(shè)計(jì)）人: 徐秀珍;牛義鋒;丁冬;宋祎璠;張媛媛;趙霞;吳國(guó)林
• 申請(qǐng)（專利權(quán)）人: 重慶郵電大學(xué)
• 主分類號(hào): H04L43/08
• 分類號(hào): H04L43/08
• 代理公司: 北京同恒源知識(shí)產(chǎn)權(quán)代理有限公司 11275
• 代理人: 方鐘苑

1.一種基于可行循環(huán)流的多狀態(tài)網(wǎng)絡(luò)極小路向量搜索方法，其特征在于，該方法包括以下步驟：

S1：確定極小路向量d-MP的搜索空間X；

S2：判定M(U)、M(L)與d的關(guān)系，其中，M(U)表示網(wǎng)絡(luò)G在X的上界容量向量U下的最大流量，M(L)表示網(wǎng)絡(luò)G在X的下界容量向量L下的最大流量，d表示容量需求；

S3：通過(guò)求解循環(huán)流問(wèn)題尋找d-MP；

S4：將搜索空間分解成若干個(gè)不相交的子集；

S5：在分解后的子集中繼續(xù)進(jìn)行搜索。

2.根據(jù)權(quán)利要求1所述的多狀態(tài)網(wǎng)絡(luò)極小路向量搜索方法，其特征在于，步驟S1具體包括：設(shè)網(wǎng)絡(luò)G的最大容量向量為W＝(W₁,W₂,…,W_m)，其中W_i表示邊e_i的最大容量，1≤i≤m，m表示邊的總數(shù)量；令L_i＝max{d-M(W(0_i)),0}(1≤i≤m)為邊e_i的下界容量，其中W(0_i)是將W的第i個(gè)分量設(shè)置為0時(shí)得到的容量向量，M(W(0_i))表示網(wǎng)絡(luò)G在W(0_i)下的最大流量；令U_i＝min{W_i,d}(1≤i≤m)為邊e_i的上界容量，則d-MP的搜索空間為X＝{x＝(x₁,x₂,…,x_m)|L_i≤x_i≤U_i，1≤i≤m}＝{x|L≤x≤U}＝[L,U]，其中，L＝(L₁,L₂,…,L_m)為X的下界容量向量，U＝(U₁,U₂,…,U_m)為X的上界容量向量，x_i為邊e_i的容量，x為容量向量。

3.根據(jù)權(quán)利要求2所述的多狀態(tài)網(wǎng)絡(luò)極小路向量搜索方法，其特征在于，步驟S2具體包括：如果M(U)d，搜索空間X中不存在極小路向量d-MP，算法停止；如果M(L)＝d，根據(jù)d-MP的定義，如果對(duì)于L的第i個(gè)分量大于0的所有i滿足M(L-0(e_i))d，則L是d-MP，其中，0(e_i)是單位向量，即0(e_i)的第i個(gè)分量為1，其他分量都為0，M(L-0(e_i))表示網(wǎng)絡(luò)G在L-0(e_i)下的最大流量，算法停止；否則進(jìn)行步驟S3。

4.根據(jù)權(quán)利要求3所述的多狀態(tài)網(wǎng)絡(luò)極小路向量搜索方法，其特征在于，步驟S3具體包括：在初始網(wǎng)絡(luò)G中添加一條從匯點(diǎn)t指向源點(diǎn)s的新邊e_m+1，得到一個(gè)新網(wǎng)絡(luò)G*，令邊e_m+1的容量為固定值d，即e_m+1的下界容量L_m+1和上界容量U_m+1都等于d，其他邊的下界容量和上界容量保持不變；利用最大流算法在新網(wǎng)絡(luò)G*中求解循環(huán)流問(wèn)題，如果不存在可行循環(huán)流，則搜索空間X中不存在d-MP，算法停止；否則，假設(shè)F^d＝(f₁^d,f₂^d,…,f_m^d,f_m+1^d)是求得的可行循環(huán)流，如果(f₁^d,f₂^d,…,f_m^d)不包含有向圈，則(f₁^d,f₂^d,…,f_m^d)是一個(gè)d-MP。