[發明專利]一種基于貪心策略的群智感知參與者選擇方法

有效

• 申請號: 201611189560.1
• 申請日: 2016-12-21
• 公開（公告）號: CN106599254B
• 公開（公告）日: 2019-11-12
• 發明（設計）人: 於志勇;郭文忠;郭龍坤;周杰
• 申請（專利權）人: 福州大學
• 主分類號: G06F16/29
• 分類號: G06F16/29;G07C1/10
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

1.一種基于貪心策略的群智感知參與者選擇方法，其特征在于：包括以下步驟：

步驟S1：通過原始數據庫，獲取每個用戶在各個周期所覆蓋的目標點的集合；步驟S2：利用貪心策略選取一個用戶集，保證目標點在第一個覆蓋周期滿足覆蓋要求；步驟S3：用步驟S2中得到的用戶集來對下一個覆蓋周期進行覆蓋，記錄各點的覆蓋次數情況；步驟S4：對步驟S3中未滿足覆蓋次數要求的點，繼續用貪心策略選取用戶，加入到原來的用戶集，直到所有點都滿足覆蓋次數要求；步驟S5：返回步驟S3，重復步驟S3和S4中的步驟，直到最后一個覆蓋周期也滿足覆蓋要求。

2.根據權利要求1所述的一種基于貪心策略的群智感知參與者選擇方法，其特征在于：所述步驟S1中構建用戶與目標點的覆蓋關系集合的操作過程為：

步驟S101：以每個周期所限定的時間與目標地點作為查詢條件，連接并讀取原始數據庫，獲取原始用戶和地點信息

步驟S102：根據步驟S101中得到的查詢結果信息，構建用戶與目標地點覆蓋關系矩陣，具體操作為：

先將讀取的原始數據進行格式轉換，即cur1 = cell2mat(cur1)，以便后續操作，cur1為獲取cell型原始數據；然后對給定的目標地點編號為1,2,...,h，對用戶編號為1,2,...,n，逐行讀取上述數據，并構建矩陣：

M{i}(ipp,u) = 1，

即某用戶覆蓋過某個點，則將相應位置為1；其中，i表示第i個周期，ipp為目標地點編號（1,2,...,h）,u為用戶編號（1,2,...,n）；

步驟S103：根據步驟S102中建立的用戶與目標地點覆蓋關系矩陣，得到用戶與目標地點覆蓋關系集合，具體操作為：

遍歷步驟S102中得到的矩陣，對于某個指定用戶，他若覆蓋過某個地點，則將該地點的編號加入相應的集合中，每個用戶所覆蓋的目標點集合用元胞數組cell的結構來存儲，即：

ce(i){t2}(count)=s2，

其中i為周期，t2、s2為循環變量，表示用戶和地點編號，count為累加變量。

3.根據權利要求1所述的一種基于貪心策略的群智感知參與者選擇方法，其特征在于：所述步驟S2中選取第一個用戶集來滿足覆蓋要求的操作過程為：

步驟S201：對步驟S1中得到的所有集合按照集合大小遞減的順序將相應的用戶編號，即集合編號，存入數組中，即s{i}(t)=i2，s為元胞數組，i為周期變量，i2為集合編號變量，t為累加變量；

步驟S202：依次選取數組s中的用戶加入到目標用戶集U和記錄被選用戶的數組b中，同時遍歷步驟S1中的覆蓋關系集合，對覆蓋次數矩陣B進行更新，即：

B(ce{h(f)}(i2)) = B(ce{h(f)}(i2)) + 1；

遍歷數組B，查看每個地點的覆蓋次數，若有地點的覆蓋次數達到要求，即B(i)=K，則將該地點編號存入數組a中，同時更新目標地點數，cn=cn-1；

步驟S203：若cn=0，則進入步驟S3，覆蓋下一周期；否則，遍歷覆蓋關系集合，利用數組b和數組a，求出暫時未被選中的用戶覆蓋剩余那些不滿足覆蓋要求的點的情況，并記錄這些用戶所覆蓋地點的數量，存入數組inc中，即每覆蓋一個點，便進行inc(f) = inc(f) + 1操作，其中inc(f)記錄編號為f的用戶覆蓋剩余地點的個數；

步驟S204：遍歷inc數組，取出其中的最大值對應的用戶編號f，加入到目標集合U中，同時更新數組b、數組a和數組B；

當所有地點均滿足覆蓋條件B(i)>=k時，所得到的用戶集即為所求。