检索结果-南通市图书馆

基于图的距离标号算法及其在频率分配中的应用

在线全文

学校读者我要写书评

暂无评论

基于图的距离标号算法及其在频率分配中的应用

作者：朱利娜兰州交通大学

学位级别：硕士

图论是数学的一个分支,特别是离散数学的一个重要分支,近几十年,图论把在计算机流程图、电网分析、人工智能、情报搜索、等众多领域中存在的问题转化为图论问题来解决,并广泛应用于解决频率分配、考场排座、物流、排课表问题等,致使图... 详细信息

图论是数学的一个分支,特别是离散数学的一个重要分支,近几十年,图论把在计算机流程图、电网分析、人工智能、情报搜索、等众多领域中存在的问题转化为图论问题来解决,并广泛应用于解决频率分配、考场排座、物流、排课表问题等,致使图论学科的研究飞速发展。图标号问题作为图论研究领域的一个重要研究点起源于1966年Rosa的著名的优美树猜想,由于对映射要求的不同,产生了各种各样的图标号问题。其中较受学者关注的图标号主要有优美标号、边幻和全标号、L(j,k)-标号、幸福标号等。目前,在以往研究标号的文献中,大多是采用传统的手工推理方法对图进行标号,而这种方式只能局限性的探究特殊的图结构,对于图的拓扑结构无法用参数刻画的随机图形较难进行研究。研究者们对于图标号的研究主要集中在特殊的图类上,如扇图、轮图、树图、项链图、太阳图、二部图等,这些特殊的图类较难反映现实中存在的复杂问题。本文设计了针对随机图进行边标号的算法,利用算法对随机图的数据集进行处理得到了11个点以内12205208个随机图、11个点以内81306个树图及16个点以内482977个单圈图的边标号矩阵及最小标号数,通过对结果集的探究得到了相关的标号结论和猜想并给出了具体的证明过程。当随机图的点数大于11时,其图集数量十分庞大较难在短时间内进行标号,所以本文选取部分结果集进行研究,并验证结果集的正确性。图的L(2,1)-全标号是图标号的一种,是指对于图G,要满足任意两条相邻的边标号值不相同、任意两个相邻点的标号数不相同、相关联的点和边的标号值相差至少为2,目标则是得到图G的最小标号数。基于对图的L(2,1)-全标号已有研究成果的分析,设计了一种全标号搜索算法,得到了11个点以内12205208个随机图的标号结果集,并得到了一些联图的标号结论。频率规划问题实质上是一个组合优化问题,将有限数目的信道分配给较多数目的载频。由于载频个数远远大于信道个数,不可避免的在不同载频分配到相同信道或者相邻的信道之间产生干扰。近年来很多学者将频道分配问题转化为图标号模型开展研究。针对本文研究成果进行了频率分配仿真实验,通过分析得到图标号和频率分配之间的对应关系,给出了具体的分配方案,实验证明了算法的正确性及图标号理论的现实研究价值。

关键词： L(2,1)-边标号 L(2,1)-全标号标号算法频率分配

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

交通网络最短路径标号算法的实现与效率分析

中国图象图形学报 2005年第9期10卷 1134-1138页

作者：陈洁陆锋中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室北京100101

标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种D ijkstra算法为核心的标号设定算法是各种商用G IS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正... 详细信息

