• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      不確定隨機(jī)網(wǎng)絡(luò)Top-k最近節(jié)點(diǎn)查詢算法

      2018-10-23 05:38:48連春月李孝忠牛浩浩
      關(guān)鍵詞:測度機(jī)會權(quán)重

      連春月,李孝忠,牛浩浩

      (天津科技大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院,天津 300457)

      實(shí)際生活中,會遇到許多非確定的現(xiàn)象.為了研究這類非確定的現(xiàn)象,17世紀(jì)誕生了概率論.概率論基于大量的歷史數(shù)據(jù),有效解決了很多統(tǒng)計(jì)問題.但是,有時(shí)因?yàn)楦鞣N原因無法獲得足夠多的數(shù)據(jù),這時(shí)使用概率論解決問題就很難辦到.為了解決這類問題,Liu B于2007年提出了不確定理論[1],并于2010年對不確定理論進(jìn)行重新定義[2],為小樣本數(shù)據(jù)、甚至是無樣本數(shù)據(jù)的統(tǒng)計(jì)提供了新的理論基礎(chǔ).

      經(jīng)過多年研究與實(shí)踐,不確定理論得到了充分的發(fā)展與廣泛的應(yīng)用.2013年,高原[3]詳細(xì)研究了不確定網(wǎng)絡(luò)的最短路徑問題;2014年,Zhou等[4]研究了不確定網(wǎng)絡(luò)的最短路徑的逆不確定分布問題;2015年,Zhou等[5]給出了不確定網(wǎng)絡(luò)的最小生成樹的路徑最優(yōu)條件.

      對于一個(gè)復(fù)雜網(wǎng)絡(luò),某些弧的權(quán)重可以通過對歷史數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析得到,而某些弧由于沒有歷史數(shù)據(jù)或者歷史數(shù)據(jù)無效,導(dǎo)致其權(quán)重不能通過概率統(tǒng)計(jì)得到,只能利用專家的經(jīng)驗(yàn)數(shù)據(jù),得到不確定弧的權(quán)重的不確定分布函數(shù).

      2013年,為了解決這類既有非確定因素,又有不確定因素的現(xiàn)象,Liu Y[6]開創(chuàng)了機(jī)會理論.2014年,Liu B[7]首次將機(jī)會理論引入不確定網(wǎng)絡(luò),提出不確定隨機(jī)網(wǎng)絡(luò)的概念.2015年,盛玉紅[8]對不確定隨機(jī)網(wǎng)絡(luò)的最短路徑問題、最小生成樹問題和最大流問題進(jìn)行研究,提出理想機(jī)會分布函數(shù)的概念并利用其求解了上述問題.

      關(guān)于非確定性數(shù)據(jù)的Top-k查詢問題,學(xué)者們提出了各種計(jì)算方法,包括U-topK[9]、U-kRanks[10],PT-k[11],Global-topK[12]等.Li 等[13]提出了基于權(quán)值參數(shù)的排名函數(shù),實(shí)現(xiàn)了排名分值與概率平衡.2016年,郭長友等[14]首次將不確定理論應(yīng)用到不確定數(shù)據(jù)的Top-k查詢計(jì)算中.

      非確定數(shù)據(jù)的 Top-k查詢在 P2P系統(tǒng)、電纜鋪設(shè)等方面已經(jīng)有了實(shí)際應(yīng)用,但不確定數(shù)據(jù)和隨機(jī)數(shù)據(jù)同時(shí)存在的Top-k查詢方面的研究并不多.本文基于現(xiàn)有研究成果,將包含不確定數(shù)據(jù)和隨機(jī)數(shù)據(jù)的問題轉(zhuǎn)化為不確定隨機(jī)網(wǎng)絡(luò),并在深度優(yōu)先遍歷的算法上,提出在一定機(jī)會測度的情況下,尋找距離某個(gè)節(jié)點(diǎn)最近的k個(gè)節(jié)點(diǎn)的算法,能有效解決在經(jīng)驗(yàn)數(shù)據(jù)和小樣本數(shù)據(jù)混雜情況下的節(jié)點(diǎn)查詢問題.

      1 相關(guān)概念

      1.1 不確定理論[1]

      定義1設(shè)Γ為非空集合,L是Γ上的σ-代數(shù),任意的Λ∈L稱為一個(gè)事件.如果從L到實(shí)數(shù)集R的集函數(shù)M滿足以下條件:

      公理 1(規(guī)范性) 對于全集Γ,有M{Γ}=1;

      公理 2(對偶性) 對于任意的事件Λ∈L,有M{Λ}+M{Λc}=1;

      公理 3(次可列可加性) 對于可數(shù)的事件序列M{Λ},有

      則稱集函數(shù) M 為Γ上的不確定測度,三元組(Γ,L, M)稱為一個(gè)不確定空間.

      為了研究乘積空間上的不確定測度,Liu B提出了乘積公理[1]:

      公理 4設(shè)(Γi,Li,Mi)為一列不確定空間,則乘積不確定測度M為

      不確定變量的定義是由抽象的不確定空間和Borel集描述的.如果僅從定義出發(fā),在理解和應(yīng)用不確定變量時(shí)都會遇到困難,為了更好地理解不確定變量,給出如下不確定分布的概念.

      定義 4若不確定變量ξ具有不確定分布

      其中 a和 b為常數(shù),則ξ為線性的不確定變量,記為L( a, b).

      定義 5若對于任意的 α∈ (0,1),不確定變量ξ的不確定分布Φ(x)的反函數(shù) Φ-1(α)存在且唯一,則稱Φ(x)為正則分布,稱ξ為正則不確定變量.

      定義 6若不確定變量ξ具有正則分布Φ(x),則其反函數(shù)Φ-1(α)稱為ξ的逆不確定分布.

      例 1根據(jù)定義 4—定義 6,線性不確定變量L( a, b)的逆不確定分布為

      1.2 機(jī)會理論[6]

      定義 7設(shè)(Γ,L,M)× (Ω,A, Pr)是一個(gè)機(jī)會空間,Θ是L×A的一個(gè)事件,那么事件Θ的機(jī)會測度為

      定義 8從機(jī)會空間(Γ ,L ,M )× (Ω,A, Pr)到實(shí)數(shù)集 R的可測函數(shù)ξ稱為不確定隨機(jī)變量,即對于任意的Borel實(shí)數(shù)集Β,集合

      是L×A中的一個(gè)事件.定義 9設(shè) f:Rn→R是一個(gè)可測函數(shù),ξ1,ξ2,…,ξn是機(jī)會空間(Γ,L,M)×(Ω,A, Pr)上的一列不確定隨機(jī)變量,那么對任意的(γ,ω)∈?!力?,ξ=f(ξ1,ξ2,…,ξn)是由

      所確定的一個(gè)不確定隨機(jī)變量.

      定義10η1,η2,…,ηm是一系列獨(dú)立的隨機(jī)變量,概率分布分別為Ψ1,Ψ2,…,Ψm,τ1,τ2,…,τn是一列不確定變量,不確定分布分別為?1,?2,… ,?n,那么不確定隨機(jī)變量

      有一個(gè)機(jī)會分布

      其中,對任意的實(shí)數(shù)y1, y2,…,ym,F(xiàn)(x, y1,y2,…,ym)是不確定變量f(η1,η2,…,ηm,τ1,τ2,…τn)的不確定分布,它可由其反函數(shù)F-1(α;y, y,…,y)=f(y,y,…,12m12y,?-1(α) ,?-1(α),…,?-1(α))決定,條件是f為對于m12nτ1,τ2,…,τn的單增函數(shù).

      例 2設(shè)η是一個(gè)隨機(jī)變量,其概率分布為Ψ,τ是一個(gè)不確定變量,其不確定分布為?.那么,ξ= η+ τ是一個(gè)不確定隨機(jī)變量,ξ的機(jī)會分布為

      其中,y是隨機(jī)變量η的任一實(shí)現(xiàn).

      2 不確定隨機(jī)網(wǎng)絡(luò)下的Top-k查詢算法

      2.1 不確定隨機(jī)網(wǎng)絡(luò)

      N是節(jié)點(diǎn)集合,U是不確定弧的集合,R是隨機(jī)弧的集合,W 是不確定權(quán)重和隨機(jī)權(quán)重的集合,那么四元組(N,U,R,W)被稱為一個(gè)不確定隨機(jī)網(wǎng)絡(luò).

      例3圖1是有4個(gè)節(jié)點(diǎn)的不確定隨機(jī)網(wǎng)絡(luò).其中,隨機(jī)權(quán)重ηAB、ηCD的概率分布分別為ΨAB、ΨCD.不確定權(quán)重τBC具有正則的不確定分布?BC.各邊的權(quán)重的分布函數(shù)見表1.

      圖1 4節(jié)點(diǎn)不確定隨機(jī)網(wǎng)絡(luò)Fig. 1 Uncertain random network with 4 nodes

      表1 圖1網(wǎng)絡(luò)中各邊的權(quán)重的分布函數(shù)Tab. 1 Distribution function of the edge’s weight of figure 1

      ΨAB,ΨCD的概率分布函數(shù)分別為

      ?BC的不確定分布為

      則權(quán)重的機(jī)會分布函數(shù)為

      計(jì)算可得

      假設(shè)機(jī)會測度Φ (x) =0.95,計(jì)算得權(quán)重x=25.7.

      2.2 Top-k最近節(jié)點(diǎn)查詢算法

      給定不確定隨機(jī)網(wǎng)絡(luò)G,節(jié)點(diǎn)間的權(quán)重的機(jī)會分布函數(shù)為Φ,則節(jié)點(diǎn)間的路徑長度機(jī)會分布函數(shù)D=Φ,即將節(jié)點(diǎn)間的權(quán)重建模為節(jié)點(diǎn)間的路徑長度.基于節(jié)點(diǎn)間的路徑長度,提出以下的不確定隨機(jī)網(wǎng)絡(luò)Top-k最近節(jié)點(diǎn)查詢算法.

      輸入:不確定隨機(jī)網(wǎng)絡(luò) G=(N,U,R,W),選擇的最近節(jié)點(diǎn)個(gè)數(shù)k,初始節(jié)點(diǎn)p,機(jī)會測度α.

      輸出:當(dāng)機(jī)會測度為α?xí)r,與 p最近的k個(gè)節(jié)點(diǎn),以及對應(yīng)路徑.

      具體算法如下:

      (1)計(jì)算所有節(jié)點(diǎn)間 i,j間的路徑,初始節(jié)點(diǎn)為:i=1,j=2,并將 i標(biāo)記為已訪問;

      (2)從N中取出非i節(jié)點(diǎn)k,若兩點(diǎn)間有路徑,將k標(biāo)記為已訪問;

      (3)若k=j(luò),將所有已訪問節(jié)點(diǎn)組成的路徑放入路徑集合D中,回溯至上一個(gè)已訪問節(jié)點(diǎn),重復(fù)步驟(2);否則,重復(fù)步驟(2);

      (4)若 k≥n,j++,重復(fù)步驟(1)—(3),直至 j=n;

      (5)若 j>n,j- -,i++,重復(fù)步驟(1)—(4),直至 i=n;

      (6)計(jì)算D中所有路徑的機(jī)會分布函數(shù);

      (7)計(jì)算當(dāng)機(jī)會測度為α?xí)r,點(diǎn) p到所有節(jié)點(diǎn)的路徑長度;

      (8)找到距離點(diǎn) p最近的k個(gè)點(diǎn)及對應(yīng)路徑,算法結(jié)束.

      算法中步驟(2)—(3)部分的代碼如下:

      function FindPath(matrix,startNode,endNode){

      result[nPos]=startNode.key;//將當(dāng)前節(jié)點(diǎn)放入結(jié)果集

      Mark[startNode.key]=true;//標(biāo)記為已訪問nPos++;

      while(nPos !=0){

      var tempVal=result[nPos-1];//獲取結(jié)果集最后

      一個(gè)元素

      if(tempVal==endNode.key){//如果當(dāng)前節(jié)點(diǎn)為

      結(jié)束節(jié)點(diǎn),將結(jié)果集中的節(jié)點(diǎn)放入路徑結(jié)果集中

      for(let j=0;j<nPos;j++){

      resultPath[pathNum][j]=result[j];

      }

      nPos- -;//回溯至目標(biāo)節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)

      result[nPos]=0;

      pathNum++;//新增路徑數(shù)目

      Mark[endNode.key]=false;

      break;

      };

      while(startNode.flag<matrix.length){

      if(matrix[tempVal][startNode.flag]==1){

      if(Mark[startNode.flag]==false){

      var tempNode=new Node();

      tempNode.key=startNode.flag;

      tempNode.flag=0;

      FindPath(matrix,tempNode,endNode);

      }

      }

      startNode.flag++;

      }

      if(startNode.flag==matrix.length){

      nPos- -;

      startNode.flag=0;

      Mark[startNode.key]=false;

      break;

      }

      }

      為了更好地理解算法,用例4進(jìn)行簡要說明.

      例 4有 5個(gè)節(jié)點(diǎn)的不確定隨機(jī)網(wǎng)絡(luò),如圖 2所示.其中τAB、τBD、τDE是不確定權(quán)重,且分別具有正則的不確定分布?AB、?BD、?DE;ηAE、ηBC、ηCD是隨機(jī)權(quán)重,分別具有概率分布ΨAE、ΨBC、ΨCD,網(wǎng)絡(luò)中各邊的權(quán)重的分布函數(shù)見表 2.求距離節(jié)點(diǎn) A最近的3個(gè)節(jié)點(diǎn).

      圖2 5節(jié)點(diǎn)不確定隨機(jī)網(wǎng)絡(luò)Fig. 2 Uncertain random network with 5 nodes

      表2 圖2網(wǎng)絡(luò)中各邊的權(quán)重的分布函數(shù)Tab. 2 Distribution function of the edge’s weight of figure 2

      能夠得到任意兩點(diǎn)間的路徑長度機(jī)會分布函數(shù)

      其中F( x,yij,(i,j)∈R)由它的逆不確定分布確定:

      當(dāng)機(jī)會測度α=0.9時(shí),計(jì)算出任意兩點(diǎn)間的最小路徑長度,計(jì)算結(jié)果見表3.

      表3 α=0.9時(shí)節(jié)點(diǎn)間路徑長度Tab. 3 Path length between nodes when α=0.9

      當(dāng)機(jī)會測度α=0.8時(shí),計(jì)算出任意兩點(diǎn)間的最小路徑長度,計(jì)算結(jié)果見表4.

      表4 α=0.8時(shí)節(jié)點(diǎn)間路徑長度Tab. 4 Path length between nodes when α=0.8

      所以,當(dāng)機(jī)會測度α=0.9,k=3時(shí),距離節(jié)點(diǎn)A最近的 3個(gè)點(diǎn)分別為 E、B、C.當(dāng)機(jī)會測度α=0.8,k=3時(shí),距離節(jié)點(diǎn)A最近的3個(gè)點(diǎn)分別為E、B、D.

      當(dāng)機(jī)會測度變化時(shí),查詢到的最短路徑節(jié)點(diǎn)也可能發(fā)生變化,所以需要根據(jù)現(xiàn)實(shí)需求來指定機(jī)會測度,以得到預(yù)期結(jié)果.

      3 結(jié) 語

      本文提出了不確定隨機(jī)網(wǎng)絡(luò)的 Top-k最近節(jié)點(diǎn)查詢問題,并使用機(jī)會理論求解該問題,設(shè)計(jì)不確定隨機(jī)網(wǎng)絡(luò)在一定機(jī)會測度條件下的 Top-k查詢算法.此算法能正確求解不確定隨機(jī)網(wǎng)絡(luò)的Top-k查詢問題,在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目較小、不確定隨機(jī)分布較簡單時(shí)的效率較高;一旦網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目眾多、網(wǎng)絡(luò)非常復(fù)雜時(shí),則計(jì)算的時(shí)間復(fù)雜度會較高.如何對算法進(jìn)行改進(jìn),以提高算法的計(jì)算效率是下一步的研究方向.

      猜你喜歡
      測度機(jī)會權(quán)重
      三個(gè)數(shù)字集生成的自相似測度的乘積譜
      R1上莫朗測度關(guān)于幾何平均誤差的最優(yōu)Vornoi分劃
      權(quán)重常思“浮名輕”
      非等熵Chaplygin氣體測度值解存在性
      Cookie-Cutter集上的Gibbs測度
      給進(jìn)步一個(gè)機(jī)會
      海峽姐妹(2020年3期)2020-04-21 09:27:40
      最后的機(jī)會
      NBA特刊(2018年17期)2018-11-24 02:45:44
      為黨督政勤履職 代民行權(quán)重?fù)?dān)當(dāng)
      給彼此多一次相愛的機(jī)會
      海峽姐妹(2018年6期)2018-06-26 07:27:20
      沒機(jī)會下手
      厦门市| 宕昌县| 平凉市| 乐东| 闸北区| 平果县| 华安县| 永年县| 兴国县| 水城县| 安平县| 嵊泗县| 肇庆市| 开鲁县| 巨鹿县| 广丰县| 通榆县| 柳江县| 同仁县| 醴陵市| 梅河口市| 司法| 休宁县| 平顺县| 邛崃市| 车险| 鲜城| 木兰县| 平舆县| 丰顺县| 宾川县| 长阳| 拜泉县| 广州市| 仁化县| 新郑市| 逊克县| 临武县| 三门县| 尼木县| 中江县|