一类多旅行商路径均衡规划算法

本文研究了多个旅行商旅行多个城市的路径规划问题,提出了基于系统科学中的"吸引子"意义下的路径规划算法.路径规划的目标是均衡各旅行商的旅行路径长度并使得路径总和得到优化.为此提出了一种求解该问题的启发式算法思想,并结合邻近点和最短路径设计了算法,同时由复杂度分析知该算法的计算时间复杂度比以往的要低.     

旅行商问题的一种启发式算法

用一个有向图表示旅行商避开某一城市到1个顶点的所有最短路径,并在每条弧上定义一个线性表,用以记录所有包含该弧的图,从而将判断某条弧和某个顶点是否应该存在于某个子图中的最短路径上的问题转化为线性表的相关操作,进而讨论了图上的弧都在某一最短路径上的充要条件,以及如何顺序产生第1列到第n列的顶点上的图,如何从这些图上搜索出近似最优解的方法.     

聚类处理的蚁群算法在旅行商问题中的应用

针对大规模旅行商问题具有区域分布的族类特征,采用最小方差法将城市样本点聚成k个城市群,利用蚁群算法,求出每个城市群内部城市的最短路径及城市群之间的最短路径.提出了一种新的城市群连接方式及标记方法,使得从任一个城市出发,以该方式可对每个城市群的连接城市进行标记,同时,利用循环搜索的方法可得到每个城市群的连接方式,最终得到全局最短路径的一个满意解.最后利用TSPLIB提供的实验数据,对算法的正确性进行了验证.     

基于极小代数赋权有向图最短路径求解算法

应用极小代数给出了求解简单有向赋权图最短路径问题的代数算法.该算法基于赋权有向图的直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵Ak和最短路径距离矩阵A+,并依此确定出赋权有向图的最短路径以及最少步数最短路径.与Dijkstra算法相比较,所提出的代数算法求解路径规划问题能够较快地得到特定的最短路径及其长度.     

交通网络最优安全路径选择模型与算法

针对交通网络任意路段均可能发生中断的最小损失路径选择问题,提出交通网络最优安全路径选择模型,并设计了2种不同网络结构下最优安全路径选择算法.首先用模型计算任意一条路径上每条边中断后产生的从起点到终点最短替代路径长度的最大值,然后选择一条最短替代路径长度最大值最小且自身长度最小的路径.在网络中,当最短路径删除后该网络依然连通时,最优安全路径问题转化为最短路径问题,其计算复杂度为O(n2);当最短路径删除后该网络不再连通时,最优安全路径问题转化为最小最大问题,其计算复杂度为O(mn),且仅与网络中节点和边的数量有关.最后,结合交通网络的实际情况对最优安全路径进行了算例分析.     

行拉丁矩横截的一个算法

一个m×n阶矩阵,其元素取自集合{a1,a2,…,ak},满足每一行的元素互不相同,称这个矩阵为基于k的一个m×n阶行拉丁矩.设R是一个m×n阶拉丁矩,它的n个不同行不同列的且互不相同的元素称为R的横截.当m＞2n-2时,给出了一个求m×n阶行拉丁矩横截的新方法,并证明了当k＞n时,任一个基于k的(2n-2)×n阶行拉丁矩有横截存在.     

关于行拉丁矩的横截的一个猜想

一个m×n阶矩阵 ,其元素取自集合 {a1 ,a2 ,… ,ak} ,满足每一行的元素互不相同 ,称这个矩阵为基于k的一个m×n阶行拉丁矩。设R是一个m×n阶拉丁矩 ,它的n个不同行不同列的且互不相同的元素称为R的横截。1 998年 ,DRISKO提出了一个猜想 :假设k≥n ,令R是一个 ( 2n-2 ) ×n阶基于k的行拉丁矩 ,则R或有一个横截 ,或R同痕于行拉丁矩A(2n- 2 )×n,这里A(2n- 2 )×n 是 ( 2n-2 )×n阶矩阵 ,它的元素是由记号 1 ,2 ,… ,n ,组成 ,其中前n -1行为 ( 1 ,2 ,… ,n-1 ,n) ,其余的n-1行都为 ( 2 ,3 ,… ,n ,1 )。本文利用行拉丁矩的配对算法 ,证明了这个猜想是成立的     

基于随机机会约束规划模型的旅行商问题及其求解算法

为了提高旅行商的效率,将旅行时间引入旅行商问题(TSP),以最短时间和最短路径为目标对旅行商问题进行求解。假设旅行商在不同城市间的旅行时间服从正态分布,以最短路径为优化目标,将旅行时间以一定的置信水平成立作为机会约束条件,构建了旅行商问题的随机机会约束规划模型。提出已构建模型的确定性等价类,设计出遗传算法并编写算法代码,以一定规模的城市为例进行仿真验证。结果表明:给定期望的总旅行时间和置信水平时,可经过计算得出最短距离,并绘制出最优路径图,同时验证了所提出模型的可行性和算法的有效性。     

n维超立方体中点不交的最短路径

最短路径问题一直是并行计算系统的研究热点之一。主要研究了n维超立方体Qn上的点不交的最短路径问题,采用数学归纳法证明了如下结果:Qn中任意两节点s、t之间一定存在k条长度为k的点不交最短路径,其中k=H(s,t)(k≤n)为s、t之间的Hamming距离。     

