当前位置:首页 >> 管理学 >>

基于二部图的数字化校园模型研究


信息科技

中国科技信息 2010 年第 22 期 CHINA SCIENCE AND TECHNOLOGY INFORMATION Nov.2010

DOI:10.3969/j.issn.1001-8972.2010.22.032

基于二部图的数字化校园模型研究
庄天龙 尚维来 宣旭君  南京化工职业技术学院 210048
摘 要 采用将驻留点和线路抽象为二部图中的两 类顶点的模型描述数字化校园路径, 用参 照距离值度量顶点间路径的长度, 考虑换 路线因素和距离因素对路径选择行为的影 响,在 Dijkstra 算法基础上,设计了网络 最优路径搜索算法引入迭代惩罚函数。 关键词 数字化校园 二部图 Dijkstra 算法  Matlab ; ; ; 向图。 表示线路与站点之间的逻辑关系,这种边 没有方向,也不表示任何实际的距离。图 3 给出了一个校园交通网络抽象为二部图 模型的示意图 [ 6 ] 。

图 1 实际校园航拍图

引言
数字化区域问题的研究在地理信息系 统开发、路线信息查询等方面具有重要的 理论和应用价值[1]。对数字化校园网络路 径选择问题的研究包括路径网络的数学描 述和路径搜索算法设计两个方面,现有的 研究多采用有向赋权图模型描述数字化校 园网络,将驻留点抽象为图中的顶点,将 驻留点间的线路抽象为图中的边[2]。但数 字化校园网络中存在变换路线现象,且变 换成本是发生在驻留点上的,采用普通的 有向赋权图描述模型很难处理顶点带权的 路径搜索问题,需要在路径搜索过程中反 复判断是否存在变换,导致搜索效率的下 降。针对这一问题,采用二部图模型描述 数字化校园,把驻留点和有效线路均抽象 为图中的顶点。在此基础上,设计了综合 考虑变换次数和行进距离因素的数字化校 园网络最优路径搜索算法。

图 2 生成数字化校园网络路径 对所生成的路径网络图中的路径和交 叉点及驻留点的属性描述是关键点,如 果有新路径和驻留点的出现,将会及时 主动加入现有的相对坐标中。

2 用二部图模型描述校园路径网 络
二部图是图论中的一种特殊模型, 设 G=(V,E)是一个无向图,如顶点集 V 可分割为两个互不相交的子集 V1 和 V2 (V1 ∩ V2= φ), 并且图中每条边的两个顶 点都分属两个不同的子集,则称图 G 为二 部图 [ 2 ] 。 数字化校园网络的二部图描述可以表 示为如下形式: G = (R ,S ,E ) ( 1 ) 其中,R 为公交网络中所有线路的集 合;S 为校园网络中所有站点的集合;E 为 驻留点和有效线路连接边的集合式(1)中描 述校园网络的二部图是无向图,与一般的 校园网络有向赋权图模型有很大区别。在 有向图模型中,停留点抽象为顶点,站点 间的线路抽象为边,其权值为两站点间的 距离,这种描述方法更接近于人对校园网 络拓扑结构的直观认识,而在二部图模型 中,将校园线路也抽象为一类顶点,边则

1 数字化校园路径网络生成图
实际校园(如图 1)在规划初可能没 有考虑路径成图,或者对已成校园的老校 区进行导游线路规划及展示,若希望提供 信息查询交互平台系统,对数字化校园网 络路径选择问题将是必须解决的。 对于目标数字化校园生成路径图的方 式很多[3,4,5,7],图 2 是图 1 的目标部分数字 化校园的路径生成网络图。本文采用基于 路网描述规则,通过对路网中道路和交叉 口进行模型化,最终得出比较清晰的无

