基于平面图的最短路径算法的研究 被引量：21

1

作者 于东凯 刘玉树 《北京理工大学学报》 EI CAS CSCD 北大核心 2001年第1期31-34,共4页

研究平面图特殊应用条件下最短路径搜索算法的时间复杂度和空间复杂度 .从应用的角度 ,设计一种新的数据存储结构 ,改进最短路径搜索算法 ,并建立一种简捷的估价函数 ,使基于平面图的动态路径规划算法在时间复杂性和空间复杂性上均达到... 研究平面图特殊应用条件下最短路径搜索算法的时间复杂度和空间复杂度 .从应用的角度 ,设计一种新的数据存储结构 ,改进最短路径搜索算法 ,并建立一种简捷的估价函数 ,使基于平面图的动态路径规划算法在时间复杂性和空间复杂性上均达到了线性 ,为进一步解决这一领域内的网络综合分析打下了基础 . 展开更多

关键词 最短路径 图 平面图 欧拉公式

在线阅读 下载PDF 职称材料

基于平面图的改进Dijkstra算法研究 被引量：8

2

作者 黄纬 《江苏大学学报（自然科学版）》 EI CAS 2003年第6期70-72,共3页

针对在平面图应用条件下,对应用Dijkstra算法进行最短路径搜索的设计方法和运算过程进行分析,从应用的角度,改进Dijkstra算法,设计一种新的数据存储结构,并建立简洁的估价函数,使基于平面图的动态最短路径规划算法在时间复杂性和空间复... 针对在平面图应用条件下,对应用Dijkstra算法进行最短路径搜索的设计方法和运算过程进行分析,从应用的角度,改进Dijkstra算法,设计一种新的数据存储结构,并建立简洁的估价函数,使基于平面图的动态最短路径规划算法在时间复杂性和空间复杂性均达到线性。 展开更多

关键词 图论 最短路径 平面图 欧拉公式

在线阅读 下载PDF 职称材料

需求响应式公交系统路径优化算法 被引量：12

3

作者 王力生 帅斌 《西华大学学报（自然科学版）》 CAS 2014年第1期84-87,93,共5页

将需求响应式公交系统路径选择问题抽象为在图中寻找覆盖若干条指定边的欧拉圈问题,提出乘客数量不大于公交车容量和乘客数量大于公交车容量两种情况下的公交车运营组织方式,对第一种情况设计了有效的图论算法,对第二种方式则给出转化... 将需求响应式公交系统路径选择问题抽象为在图中寻找覆盖若干条指定边的欧拉圈问题,提出乘客数量不大于公交车容量和乘客数量大于公交车容量两种情况下的公交车运营组织方式,对第一种情况设计了有效的图论算法,对第二种方式则给出转化为动态规划问题的思路。论文引理证明,第一种算法能寻找到覆盖若干条指定边的最小欧拉圈,并通过有关算例进行了说明。 展开更多

关键词 需求响应式公交系统 欧拉圈 图论 路径优化

在线阅读 下载PDF 职称材料

最小最大路划分的一个启发式算法 被引量：1

4

作者 张同全 王泽磊 《云南民族大学学报（自然科学版）》 CAS 2004年第4期292-294,共3页

　首先证明了最小最大路划分问题是困难的,然后利用二分算法给出了特殊情形下的最优算法,最后给出了满足三角不等式的图上的一个启发式算法.

关键词 euler图 HAMILTON路 路划分 启发式算法 三角不等式

在线阅读 下载PDF 职称材料

数字集成电路课程的教学案例研究 被引量：3

5

作者 王仁平 施隆照 《高师理科学刊》 2017年第1期86-88,共3页

为配合福建省集成电路产业迅速发展,数字集成电路作为微电子科学与工程专业的核心课程,试行了以产业实际案例教学为主的应用型教学模式.强化学生的工程应用能力和创新意识,激发学生的学习兴趣和学习动机,使课程充满生机和活力.

关键词 数字集成电路 逻辑图 欧拉路径 棍棒图 教学案例

