%0 Journal Article
%T 空间网络数据库中移动对象的最短路线算法
%A 殷晓岚
%A 丁治明
%A 李京
%J 自然科学进展
%D 2008
%I 
%X 在空间网络数据库中，基于位置的服务（location-based services，LBS）变得越来越重要，最短路线查询是最广泛的服务请求之一.假设在网络上有一个原始对象（例如：在道路上行驶的汽车）、有一个目标对象（例如：旅店、加油站、救护车等等），那么最短路线查询就是要找到原始对象到目标对象的最短路线.最短路线算法的研究主要分为两个方面，实时计算和预计算.在预计算方面，当前的研究对网络空间中的最短路线查询提出了多种解决方式，但是这些方法中都假设目标对象是静止的.文中在原始对象和目标对象都处于移动状态时，给出了一种最短路线查询的算法.该算法创建了一组索引结构，将计算两个动态点之间最短路线的问题转换为计算静态边之间最短路线的问题.主要关注交通网络.但是该算法不会使用任何领域相关的信息，所以能够被应用到其他的网络环境中.从计算复杂性而言，传统的Dijkstra算法时间复杂性估计是O((i+k)2)，而该算法的相应估计是O(klbi).
%K 移动对象
%K 空间数据网络库
%K 最短路线索引
%K 最短路线
%K 空间网络数据库
%K 移动对象
%K 最短路
%K 估计
%K 算法时间复杂性
%K Dijkstra
%K 计算复杂性
%K 网络环境
%K 应用
%K 信息
%K 领域相关
%K 使用
%K 交通网络
%K 问题转换
%K 动态点
%K 索引结构
%K 状态
%K 方法
%K 解决方式
%K 网络空间
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=01BA20E8BA813E1908F3698710BBFEFEE816345F465FEBA5&cid=96E6E851B5104576C2DD9FC1FBCB69EF&jid=504AF8C1E5476CA7C4EC9DF6FEAC14AC&aid=CE66F9CC508E9E90A79CE9B22566CE57&yid=67289AFF6305E306&vid=13553B2D12F347E8&iid=B31275AF3241DB2D&sid=D02611D1F8166C9A&eid=27A3D4EE1F52A91C&journal_id=1002-008X&journal_name=自然科学进展&referenced_num=0&reference_num=31