图 3 数字化校园网络的二部图描述 从表面上看,似乎二部图模型与对 公交网络拓扑结构的直观认识有很大出 入,但它具有如下吸引人的特性: (1) 两停留点之间的路径包含偶数条 边,且边总数的一半减 1 等于该出行路 径的换乘次数; (2 )两停留点之间连接路径所包含 的 R 顶点是该条路径(依次)使用的校 园线路; (3 )如果所有边的权值相等,则任 意两停留点之间的最短路径就是变换次数 最少的路径。 二部图模型的上述特性表明,图论 中的各种最短路算法,不加任何改造就可 直接用于校园网络最少换乘次数路径的搜 索,而最小变换次数路径的搜索在使用有 向赋权图描述的校园网络中是较难实现的 [5] 。但用二部图模型描述校园网络也存在 一个问题,即两驻留点之间路径的实际距 离值无法直接得到。这一问题可以通过为 每条边添加一个参照距离值来解决。 边的参照距离值定义为:一条边连 接的站点在该条边连接的线路中所处的、 相对于该线路起始点的距离值。也就是 说,对于任一条线路,其起始点连接边 的参照距离值等于 0,其余点连接边的参 照距离值等于该点到起始点的距离。这 一距离值计算的思路与 GIS 中的线性参照 系统非常类似[7],因此将其命名为参照距

-78-

离。这样,同一条线路上任意两驻留点 之间路径的长度,就等于该路径所包含的 两条边的参照距离值之差。基于上述考 虑, 对式(1)中的公交网络二部图模型进行 如下扩展: G=(R,S,E,W,L) (2) 其中,R,S,E 符号意义同前;W 为 边的权值集合;L为边的参照距离值集合。 对于一个实际的公交网络, 可以按以 下步骤生成一个二部图: (1)将校园网络中的所有线路(不区 分上下行)加入顶点集合; (2 )将校园网络中的所有站点加入 顶点集合 对于分别属于两条不同线路但 又相邻很近的停留点,可根据一定原则合 并为同一顶点 [ 3 ]; (3 )如果一条公交线路经过某些停 留点,则在此线路顶点和这些停留点顶 点之间连接一条无向边; (4) 令所有边的权值等于1, 这一权值 不代表任何实际距离,只是为了在路径搜 索中计算变换次数; (5 )根据一条线路包含站点的次 序,依次赋予每条边一个参照距离值, 对于该条线路上的起始站点,参照距离 值等于 0,其余站点连接边的参照距离值 等于该站点到起始站点的距离。

性,为后续信息交互系统的建设做好准 备。

上接第 77 页 (五)形成表述规范的设计文档 为了保证系统实施的可操作性和系统 的可维护性,设计文档应该采用规范的 表述形式。例如:我们可以采用标准建 模 语 言 U M L (U n i f i e d M o d e l i n g Language)描述软件设计方案,利用甘 特图(G a n t t C h a r t )描述工程进度安 排等。

三、实施阶段的质量控制
(一) 慎重选择系统分包商 网络系统实施过程的分包是非常常见 的。由于工程的任何部分都会对整个系 统的质量产生影响,应该慎重选择分包 商,尽量选择具有相应工程资质、丰富 工程经验、有技术保障的分包商。 ( 二 )遵 循 科 学 的 实 施 流 程 和 技 术 要求 系统实施过程应该遵循科学的流程和 有关技术要求,坚持按照标准的实施流 程完成系统的建设。系统实施流程应只 与系统的需求和类型相关,不能因人而 异。例如:网络设备选型时,应当有事 实数据来评估每种设备的性能指标是否满 足网络系统的设计要求。 (三)合理进行阶段性测试 系统实施的各个阶段应该遵照质量控 制方案的要求,分阶段地进行系统测 试,逐步地实现质量控制目标。例如: 综合布线系统施工过程中,应该及时利 用网络测试仪测定线路质量,及早发现 并解决质量问题。

3 算例分析
在前述算法设计的基础上,用 Matlab 编制了数字化校园网络路径搜索 仿真程序,验证数字化校园二部图模 型,示例数字化校园网络中共有 n=50 个 驻留点,m=49 条路径分别用不同线型表 示,如图 2 所示。为简便起见,假定相 邻两驻留点间的距离均为相等值。 通过分析计算结果可以看出, 算法能 够以变换次数最少和距离较短为目标,搜 索出数字化校园网络中两点间的多条可行 路径,且算法生成的最佳路径,与一般用 户的选择方案选择行为较为符合。