在线阅读 下载PDF 职称材料

水灾地区邮递员问题 被引量：4

6

作者 汤泽滢 谢政 《应用数学与计算数学学报》 2000年第1期25-30,共6页

本文首次提出了中国邮递员问题的推广问题－水灾地区邮递员问题，并对解的存在性给出了一系列的充分条件、必要条件及充要条件。

关键词 灾邮路线 欧拉图 奇点 水灾地区 邮递员问题 多项式算法

在线阅读 下载PDF 职称材料

基于欧拉迭代模型预测的欠驱动水面船舶路径跟踪控制 被引量：7

7

作者 李荣辉 陈志娟 +1 位作者 李宗宣 卜仁祥 《广东海洋大学学报》 CAS 2020年第1期104-110,共7页

【目的】解决具有外部受风流干扰和舵角输入受约束的欠驱动船舶路径跟踪问题。【方法】采用基于欧拉迭代的模型预测控制算法(MPC)对欠驱动船舶路径跟踪进行控制。【结果】MPC能够灵活地处理舵角输入受约束问题,欧拉迭代法离散和预测船... 【目的】解决具有外部受风流干扰和舵角输入受约束的欠驱动船舶路径跟踪问题。【方法】采用基于欧拉迭代的模型预测控制算法(MPC)对欠驱动船舶路径跟踪进行控制。【结果】MPC能够灵活地处理舵角输入受约束问题,欧拉迭代法离散和预测船舶未来状态可以简化MPC设计的运算。为弥补欧拉迭代法在精度上的不足,直接以分离型船舶模型(MMG)作为MPC的预测模型。应用径向基函数(RBF)神经网络历史信息训练实现对外界风流干扰的逼近及补偿。【结论】所设计的控制器可以使船舶在考虑风流干扰和舵角约束的情况下准确地跟踪上设定的路径,所提控制算法的有效性得到验证。 展开更多

关键词 船舶路径跟踪 模型预测控制 欧拉迭代法 船舶运动控制

在线阅读 下载PDF 职称材料

边界表示的拓扑与几何一致性 被引量：1

8

作者 刘雄伟 彭维 郑海波 《华侨大学学报（自然科学版）》 CAS 2000年第1期51-56,共6页

闭路拓扑原理和欧拉公式是检验实体模型边界表示的拓扑与几何一致性的重要工具 .有关文献对此问题的论述不妥 .文中在总结前人研究工作的基础上 ,给出曲面上简单闭路总旋转角的精确定义 ,并以球面为例分析曲面上简单闭路总旋转角的计算... 闭路拓扑原理和欧拉公式是检验实体模型边界表示的拓扑与几何一致性的重要工具 .有关文献对此问题的论述不妥 .文中在总结前人研究工作的基础上 ,给出曲面上简单闭路总旋转角的精确定义 ,并以球面为例分析曲面上简单闭路总旋转角的计算方法 ,从而导出角度超出量的概念 .对多面体进行严格的定义 ,给出欧拉公式及 Gauss- Bonnet定理对多面体的应用条件 .最后给出多面体的广义欧拉特征值、广义 Gauss- Bonnet定理及广义欧拉公式 .这些理论和方法 ,共同构成实体模型边界表示的拓扑与几何一致性检验的有效工具 . 展开更多

关键词 欧拉公式 边界表示 拓扑几何 一致性

在线阅读 下载PDF 职称材料

采用欧拉回路的混凝土3D打印路径优化算法

9

作者 马宗方 万伟鹏 +3 位作者 宋琳 刘超 刘化威 武怡文 《机械科学与技术》 CSCD 北大核心 2024年第11期1954-1960,共7页

针对混凝土3D打印过程中成型质量不好、打印时间长的问题,以欧拉回路模型为基础,设计一种混凝土3D打印路径优化算法,实现了混凝土构件更优、更快的成型。该算法先通过不断寻找打印路径中的欧拉回路来确保打印喷头在抬头次数尽可能少的... 针对混凝土3D打印过程中成型质量不好、打印时间长的问题,以欧拉回路模型为基础,设计一种混凝土3D打印路径优化算法,实现了混凝土构件更优、更快的成型。该算法先通过不断寻找打印路径中的欧拉回路来确保打印喷头在抬头次数尽可能少的情况下遍历整个打印路径,然后应用蚁群算法寻找打印喷头在各个欧拉回路之间运行的最短路径,最后确定整个混凝土构件的打印路径来减少打印喷头抬头次数和运行路径中的空行程。实验结果表明:打印喷头抬头次数和打印路径空行程对混凝土3D打印的成型质量和打印时间有着非常重要的影响。该文算法打印结果与传统算法相比,打印喷头抬头次数减少了57.14%,喷头运行行程减少了23.21%。该文算法对于混凝土3D打印中存在的问题有着明显的改善,为混凝土3D打印构件的成型质量和打印时间的优化提供了有效的参考。 展开更多

关键词 混凝土3D打印 路径优化 欧拉回路 蚁群算法

在线阅读 下载PDF 职称材料

公园类景区的路径设计模型 被引量：1

10

作者 倪敬能 汪晓梦 《合肥学院学报（自然科学版）》 2005年第4期9-12,共4页

立足于实际,研究公园类景区的路径设计问题,通过建立多级路径设计的数学模型,并由此求解出一个科学的路径设计方案。

关键词 路径 最小生成树 euler图 模型

在线阅读 下载PDF 职称材料

基于基本路径集算法生成最小长度测试序列的方法 被引量：4

11

作者 蒙移发 陈源凯 徐惠民 《计算机工程与应用》 CSCD 北大核心 2003年第16期180-182,共3页

在协议工程中,一致性测试已成为非常活跃的领域,而测试序列的产生是一致性测试非常关键的环节。文章基于基本路径集的生成算法,获得不相交路径,并利用测试子序列的一个重要特征—“重叠”来获得连接正收敛边和不相交路径的最小费用迁移... 在协议工程中,一致性测试已成为非常活跃的领域,而测试序列的产生是一致性测试非常关键的环节。文章基于基本路径集的生成算法,获得不相交路径,并利用测试子序列的一个重要特征—“重叠”来获得连接正收敛边和不相交路径的最小费用迁移路径,从而减少了测试序列的长度。 展开更多

关键词 测试序列 测试子序列 欧拉路径 正收敛边 基本路径集

在线阅读 下载PDF 职称材料

集成电路版图欧拉路径的快速判寻方法 被引量：1

12

作者 王健 陈海洋 蓝海萌 《微电子学》 CAS CSCD 北大核心 2011年第6期865-868,共4页

版图欧拉路径法是实现集成电路版图面积最小化的常用方法。讨论了版图欧拉路径与布尔表达式的关系,提出一种版图欧拉路径快速判寻方法。利用该方法,设计了几种典型电路的版图欧拉路径,并运用集成电路设计软件设计其中一种电路,经过优化... 版图欧拉路径法是实现集成电路版图面积最小化的常用方法。讨论了版图欧拉路径与布尔表达式的关系,提出一种版图欧拉路径快速判寻方法。利用该方法,设计了几种典型电路的版图欧拉路径,并运用集成电路设计软件设计其中一种电路,经过优化后的版图面积明显减小。该方法快速、准确、方便,具有广阔的应用前景。 展开更多

关键词 集成电路 版图欧拉路径 布尔表达式 网络拓扑 标准单元

原文传递

战争地区邮递员问题

13

作者 汤泽滢 卢汉清 《应用数学与计算数学学报》 2002年第1期85-89,共5页

本文首次提出了赋权有向图上中国邮递员问题的一个推广-战争地区邮递员问题,并对解的存在性给出了若干充分条件和必要条件,得到了求解该问题的一个多项式算法.

关键词 战争地区 邮递员问题 有向战邮路线 有向欧拉图 非平衡点

在线阅读 下载PDF 职称材料

