论文部分内容阅读
随着互联网的发展和智能手机的普及，基于位置的服务也迅猛地发展了起来，其中，地图搜索的功能也开始日趋强大和多样化。如何改善地图搜索的功能，提供给用户更加智能更加人性化的结果，成为了当前研究的一个热点。 本文从这一点出发，考察了用户在使用地图搜索功能中的一些实例，提出了地图密集区域搜索问题。并根据最优化的不同角度，提出了r-区域问题和k-区域问题两类问题。即对这些问题中的特殊情况做出了分析，又对一般情况给出了可行的基于k-NN的近似算法和基于高阶Voronoi图的算法。同时还分析了r-区域问题与k-区域问题之间的联系，基于强对偶定理和目标函数的单调性，给出了一个二分算法。 在此基础上，进一步考虑了更加复杂的用户需求，从类似的角度对在主要关键字之上，附有次要关键字的主次关键字地图密集区域搜索问题进行了分析。最后，通过实验，比较了不同算法的优劣，并验证了算法的效果。