四、结语
参考文献 [ 1 ]   闫小勇,尚艳亮.基于二部图模型 的公交网络路径搜索算法[J].计算机工 程与应用.2010,46(5) :246-248. [2]  杨新苗,马文腾.基于 GIS  的公 交乘客出行路径选择模型[J].东南大学 学报:自然科学版.2000,30(6):87-91. [ 3 ]   鲍江宏,关毅璋.基于矩阵运算的 公交查询高效算法[J].计算机工程与应 用.2008,44(10):198-200. [ 4 ]   侯刚,周宽久.基于换乘次数最少 的公交网络最优路径模型研究[J].计算 机技术与发展.2008,18(1):44-47. [ 5 ]   闫小勇,牛学勤.公交网络多路径 选择启发式算法研究[J].城市交通.2005,3 (3):23-26. 计算机网络已成现代社会的基础设 施,其本身的复杂性构成对系统质量的挑 战。在网络系统集成应把握各阶段的质量 控制,才能实现整个系统的效能。

4 结语
采用二部图模型描述数字化校园路径 网络,将线路抽象为图中一类特殊的顶 点,对图论中普通的最短路搜索算法稍 加改造,即可搜索到变换次数最少且距 离较短的合理出行路径,避免了采用有 向赋权图描述模型时变换乘识别的困难。 在此基础上进一步研究了校园网络多条备 选路径的搜索算法,不局限于只提供单 一的路径方案,使研究成果更具实用

参考文献 [1]杨卫东. 网络系统集成与工程设计[M]. 北京:科学出版社.2002.04 [2]奚文骏. GJB9001A与全面质量管理[J]. 质量与可靠性.2002.第 3 期
作者信息 赵党乾(1 9 6 9 - ) 男,工程师,本科 , 学历,主要研究方向:网络安全、计算机软 件、电子政务。

-79-


相关文章:
基于数字化校园的车载管理系统研制技术报告
二〇一二年八月九日 基于数字化校园的车载管理系统...自主型存取控制:在这种存取控制模型中,系统用户对...密钥的产生见图。 1 公司授权 根密钥 随机数 ...
基于域控制器的数字化校园网部署策略研究与实现5.27
基于域控制器的数字化校园网部署策略研究与实现 作者...15 3.3 域控制器网络系统功能模型研究 ......图 3.1:域控制器基本结构 3.4 域控制器网络系统框架设计...
基于数字化校园科研协作平台的研究和建设
基于数字化校园科研协作平台的研究和建设_军事/政治_...关键词:数字化校园;协作科研;协作办公 中图分类号:...高校的科研工作作为全社会科技活动的一个重要组成部 ...
基于数字化校园环境下的电子白板的应用研究(实验小学)
附件二: 南京市小学“新三基”教育重点实验项目申报表 项目名称: 基于数字化校园环境下的电子白板的应 用研究 项目负责人:童坤荣 所在单位 :六合区实验小学 申报...
...:基于数字化校园的网上教学平台搭建与应用的研究
年度 编号 (以上由省教育科学规划办填写) 湖南省教育科学规划课题 立项申请·评审书学 科分类 一般课题 课 题类 别 省级一般资助课题 课 题名 称 基于数字化...
基于CRP的数字化校园信息平台研究和开发研究报告
基于CRP的数字化校园信息平台研究和开发研究报告_军事...信息化 中图分类号:TP393 文献标识码:A 文章编号...基于道路信息模型的湛徐... 120人阅读 6页 免费 ...
胡旭松-基于WEBGIS的数字化校园设计与实现
胡旭松-基于WEBGIS的数字化校园设计与实现胡旭松-基于WEBGIS的数字化校园设计与...校区数字化校园地理信息系统建设为研究实例,设计了数字化校园的 WebGIS 模型, ...
“数字化学校建设研究”课题结题报告
“十字星”数字化学校模型,初步建 成了数字化学校...二、研究理论依据 1、建构主义学习理论与教学理论。...力图突破传统的以教师传授为主、学生被动学习的传统...
数字化校园建设的研究与实践(报告)
数字化校园建设的研究与实践(报告)_教育学/心理学_...二、课题实验的总体设计 1.概念的界定 数字化校园:...构建各学科网上资源开发体系以及课堂教学基本 模型。 ...
数字化校园建设的研究课题申报_图文
数字化校园建设的研究 科分名 课题 ___ 课题负责...二、作为课题研究者或主要承担者,本人完全了解中央电...已经基本上完成了由 传统教育向基于数字平台教育的...
更多相关标签: