摘要： 针对不确定网络环境下的近邻查询问题,给出一种新的解决方法。将不确定网络建模为模糊图,定义模糊图中两点间的可信最短路径距离和可信最短路径期望距离,在可信距离基础上,提出模糊图可信近邻查询概念,并给出网络距离受限条件下的模糊图可信近邻查询算法和即时可信近邻查询算法。算法采用模糊模拟方法降低问题难度,使用网络距离约束缩小搜索空间,运用优先队列快速得到满足精度ε要求的可信近邻查询结果。算法的时间复杂度分别为O((2r+Δr)(e+nlgn)+hlgh+lgn)和O(e+(n+1)lgn)。理论分析与实验结果表明,可信近邻查询算法能够从模糊角度解决不确定网络环境下的近邻查询问题。

关键词: 不确定网络, 模糊图, 可信距离, 可信近邻, 模糊模拟, 距离约束

Abstract: This paper gives a new method for solving the problem of the nearest neighbor query in uncertain network.The method is that,gives the definition of credible shortest path distance and credible shortest path expectation distance,based on credible distance,puts forward the concept of fuzzy graph credible nearest neighbor query,and proposes fuzzy graph credible nearest neighbor query algorithm and instant credible nearest neighbor query algorithm on the condition of network distance constraint.The algorithm decreases the difficulty of the problem by using fuzzy analog,diminishes search space by using network distance constraint and quickly acquires the result of credible nearest neighbor query according to the precisionε by using the priority queue.The complexity of the algorithm is O((2r+Δr)(e+nlgn)+ hlgh+lgn) and O(e+(n+1)lgn).Theory analysis and experimental results show that fuzzy graph credible nearest neighbor query algorithm can solve the problem of the nearest neighbor query in uncertain network at the angle of fuzzy quality.

Key words: uncertain network, fuzzy graph, credible distance, credible nearest neighbor, fuzzy analog, distance constraint

中图分类号: 

• TP311.13