寻求中国货郎担问题最短回路的多项式时间算法

研究求解中国货郎担问题最短回路的多项式时间算法．首先利用计算几何中凸亮与中轴的结构将点集划分成若干个子点集，然后反复采用求子点集凸壳及划分剩余干点集的方法，求得通过于点集的子路径，最后将各子路径连接成一条回路．中国货郎担问题存在多项式时间算法求得最短回路．所设计的算法的时间复杂性为O（n2lbn），将它用于中国货郎担问题，得到一条长度为15404km的最短回路．与陈沐天等人采用几何分块方法所得的最短回路相一致．

卫勤最短回路问题的遗传算法求解

本文采用了一种基于环形交叉算子和环形变异算子的改进遗传算法IGA(Improved Genetic Algorithm),同时在遗传算法中结合贪心策略来解决卫勤最短回路问题(SCPHS)。对比试验结果表明,本文给出的算法能够在一个较短的时间内找到一个满意解;相对于文献中给出的其它算法,该算法更加有效。

寻找无向图中回路的并行算法

对无向简单图Ｇ＝（Ｖ，Ｅ），｜Ｖ｜＝ｎ，｜Ｅ｜＝ｍ，给出对下述问题的ＮＣ算法：（１）寻找Ｇ中最短回路；（２）寻找Ｇ中最短偶（奇）长度回路；（３）求解Ｃｋ，ｋ＝３，４，这里Ｃｋ表示Ｇ中长度为ｋ的回路．

再生哈密顿回路的边数条件

为了缩小最短哈密顿回路的搜索空间,从而提高TSP算法的搜索效力;并依据图论中邻点交叉边的性质,对哈密顿回路内边进行全面分析和统计,给出和证明了再生哈密顿回路的边数条件P(n),这在图论中是未曾有过的.进而证明了最短哈密顿回路必至少含有前P(n)条小边之一的结论.该结论可广泛应用于TSP搜索算法中,减少搜索时间.

基于改进聚类算法的关键输电断面搜索方法

为了有效避免切除故障或过载线路后连锁跳闸事故的发生,提出一种基于改进模糊C均值聚类算法的关键输电断面搜索方法。该方法首先采用改进粒子群算法更新聚类中心,解决聚类算法对初始聚类中心敏感的问题,然后基于改进的聚类算法得到初始输电断面;其次运用Floyd算法搜索含断开线路的最短回路和次短回路,补充漏选的线路到初始输电断面内,构成候选输电断面;最后利用提出的复合因子判据筛选候选输电断面,进而确定关键输电断面。以IEEE 14节点和IEEE 118节点标准系统为例,所提方法可精准搜索得到系统内受切除线路影响较大且可能存在连锁跳闸风险的线路,即关键输电断面。结果表明采用该方法得到的关键输电断面更具有实用性和工程指导价值。

一种基于TSP问题的启发式搜索算法研究

旅行推销员问题(TSP问题)是算法研究的经典问题,该问题属于典型的NP难题。研究解决此问题尽可能少计算时间的算法具有重要意义。本文通过研究一种启发式搜索算法,把TSP问题的矩阵通过一种启发式准则约简和搜索,尽量地简少了搜索的范围。

灾区巡视路线的分析

本问题是一个典型的最短回路问题 ,我们借助于最小生成树法和动态规划的方法 (用点权代替边权 ) ,建立了三个模型 ,再运用重绕最小生成树法求解三个模型 .在整个过程中我们还运用了 AUTOCAD制图、EXCEL制表、WORD和 WORDPRO处理文档 ,以及其他一些计算机软件 .本文的模型具有较强的实用性和普遍性 .建模过程中 ,用点权代替边权 ,是对动态规划的一个合理推广 .

三维无线传感器网络寿命和动态路由算法

无线传感器网络(WSNs)寿命受到电池能量的制约,利用无线能量传输技术对传感器节点进行充电,可以解决无线传感器网络的能量问题。以三维无线传感器网络为研究对象,证明三维最短Hamilton回路为无线充电设备遍历网络中节点的最优路径,提出了网络的连续时变模型,并简化复杂度为多项式的离散T+1阶段线性规划模型。仿真结果表明:通过运算离散T+1阶段线性规划模型能够使无线传感器网络持续运行。

差分进化算法在旅行商问题中的应用

为了解决旅行商在实际应用过程中存在的离散差值及求解问题,研究差分进化算法在旅行商问题中的应用。通过差分粗粒度并行预处理,构建交叉进化运算层级,建立迭代旅行商离散矩阵,设计无线差分积累应用模型,完成C2Opt算子重复排序,设定逆向旅行域的同时,采用迭代进化完成旅行商问题的应用。测试结果表明:设计算法的规划线路数相对较多,可以达到21条方案,对旅行路线规划的最优解更加可靠、精准。