[發(fā)明專利]求解無向帶權(quán)圖最小割的安全外包方法有效
| 申請?zhí)枺?/td> | 201811342195.2 | 申請日： | 2018-11-12 |
| 公開（公告）號： | CN109409116B | 公開（公告）日： | 2022-01-28 |
| 發(fā)明（設(shè)計）人： | 于佳;郝蓉;趙譜 | 申請（專利權(quán)）人： | 青島大學(xué) |
| 主分類號： | G06F21/60 | 分類號： | G06F21/60 |
| 代理公司： | 北京華仁聯(lián)合知識產(chǎn)權(quán)代理有限公司 11588 | 代理人： | 蘇雪雪 |
| 地址： | 266071 山*** | 國省代碼： | 山東;37 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 求解 帶權(quán)圖 最小 安全 外包 方法 | ||
1.一種求解無向帶權(quán)圖最小割的安全外包方法，其特征在于，包括：
第一步，盲化，具體包括第1.1步，隨機選取G中的一個頂點添加到集合A中，集合A初始為空，然后遍歷圖G中不屬于集合A的頂點，將使得成立的頂點添加到集合A中，其中w(A，y)是指集合A中的頂點和頂點y之間所有邊的權(quán)值之和，重復(fù)上述過程，直到將G中所有頂點都添加到集合A中，記錄下將最后一個加入到集合A中的頂點割離圖G的割以及這個割權(quán)值，然后將最后兩個添加到集合A中的頂點合并，合并兩個頂點是指將這兩個頂點之間的邊刪除，然后將原本連接到這兩個頂點的邊都連接到由這兩個頂點合并而成的新頂點上；
第1.2步，重復(fù)執(zhí)行第1.1步rt次，這里rt＝(1/2)·log2|V|次，得到一個較小規(guī)模的圖Gs，同時將其中記錄下來的割中權(quán)值最小的割記作Mp；
第1.3步，再重復(fù)第1.1步log2|V|-rt次，再將這些輪次合并中記錄下來的權(quán)值最小的割的權(quán)值記為ws，得到的更小規(guī)模的圖無需保存；
第1.4步，初始化一個保存父頂點與子頂點關(guān)系的字典D，然后遍歷Gs中的所有邊，在遍歷的過程中首先判斷當(dāng)前遍歷的邊中的兩個頂點是否有子頂點，如果沒有，那么就隨機選取一個頂點v作為父頂點，為其添加一個子頂點v′，并記錄到字典D中，之后在父子頂點之間添加一條邊，這條邊的權(quán)值要大于第1.3步中的ws，如果當(dāng)前遍歷的邊中的兩個頂點至少有一個有子頂點，那么什么也不做，之后，設(shè)遍歷到的當(dāng)前邊為a，b，a有子頂點a′，將a，b的權(quán)值減小re，再添加一條權(quán)值為re的新邊a′，b，遍歷完成之后，得到圖Gd；
第1.5步，初始化一個由到的隨機置換π，為圖Gd中的所有點構(gòu)成的集合，然后將Gd中的任一頂點u都重命名為π(u)；
第1.6步，對Gd中的所有邊的權(quán)值都乘上一個隨機實數(shù)r，得到G′；
第二步，計算，具體為用戶將G′發(fā)送給云服務(wù)器，請求云服務(wù)器求出G′的最小割，云服務(wù)器求出的最小割用M1表示，之后云服務(wù)器將M1發(fā)送給用戶；
第三步，驗證，具體為用戶收到M1之后，對第一步的步驟1.6、1.5、1.4分別求逆：把圖G′中所有邊的權(quán)值都除以r，用隨機置換π的逆置換復(fù)原所有頂點，再合并字典D中所有對應(yīng)的父子頂點，通過上述操作可以從M1中恢復(fù)出Gs的最小割Ms，求出Gs最小割之后，遍歷所有Ms中的邊，將每條邊的權(quán)值減小rs，rs是遠(yuǎn)小于當(dāng)前邊權(quán)值的一個隨機數(shù)，每條邊權(quán)值減小的量都不同，每條Ms中的邊減小權(quán)值的總量記為d，即所有rs的和為d，之后，再將不在Ms中的每條邊的權(quán)值增大ri，ri是遠(yuǎn)小于當(dāng)前邊權(quán)值的一個隨機數(shù)，每條邊權(quán)值增加的量都不同，對Gs做上述修改得到Gs′后，再對Gs′重復(fù)盲化過程中的步驟1.4、1.5、1.6得到新圖G″，生成圖G″的過程中用到的字典、隨機置換、隨機實數(shù)分別為D′、π′以及r′，用戶將G″發(fā)送給云服務(wù)器，請求云服務(wù)器求出G″的最小割，云服務(wù)器求出的最小割用M2表示，之后云服務(wù)器將M2發(fā)送給用戶，用戶收到服務(wù)器返回的M2之后，用和恢復(fù)Ms的手段從M2中恢復(fù)出Gs′的最小割Ms′，之后驗證w(Ms)-d＝w(Ms′)是否成立，其中w(Ms)表示Ms的權(quán)值，如果相等，云服務(wù)器的響應(yīng)通過驗證，否則，用戶指控云服務(wù)器存在不誠實行為；
第四步，求解，具體為用戶比較w(Mp)和w(Ms)的大小，如果前者較小，那么Mp即為原圖的最小割M，如果后者較小，那用戶拆分生成Gs時合并的所有頂點，最終由Ms恢復(fù)出原圖的最小割M。
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于青島大學(xué)，未經(jīng)青島大學(xué)許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201811342195.2/1.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