DNA序列拼接中de Bruijn图结构的研究 被引量：2

14

作者 王东阳 任世军 王亚东 《智能计算机与应用》 2011年第2X期20-25,30,共7页

基因组测序是生物信息学中最基本的研究方向之一，然而大多数生物的基因组都不可能一次性获得，需要利用序列拼接技术对实验中获得的DNA片段进行拼接操作。目前，测序过程中获得的DNA片段越来越短，基于Euler路径的拼接算法在处理这种... 基因组测序是生物信息学中最基本的研究方向之一，然而大多数生物的基因组都不可能一次性获得，需要利用序列拼接技术对实验中获得的DNA片段进行拼接操作。目前，测序过程中获得的DNA片段越来越短，基于Euler路径的拼接算法在处理这种短片段拼接时具有优势。在Euler路径算法中，一个关键的步骤是deBruijn图的构建，一直以来，构建deBruijn图的方式总是让后一个κ-mer与前一个κ-mer之间有κ-1个碱基的交叠，相邻的两个κ-mer之间相互错开一位。但文中的研究发现，如果有边连接的两个κ-mer之间有κ-2个或者更少的碱基相交叠，会对deBruijn图结构复杂性产生重要影响。针对这些影响进行详细分析，并设计实验进行验证，实验结果表明，κ-mer之间的错位数变化对deBruijn图结构复杂性有显著影响。 展开更多

关键词 生物信息学 基因组测序 DNA序列拼接 euler路径 DE BRUIJN图

在线阅读 下载PDF 职称材料

一种3R机械臂最短路径规划方法 被引量：2

15

作者 安凯 马佳光 《光电工程》 CAS CSCD 北大核心 2014年第12期1-6,共6页

为求解机械臂最短路径问题,导出了机械臂末端路径长度的表示式,并将最短路径问题归结为一个泛函极值问题。为简化求解过程,将泛函极值问题转化成另一个同解的泛函极值问题,并利用变分法求出了表示后一问题解的微分方程组。利用上三角矩... 为求解机械臂最短路径问题,导出了机械臂末端路径长度的表示式,并将最短路径问题归结为一个泛函极值问题。为简化求解过程,将泛函极值问题转化成另一个同解的泛函极值问题,并利用变分法求出了表示后一问题解的微分方程组。利用上三角矩阵逆矩阵的表示式,将该微分方程组转化成了标准状态方程组,与微分几何方法相比,避免了逆矩阵计算,使转化过程更加简单。利用Matlab进行仿真,求出了3R机械臂最短路径所对应的三个关节角度的位移函数。 展开更多

关键词 机械臂 路径规划 最短路径 euler方程

在线阅读 下载PDF 职称材料

非主割边与次连通性在寻求欧拉路中的应用

16

作者 孙霞林 《湖北工学院学报》 2002年第1期64-66,共3页

运用图论中无向图的割边与连通性的理论 ,阐述无向图的主割边与次连通性的概念 ,推导出若干有关性质 ,并给出一种在无向图中寻求一条欧拉路的有效方法取非主割边法 .

关键词 主割边 次连通性 欧拉回路 欧拉通路 无向图 图论 取非主割边法

在线阅读 下载PDF 职称材料

基于不确定理论的灾区救援物资配送模型及算法 被引量：1

17

作者 王冬冬 邢进生 《山西师范大学学报（自然科学版）》 2014年第4期21-25,共5页

灾区救援物资配送问题采用传统的中国邮递员问题(CPP)的思想,传统的中国邮递员问题是对确定权重模型的解决,然而在实际应用中,经常会遇到权重不确定的因素,由此本文针对不确定权重的灾区救援物资配送问题,采用不确定理论建立了不确定期... 灾区救援物资配送问题采用传统的中国邮递员问题(CPP)的思想,传统的中国邮递员问题是对确定权重模型的解决,然而在实际应用中,经常会遇到权重不确定的因素,由此本文针对不确定权重的灾区救援物资配送问题,采用不确定理论建立了不确定期望最短路径和α最短路径两种模型,并运用欧拉回路算法分别求解出两种模型的解,使不确定权重灾区救援物资配送问题得到解决. 展开更多

