Abstract:
The problem of k Obstructed Globally Different Optimal Sequenced Route(kOGDOSR) query is proposed. The approximate algorithm for resolving this query problem is put forward based on visibility graph. The introduction of effect set and obstructed angle point reduces the number of obstacles used in the configuration of visibility graph. It decreases the number of inner obstructed route calculations through analyzing the relationship between the line segment from query point to data point and the vertices and arcs of the visibility graph. The algorithm is optimized completely through the two aspects described above. Experimental results indicate that the algorithm presented has a better performance.
Key words:
k Obstructed Globally Different Optimal Sequenced Route(kOGDOSR),
effect set,
obstructed angle point,
visibility graph,
approximate algorithm
摘要： 提出障碍k全局相异最优有序路径的查询问题，利用可视图的思想给出近似查询算法，通过作用集与障碍角度点的引入有效地减少构造可视图障碍对象的数量，分析查询点和数据点构成的线段与可视图的顶点和弧的关系，减少内部障碍路径的计算次数，实现算法的全面优化。实验结果表明，该算法具有较好的性能。
关键词:
障碍k全局相异最优有序路径,
作用集,
障碍角度点,
可视图,
近似算法
CLC Number:
SUN Dong-Pu, HAO Zhong-Xiao. k Globally Different Optimal Sequenced Route Query Based on Obstacles[J]. Computer Engineering, 2011, 37(5): 80-82.
孙冬璞, 郝忠孝. 基于障碍物群的k全局相异最优有序路径查询[J]. 计算机工程, 2011, 37(5): 80-82.