基于改进蚁群算法的柑橘采摘最优路径

为了提高柑橘采摘效率,对柑橘采摘的最优路径进行研究.将柑橘采摘的路径规划抽象为旅行商问题的解集,建立柑橘果实点3维模型.在蚁群算法的基础上,引入随时间改变的自适应信息素浓度更新机制,提出改进的蚁群算法.仿真实验结果表明:改进蚁群算法的路径长度比蚁群算法的路径长度短;改进算法采用蚁周模型进行路径规划时有较高的效率.     

PMI中的证书路径处理机制的优化

在EPMI中,证书路径的处理包含属性证书路径处理及各属性证书相对应的公钥证书路径的处理。其中证书路径构造尤为复杂和耗时,路径验证算法也没有考虑顺序,缺乏相应性能分析,阻碍了PMI的应用推广。提出一种优化的路径处理方案．给出了实现的流程图和算法,并进行了性能分析。     

实现双轨迹和平行直线轨迹的齿轮五杆机构综合

本文讨论了齿轮五杆机构实现双轨迹和平行直线轨迹的综合方法。利用计算机绘图分析了各个结构参数对两连杆曲线的影响规律,对实现平行直线轨迹的齿轮五杆机构,给出了结构尺寸关系数据表和误差分析方法。为综合具有平行直线轨迹的齿轮五杆机构提供了有效的方法。     

X=3的六角系统的构造

首先证明了在一个ｘ＝３的六角系统中，起始路和终止路最多共有三条，然后，对起始路和终止路进行分类，利用张福基等关于ｘ＝１，２时六角系统的构造，得到了下述结论：Ｇ是ｘ＝３的六角系统的充要条件为Ｇ是Ⅲ，Ⅳ，Ⅴ，Ⅵ，Ⅶ型图中的一个。     

移动机器人路径规划算法综述

为提高机器人路径规划的搜索速度,缩短搜索时间,总结归纳移动机器人在路径规划问题上的算法及其特点。首先回顾移动机器人发展历史,并对路径规划技术进行概述; 其次对移动机器人路径规划进行分类总结,并从移动机器人对环境掌握情况的角度出发,将移动机器人路径规划分成全局规划和局部规划两类,然后对全局规划和局部规划的相关算法进行综述,同时对相关算法发展现状及优缺点进行总结。最后指出机器人路径规划技术在改进算法、混合算法、多机器人协作、复杂环境以及多维环境下进一步深入研究的未来发展趋势。     

模糊因果聚类模型在高炉焦比预测中的应用

通过通径分析,对高炉现场采集的数据进行处理,在给定的描述高炉系统的诸多变量中,利用最小剩余通径系数确定影响目标函数的主要变量因素·将诸因素关系处理为直接通径和间接通径,并对其进行了排序,找出了影响指定目标函数:焦比的主要直接通径和间接通径·综合直接通径和间接通径效果,确定了高炉炉顶温度、料批、矿批重、焦炭负荷和[Si]既是影响焦比的直接原因,也是其他因素对焦比作用的间接原因·     

无向图中严格第三短路问题的多项式时间算法

给定一个无向图G=(V,E;w;s,t),其中s,t是2个固定顶点,w:E→R+是边的长度函数.最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者.对正权重无向图中严格第三短路问题给出一个O(n4)多项式时间算法.     

超链接文本中的连贯

连贯理论一直以来针对的是线性文本,本文试图运用语用学的连贯理论,从交际者共享知识的角度描写超链接文本中的连贯。超链接文本最基本的要素是文本路径,它可分为预先定义路径和自选路径。本文分别阐述了由这两种路径构成的超链接文本的连贯。论文尝试指出,从语用上来说,超链接文本中的连贯与普通线性文本一样,是建立在作者与读者共同遵守的语篇组织模式和运用世界知识的推理之上。人们具有的世界知识和推理能力,对理解超链接文本的连贯起重要作用。     

数字仿真器中的时间校验探讨

针对事件驱动仿真检测时间延迟的困难，提出用时间校验网络来检测时间延迟。论述时间校验的几种方法及在时间校验中的几个问题。     

关于支配圈和支配路的存在性

圈C称为图G的支配圈,若对G中任一点v,至少有圈C上的一个顶点与之邻接.类似定义图G的支配路.本文讨论了图中支配圈和支配路的存在性,得到下列结果:(1)设G是有n个顶点,ε条边的k-连通图(k≥1),若ε>((n-k)/2)~2-(3n-k)/2+4,则G中存在支配圈.(2)设G是有n个顶点的k-连通图(k≥2),若对图G中任何有k个顶点的独立点集{v_0,v_1,…v_(k-1)},满足N(v_i)∩N(v~i)=φ(0≤i≠i≤k-1),有~(k-1)∑_(i=0)d(v_i)>n-2(k+2)成立,则G中存在支配路.     

关于SPS-图的一个充分条件

如果图中的一条路不是其他任何路的子路,则称这条路为该图的一条极大路。图G的路谱指的是G中所有极大路的长度构成的集合,记为ps（G）。对于一个阶为n的图G,如果存在一个正整数s（G）使得ps（G）={s（G）,s（G）＋1,…,n-1},则称G为一个SPS-图。本研究证明了对于任意的2-连通图G,如果G中任何导出子图都不与K1,3或P5同构,则G是一个SPS-图或者是一类路谱特殊的图。