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

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


信息科技

中国科技信息 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-


相关文章:
基于二部图的数字化校园模型研究.pdf
基于二部图的数字化校园模型研究 - 信息科技 中国科技信息 2010 年第 22
基于二部图的数字化校园模型研究_论文.pdf
基于二部图的数字化校园模型研究 - 采用将驻留点和线路抽象为二部图中的两类顶点的
基于二部图的数字化校园导游系统研究_论文.pdf
基于二部图的数字化校园导游系统研究 - 采用将驻留点和线路抽象为二部图中的两类顶点的模型描述有限区域网络路径,用参照距离值度量顶点间路径的长度,考虑换路线...
基于门户技术的数字化校园数据整合应用研究.pdf
基于门户技术的数字化校园数据整合应用研究 - 第 23 卷第 4 期 2010
数字化校园统一身份认证系统的模型研究与实现_图文.ppt
数字化校园统一身份认证系统的模型研究与实现 - 数字化校园统一身份认证系统 的模型研究与实现 专业:软件工程 姓名:聂坤苗 日期:2009.5.25 内容概要 ? ? ? ? ...
基于MP2DR3W模型的数字化校园安全解决方案研究_论文.pdf
基于MP2DR3W模型的数字化校园安全解决方案研究 - 长江大学学报 ( 自科
基于云计算的数字化校园的研究.pdf
基于云计算的数字化校园研究 - Computer Knowledge and
基于URP的高职院校数字化校园建设研究.doc
基于URP的高职院校数字化校园建设研究 - 龙源期刊网 http://www.qikan.com.cn 基于 URP 的高职院校数字化校园建设研究 作者:宋荣 来源:《无线互联科技》2015 ....
基于云平台的数字化校园建设研究_论文.pdf
基于云平台的数字化校园建设研究_信息与通信_工程...职业教育 根据 云架 构模型 规律 ,构建基于 云平...各个 业务 部 门的基 本 数据 , 数据 的安 全...
《基于云服务的数字化校园建设与应用研究》.doc
基于云服务 展开数字化校园的应用,将逐步形成我校的教育大数据。 (二)建设基于...2.对云平台的功能认识有了突破,学校云平台的构建初具模型。 云平台是数字化...
基于SOA的数字化校园信息平台设计研究_论文.pdf
基于SOA的数字化校园信息平台设计研究 - 当前高校各业务软件系统结构不同、信息
基于数字化校园平台的就业管理系统研究_论文.pdf
基于数字化校园平台的就业管理系统研究_企业管理_经管营销_专业资料。第2 5卷第...关键词: 就业 , 数字化校园,系统 中 图分 类号:TP311 文献标识码:A 文章...
面向中小学的轻量级数字化校园建设模型及其应用.doc
发展趋向等多个方面都已经有了丰硕的研究成果和实践...二 面向中小学的轻量级数字化校园建设模型 虽然高校...有的是 C/S 架构的软件、有的是基于 B/S 的...
基于数字化校园建设的校园一卡通系统研究.doc
基于数字化校园建设校园一卡通系统研究 - 基于数字化校园建设校园一卡通系统研究 【摘要】 :随着社会信息化蓬勃的发展,校园管理进入了迅速发展的信息化 时代,本文...
...:基于数字化校园的网上教学平台搭建与应用的研究_图....doc
基于数字化校园的网上教学平台搭建与 应用的研究 ...数字化教学平台 2014 年 6 月 1 二、主持人...内容包括: ①完成学校的网络结构模型,确保网络中心的...
基于协同思想的数字化校园信息系统的设计与开发.doc
关键词:协同思维;联动行为模型;组件 中图分类号: TP31 文献标识码: A 文章编号: 1673-1069(2016)12-153-2 1 设计思路 基于协同思维的数字化多媒体校园信息...
基于云计算的数字化校园架构研究_论文.pdf
基于云计算的数字化校园架构研究 - 分析了云计算的基本理念和架构的实现和原理,以具体学校的数字化校园建设为例,提出了基于云计算技术的校园网架构,并对架构的可行...
基于数字化校园自主学习与有效教学的理论与实践研究.pdf
基于数字化校园自主学习与有效教学的理论与实践研究_...图1 二、研究的目的和意义 为教学改进最为显著的指标...通过网上阅 卷将采集到的数据导入到成绩数据模型进 ...
“数字化学校建设研究”课题结题报告.doc
“十字星”数字化学校模型,初步建 成了数字化学校...二、研究理论依据 1、建构
基于Web Service的数字化校园集成信息平台的研究_论文.pdf
基于Web Service的数字化校园集成信息平台的研究 - 针对数字化校园的建设现状,介绍了Web Service技术,提出了一种基于Web Service的信息集成模型,并结合实例描述了具体...
更多相关标签: