求解k完全相异可视最优有序路径的近似算法  

APPROXIMATE ALGORITHMS FOR RESOLVING k COMPLETELY DIFFERENT VISIBLE OPTIMAL SEQUENCED ROUTE

作　　者：孙冬璞[1] 郝忠孝[1,2] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,黑龙江哈尔滨150080 [2]哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《计算机应用与软件》2011年第1期22-25,共4页Computer Applications and Software

基　　金：国家自然科学基金项目(60673136);黑龙江省自然科学基金项目(F200601)

摘　　要：提出了k完全相异可视最优有序路径查询问题,根据处理数据集与障碍集先后顺序的不同,给出了距离优先的近似算法Distance_First以及角度优先的近似算法Angle_First。实验结果表明,算法Distance_First适用于障碍集规模较小的k完全相异可视最优有序路径查询问题,而算法Angle_First适用于障碍集规模较大的k完全相异可视最优有序路径查询问题。The problem of k completely different visible optimal sequenced route query is put forward in the paper.Two approximate algorithms for resolving this query problem,the Distance_First algorithm and the Angle_First algorithm at the rules of distance preference and angle preference respectively,are presented based on different order of dealing with datasets and obstacle set.Experimental results show that for k completely different visible optimal sequenced route query problem,the Distance_First algorithm fits the one with smaller obstacle set and the Angle_First algorithm fits the one with larger obstacle set.

关 键 词：k完全相异可视最优有序路径 距离优先 角度优先 可视区域 近似算法 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]