关键词 不确定理论 期望最短路径 α最短路径 欧拉回路

在线阅读 下载PDF 职称材料

球台表面两点间的最短路径算法研究

18

作者 臧爱彬 傅伟国 《宜春学院学报》 2015年第9期11-14,共4页

本文研究在球台表面上的两点间最短路径。若两点落在球体表面上,可利用变分原理中Euler-Lagrange方程求得最短路径。然而,至少有一点在球台上底面或下底面上,发现过这两点经球体表面任一条曲线都不是可微的,从而不能直接利用Euler-Lagra... 本文研究在球台表面上的两点间最短路径。若两点落在球体表面上,可利用变分原理中Euler-Lagrange方程求得最短路径。然而,至少有一点在球台上底面或下底面上,发现过这两点经球体表面任一条曲线都不是可微的,从而不能直接利用Euler-Lagrange方程。本文构造一条光滑曲线逼近给定可求长曲线,得到光滑曲线长度泛函是可微的,进而得出两个曲线长度泛函之间关系也得到一种寻找最短路径方法。 展开更多

关键词 球台表面 最短距离 E-L方程 求法

在线阅读 下载PDF 职称材料

长江口枸杞岛附近海域溢油风险数值模拟 被引量：4

19

作者 李社生 李瑞杰 +1 位作者 丰青 肖千璐 《人民长江》 北大核心 2014年第21期65-69,共5页

为制订长江口枸杞岛附近海域突发溢油事故的应急处理方案,利用实测地形数据建立了枸杞岛附近海域二维潮流数学模型,并根据实测资料对该潮流模型模拟的潮位、流速、流向进行了验证。验证结果表明,该潮流数学模型能较好地反映枸杞岛附近... 为制订长江口枸杞岛附近海域突发溢油事故的应急处理方案,利用实测地形数据建立了枸杞岛附近海域二维潮流数学模型,并根据实测资料对该潮流模型模拟的潮位、流速、流向进行了验证。验证结果表明,该潮流数学模型能较好地反映枸杞岛附近海域的潮流运动情况,可以作为MIKE21 SA溢油模块的水动力基础数据。基于欧拉-拉格朗日"油粒子"理论,综合考虑油膜扩散、漂移、风化等过程,应用MIKE21 SA模块建立了枸杞岛附近海域二维溢油扩散模型,并模拟了8种不同工况组合下的溢油油膜漂移路径和扫海面积。结果分析表明,潮流场、风场、溢油时刻对油膜的漂移轨迹和扫海面积都有影响,其中溢油时刻对油膜的漂移路径影响最大。 展开更多

关键词 潮流数学模型 溢油 欧拉-拉格朗日理论 扫海面积 溢油路径

在线阅读 下载PDF 职称材料

基于自建GIS及欧拉环游的路径优化算法研究与实现 被引量：1

20

作者 杨明 喻莎 +1 位作者 田永 邓梦航 《物流工程与管理》 2023年第8期73-75,共3页

湖北省烟草公司在自建GIS服务的基础之上,以OSM路网文件为底图,利用高德地图API构建基础路网,通过对路网进行分析处理,得到基础欧拉图。并利用Python代码得到该路网的欧拉环游,之后根据每辆车实际装载量约束,对欧拉环游进行分割,得到代... 湖北省烟草公司在自建GIS服务的基础之上,以OSM路网文件为底图,利用高德地图API构建基础路网,通过对路网进行分析处理,得到基础欧拉图。并利用Python代码得到该路网的欧拉环游,之后根据每辆车实际装载量约束,对欧拉环游进行分割,得到代表车辆运行路线的欧拉环路,从而高效、简洁地实现了烟草物流配送路径优化。 展开更多

关键词 GIS 欧拉环游算法 烟草物流 路径优化 PYTHON

在线阅读 下载PDF 职称材料