[發明專利]一種單位圓盤圖上的最大獨立集近似求解方法在審
| 申請號： | 201910659827.6 | 申請日： | 2019-07-22 |
| 公開（公告）號： | CN110489804A | 公開（公告）日： | 2019-11-22 |
| 發明（設計）人： | 宋洪濤;韓啟龍;張立國;張可佳;盧丹;崔寰宇;劉鵬 | 申請（專利權）人： | 哈爾濱工程大學 |
| 主分類號： | G06F17/50 | 分類號： | G06F17/50 |
| 代理公司： | 暫無信息 | 代理人： | 暫無信息 |
| 地址： | 150001 黑龍江省哈爾濱市南崗區*** | 國省代碼： | 黑龍;23 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 單位圓盤 近似 最大獨立集 判斷結果 相鄰頂點 誘導子 最優解 求解 計算時間復雜度 動態規劃 近似算法 求解問題 近似解 并集 優化 檢查 聯合 | ||
1.一種單位圓盤圖上的最大獨立集近似求解方法，其特征在于，該方法包括以下步驟：
步驟1：若頂點v的相鄰頂點集為V＝{v1,v2…vn}，將x軸穿過頂點，V中的所有頂點都在寬度為2的窄條內；
步驟2：將步驟1中所述窄條等分成a區、b區、c區和d區四個區域，從而將V集合進行劃分，將不同區域中的頂點按x坐標進行排序，得到V中頂點在不同區域中的子集；
步驟3：對于V中任意一個頂點vi，定義不同區域內在vi左側且與vi不相鄰的最右側的頂點；
步驟4：定義S(ka,kb,kc,kd)是頂點集，其中0≤ka≤vka；0≤kb≤vkb；0≤kc≤vkc；0≤kd≤vkb；vka,vkb，vkc和vkd是定點集S(ka,kb,kc,kd)中在對應區域中的最右側的頂點；
步驟5：定義求解S(ka,kb,kc,kd)中頂點誘導子圖的最大頂點獨立集為一個子問題，其中最優解為Iopt(S)，最優解成員數量為Lopt(S)；
步驟6：構造遞歸函數。
2.根據權利要求1所述的一種單位圓盤圖上的最大獨立集近似求解方法，其特征在于，步驟3所述的定義不同區域內在vi左側且與vi不相鄰的最右側的頂點，包括以下步驟：
步驟3.1：將V中的頂點進行編號，另頂點支配獨立集S初始值為集合{v1}；
步驟3.2：對V-S中的頂點與S中的頂點進行依次判斷，若當前頂點在S中不存在臨點，那么將該頂點添加到S中，直至判斷完所有點。
3.根據權利要求1所述的一種單位圓盤圖上的最大獨立集近似求解方法，其特征在于，步驟4所述的定義求解S(ka,kb,kc,kd)中頂點誘導子圖的最大頂點獨立集包括以下步驟：
步驟4.1：計算頂點獨立集；
步驟4.2：成員單獨檢查，判斷結果是否能優化，若能繼續優化則繼續進行步驟2，若不能優化則得到中間解并進入步驟3；
步驟4.3：成員聯合檢查，判斷結果是否能優化，若能繼續優化則繼續進行步驟3，若不能優化則得到最終解。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于哈爾濱工程大學，未經哈爾濱工程大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201910659827.6/1.html，轉載請聲明來源鉆瓜專利網。