标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种D ijkstra算法为核心的标号设定算法是各种商用G IS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法———基于逼近桶结构和改进四叉堆的D ijkstra算法(D IKBA与D IKQH)以及Pallottino算法(TWO-Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力。

关键词：最短路径算法标号算法复杂度交通网络

随机图的L（2,1）-标号算法及其在频率分配中的研究

在线全文

学校读者我要写书评

暂无评论

随机图的L（2,1）-标号算法及其在频率分配中的研究

作者：孙帅兰州交通大学

学位级别：硕士

作为图染色问题的一种推广,图的标号问题具有极高的理论价值,自诞生以来就成为了图论研究领域中最热门的方向之一。近年来,通过对各类标号模型的研究,得到的一些成果在科学技术和工程领域中都有着广泛的应用,这使得图标号问题备受关注... 详细信息

作为图染色问题的一种推广,图的标号问题具有极高的理论价值,自诞生以来就成为了图论研究领域中最热门的方向之一。近年来,通过对各类标号模型的研究,得到的一些成果在科学技术和工程领域中都有着广泛的应用,这使得图标号问题备受关注。标号模型通常来自于实际问题中所隐含的拓扑关系,对这些模型的研究不但有助于解决实际问题而且也促进了图论自身的发展。标号问题通常指为图的顶点或边分配自然数,使其满足某些特定的条件,根据条件的不同,学者们提出了各类标号模型的定义并进行了深入地研究,逐渐形成了种类丰富的图标号理论。传统研究方法主要是基于图自身的拓扑结构,通过组合构造法来完成标号的,但能够被这种方法处理的图大多较为特殊,并不适用于一般的随机图。随着计算机科学的快速发展,设计针对随机图的算法来解决各类图标号问题是一种新的研究方法和思路。本学位论文主要研究与信道频率分配相关的L（2,1）-标号及其变种问题,利用算法得到有限点内非同构连通图的标号结果,通过对实验数据的分析,得到了几类图的标号结论。主要工作如下:（1）介绍图及图标号的概念,总结概括L（2,1）-标号及相关变种问题的研究现状,分析目前存在的问题。（2）设计并实现了随机图的L（2,1）混合优化标号算法,对10个点内所有的简单连通图进行L（2,1）-标号求解,得到了正确的标号结果。在整理分析实验结果后,得出了有限点内的相关定理并提出了相应的猜测,基于这些猜测,扩大实验范围,对更大点数的图（主要包括16个点以内的所有单圈图和一些正则图）进行了验证。围绕Griggs关于L（2,1）-标号上界的猜想,本文结合实验结果提出了有关非正则图的更小上界猜测:若图G为非正则的连通图,则其L（2,1）-标号数不超过2Δ+1。使用算法只能得到有限点内随机图的结论,而且随着点数的增加,图结构更为复杂,图集的数量也呈爆炸式增长,所以获取全部的图集数据并不现实,故定义了几类联图,结合算法结果和组合构造法给出这几类联图的数学证明,充分发挥了算法和组合构造法的优势。（3）针对映射到边的L（2,1）-边标号问题,设计了基于线图和多目标优化的两种求解算法,而对要求将映射集合内元素全部用到的全色L（2,1）-标号问题,则使用启发式搜索算法进行求解。实验分别得到了9个点以内图的标号数据,整理并得到了关于树图、单圈图和双圈图的相关结论与猜测,其中,树图边标号的结论改进了已知的结果。（4）结合L（2,1）-标号理论及算法,设计频率分配仿真实验,说明其可行性和应用价值。

关键词： L(2,1)-标号标号数标号算法频率分配

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

随机图的幻和全标号及反幻点标号算法研究

随机图的幻和全标号及反幻点标号算法研究

作者：王笔美兰州交通大学

学位级别：硕士

本文主要研究了图标号中较为经典的两种标号,分别是边幻和全标号和（a,d）-边反幻点标号。首先,对于图G（p,q）,若存在一个映射f:V（G）∪E（G）→{1,2,…,p+q},使得任意边uv∈E（G）,满足f（u）+f（v）+f（uv）=K,K为常数,则图G（p,q... 详细信息

本文主要研究了图标号中较为经典的两种标号,分别是边幻和全标号和（a,d）-边反幻点标号。首先,对于图G（p,q）,若存在一个映射f:V（G）∪E（G）→{1,2,…,p+q},使得任意边uv∈E（G）,满足f（u）+f（v）+f（uv）=K,K为常数,则图G（p,q）为边幻和全标号图。特别地,若图G的顶点标号满足:f（V（G））→{1,2,…p},则f是图G的超级边幻和标号,图G为超级边幻和全标号图。截止到目前,研究者们对边幻和全标号的研究主要集中在特殊图上,如圈图、完全二部图、扇图、二叉树、毛毛虫树等。以上所提到的这些特殊图不足以反映现实世界的众多复杂问题,所以本文设计了一种全新的可以对一般图进行标号的边幻和全标号算法,得到了 16个点以内的所有单圈图的边幻和全标号。通过分析算法结果,找出了几类单圈图的标号规律,总结出若干定理并给出证明,最终结果表明,点数小于等于16的所有单圈图均具有边幻和全标号,且其中绝大部分也是超级边幻和全标号,从而猜测:点数多于16的单圈图也具有边幻和全标号。其次,利用边幻和全标号算法得到有限点以内的有关扇图、圈图、星图的三类联图的边幻和全标号,并将所得联图标号结合组合构造法得到了点数为无穷时的三类联图的边幻和全标号精确算法。最后,（a,d）-边反幻点标号是指仅对图G（p,q）的顶点进行标号,顶点标号映射到{1,2,…,p},且满足图中所有边的权重映射到一个等差数列{a,a+d,…,a+（q-1）d},其中a和d均为常数,其中边的权重等于其关联的两个顶点的标号之和。它被Simanjuntak,Bertault and Miller等人于2000年提出,并得到C2n、C2n+1、P2n和Pn的相关结论。继此之后,诸多学者也着手开始研究此标号,并得到Wn、Kn、Kn,n、C3（n）、mCn等特殊图的相关结论。以上特殊图仅占图集总量的一小部分,因此解决剩余的一般图的标号具有非比寻常的意义。本文设计了一种（a,d）-边反幻点标号算法,逐个求解有限点以内的所有简单无向连通图的（a,d）-边反幻点标号,然后根据标号结果给出了若干针对特殊图和联图的精确算法,针对一般图则给出了一个启发式搜索算法模型。该算法分为两个部分,第一部分依据定义设置预判函数,通过它对图集中的所有图进行预判,进而剔除部分理论上不存在（a,d）-边反幻点标号的图;第二部分求解剩余图集的（a,d）-边反幻点标号。特别地,通过预判函数知,当q≥p时,图G（p,q）无（a,2）-边反幻点标号,因此只需要对q＜p的图研究即可,故利用算法得到了 13个点以内所有树图的（a,2）-边反幻点标号。

关键词：图边幻和全标号 (a,d)-边反幻点标号标号算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于标号算法搜索过程的K最短路算法设计

兰州交通大学学报 2019年第4期38卷 27-33页

作者：刘兰芬杨信丰刘林忠兰州交通大学交通运输学院

K最短路径问题是最短路径问题中的一个重要分支,它在物流调度、交通流分配、交通网络的路径选择中起着重要的作用.为了提高K最短路的计算效率以及实用性,充分利用传统标号算法搜索过程获得的众多节点临时标号信息,设计了基于搜索过程的D... 详细信息

K最短路径问题是最短路径问题中的一个重要分支,它在物流调度、交通流分配、交通网络的路径选择中起着重要的作用.为了提高K最短路的计算效率以及实用性,充分利用传统标号算法搜索过程获得的众多节点临时标号信息,设计了基于搜索过程的Dijkstra标号算法.该算法在搜索过程中得到一条最短路径的同时,获得了大量的临时标号信息;在此基础上,继续采用该算法利用这些临时标号信息进行标号,可以获得其他严密K最短路;将该算法与交叉口有延误的最短路径算法相结合,可方便的计算城市交通网络中交叉口有延误的K最短路径问题;该算法简化了K最短路的计算过程,提高了算法的计算效率.最后,利用一个简单网络介绍了该算法的计算过程.

关键词： K最短路标号算法搜索过程交叉口延误

在线全文

学校读者我要写书评

暂无评论

单圈图的优美标号算法研究

信息技术 2018年第9期42卷 50-54页

作者：武永兰魏众德兰州交通大学电子与信息工程学院兰州730070

优美标号是图标号问题的起源,其有着广泛的应用价值。图的优美标号是指对图的顶点或边用自然数进行标号,并使这些标示数字满足一定的条件。Truszczyński提出优美单圈图猜想:除了圈Cn,n(mod 4)={1,2},之外,其它所有单圈图都是优美的。... 详细信息

优美标号是图标号问题的起源,其有着广泛的应用价值。图的优美标号是指对图的顶点或边用自然数进行标号,并使这些标示数字满足一定的条件。Truszczyński提出优美单圈图猜想:除了圈Cn,n(mod 4)={1,2},之外,其它所有单圈图都是优美的。针对该猜想,设计了一种单圈图优美性验证算法,给出了预判断函数对算法进行优化,并对猜想进行计算机证明,即对每一个单圈图进行优美标号。利用该算法,对18个点内的所有单圈图进行了优美性标号。实验结果表明,对于单圈图来说,除了圈图Cn,n(mod 4)={1,2}之外,18个点内所有单圈图都是优美的。

关键词：图标号优美标号单圈图标号算法

在线全文

学校读者我要写书评

暂无评论

分派问题一种标号算法

运筹与管理 1999年第1期8卷 16-20页

作者：夏少刚东北财经大学数量经济研究所

文章采用一定技巧，把求最短路的Ｄｉｊｋｓｔｒａ算法用于求解分派问题，得到一种标号算法，计算复杂性仅为Ｏ（ｎ２），比以往的算法减少了一个数量阶Ｏ（ｎ）。

关键词：分派问题(AP) 最短路标号算法最小方案非负处理

用网络最大流标号算法进行露天开采境界的优化设计

在线全文

学校读者我要写书评

暂无评论

云南冶金 1982年第3期 3-6页

作者：陈孝华昆明工学院

最大流标号算法是运筹学中网络图论的一种有效解题方法,其特点是按照一定法则对节点进行标号,并在有限步内把网络流调整成为最大流,利用这一算法可使复杂的矿业工程设计变得简明、直观、易于达到真正最优化.

关键词：露天开采露天采矿矿山开采标号算法矿岩网络最大流优化设计

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

绘制统筹网络图的一个标号算法及应用

运筹与管理 1994年第1期3卷 17-21页

作者：李荣生曲阜师范大学运筹学研究所

本文给出了一个绘制统筹网络图的有效算法，称之为标号算法．利用标号算法可使计算机在只接收到各工序间紧前紧后关系的数据后，便可生成网络优化中必需的网络图形．利用该算法我们还建立了网络优化计算机辅助设计系统，该方法和计算机... 详细信息

本文给出了一个绘制统筹网络图的有效算法，称之为标号算法．利用标号算法可使计算机在只接收到各工序间紧前紧后关系的数据后，便可生成网络优化中必需的网络图形．利用该算法我们还建立了网络优化计算机辅助设计系统，该方法和计算机辅助设计系统，目前已在山东省兴隆庄煤矿井下的拆除和安装工程中得到了具体应用，收到了良好的效果．

关键词：绘制统筹网络图标号算法运筹学