海上油田群水域应急救援船舶路径规划方法研究

文中提出了基于Dijkstra-ACO算法的海上油田群水域应急救援船舶路径规划方法.根据油田群水域的环境特征,运用Maklink图论算法构建救援船舶路径规划的二维空间模型,并结合Dijkstra算法与ACO算法提出应急救援船舶的路径规划算法,以山东东营油田群水域为例进行模型验证.结果表明:基于Dijkstra-ACO的应急救援船舶路径规划方法优于传统路径规划方法.

遗传优化的谱聚类方法研究

传统的谱聚类对初始化数据敏感,聚类结果随不同的初始输入数据而波动。针对上述问题,提出了一种基于遗传算法的谱聚类算法,该算法克服了谱聚类算法对初始数据的敏感性,得到较稳定的聚类结果。与遗传k均值和谱聚类算法相比,该算法在模拟数据和UCI数据集上获得了较好的聚类性能。

结合图论的供水管网PMA分区方法

供水管网压力分区(PMA)以压力调控为主,兼顾区域计量,可有效地控制城市管网漏失,为此,提出结合图论的PMA分区方法,首先运用自适应AP聚类算法结合经济性计算对供水管网进行初步分区,确定分区数目;然后运用迪杰斯特拉(Dijkstra)算法计算各个聚类中心点到水源的最短路径,确定各个分区的供水管段;建立分区边界优化模型,运用模拟退火算法求解该模型;最后结合人工经验对部分分区进行适当合并,形成最终方案并运用于Y市供水管网实例,取得良好结果.该种分区方法是以计算机算法为主体并结合人工经验,很大程度降低分区的工作量,并且比传统的人工试错分区具有更大的搜索空间,可用于指导实际供水管网的PMA分区.

中原城市群轨道交通干线选择研究——基于图论最小生成树Kruskal算法

中原城市群的发展是中部崛起的关键所在。中原城市群交通网络中轨道交通干线的构建,必将对其建设与发展起到巨大的推进作用。从计算机学科图论的角度入手,利用Kruskal求解最小生成树算法,对构建最小投资中原城市群快速干线进行了理论性研究。首先用无向图的概念对中原城市群九城市及其间距离进行图的抽象,然后给出算法过程以及实质求解意义并获得结论,最后论述了该算法的不足并对算法的结论进行了现实修正。该算法在油气干线、超高压电力干线等大型基础设施建设中亦存在一定应用前景。

基于蚁群算法的半导体生产线调度方法研究

为了解决具有可重入特性的半导体生产线调度问题,提出基于蚁群算法的半导体生产线调度模型(ASWFSM)。在模型中,利用图论的方法把调度方案的寻优过程转换为蚂蚁对有向图的搜索,并且,引入专家系统作为推理机避免了寻优过程中对可行节点判断的复杂性。仿真试验证明,此模型具有良好的调度效果和稳定性。

基于图论Gomory-Hu算法的快速图像分割

Gomory-Hu算法是图论中的经典算法,用于寻找图的最小流割等价树,具有最优解,但是该算法很难处理较大的图像,而且倾向于分割出孤立点集。为此,给出了孤立点的判定方法,并提出一种基于Gomory-Hu算法的图像分割方法。该算法首先通过快速聚类减少图中顶点数目,然后构造新的赋权图,并应用Gomory-Hu算法对图进行最优划分,得到分割结果。提出的算法对多幅自然图像进行了分割实验,平均分割时间在3 s内。实验结果证明了算法的有效性和快速性。

基于网格和图论的初始聚类中心确定算法

针对传统K-means算法随机选取初始聚类中心,易造成准则函数收敛速度慢、聚类结果陷入局部最优等问题,提出一种基于网格和图论的初始聚类中心确定算法。该算法将数据空间网格化,通过在网格单元上形成树的连通分支来选取初始中心点。采用模拟和真实数据集对该算法选取的初始中心进行测试,实验结果表明,改进后的K-means算法在降低时间复杂度、减少迭代次数以及提高聚类精度方面都取到了较好的效果。

图论的算法和应用研究

图论在学科中属于离散数学,因此它具有离散数学的许多特点。图论中许多概念和理论的产生和发展是相互独立的,因而被分成许多相互独立的专题,其算法是解决问题的一系列步骤的集合,是离散数学重要的组成部分。文章首先介绍一些图论的理论以及图的相关概念,然后对图论中经常使用到的算法作了研究和讨论,最后,并以一个具体的图论模型论述通过建立图论模型来解决实际问题了。

全双工下基于最优匹配的D2D用户簇资源分配

全双工模式下,D2D链路的吞吐量约为半双工D2D链路的2倍,但全双工通信在带来吞吐量增加的同时也造成了严重复杂的干扰。由于频谱资源的匮乏,考虑多个D2D用户复用一个蜂窝用户的场景,此时共享同一蜂窝资源的D2D用户对之间还将产生同频干扰。该方案通过图着色对D2D对进行分簇,使蜂窝用户在保证通信质量的条件下能复用足够多的D2D用户对;使用最优匹配算法为每个D2D簇分配最优蜂窝信道资源,达到减少链路间干扰的同时增大系统吞吐量的效果。仿真结果表明,该方案能有效提高频谱资源的利用率,增加系统容量。

基于多油田的渤海黄河口凹陷区域渗透率评价模型

在储量评价阶段,各油田的渗透率计算主要依赖于该油田的岩心孔渗关系模型,但对于取心井段代表性差的油田,孔渗关系模型计算的渗透率误差较大。基于渤海黄河口凹陷已开发油田储层测井响应特征的相似性,利用图论多分辨率聚类算法对该区域多个油田取心井段测井曲线进行测井相划分,并结合测录井资料,确定了测井相与岩相的对应关系,建立了基于测井相岩相约束的区域渗透率评价模型。应用结果表明,与岩心资料少且代表性差油田的同一指数关系模型计算的渗透率相比,基于测井相岩相约束的区域渗透率评价模型计算的渗透率与岩心分析渗透率符合程度更高,明显提高了渗透率的评价精度。该模型为黄河口凹陷相似油田在不取心情况下提供了一种渗透率评价方法,节省取心费用,具有一定的指导意义。

无线传感器网络的图论聚类算法研究

为了解决传感器通过三层网络结构向融合中心传递数据时必须进行分簇的问题,提出了一种采用图论方法进行聚类分簇的具体实现算法及实现过程,并通过实验验证了图论分布式聚类算法相对于集中式K-平均算法的性能优越性。

基于最小最大割算法的阈值分割算法

近年来,建立在图论基础上的谱聚类算法作为一种新型的工具被应用于图像分割。其本质是将图像分割转化为最优化问题,其中的最小最大割算法(Min-max cut)能充分满足聚类算法的准则。算法实现过程中,把最优化准则转化为特征系统进行求解。该实现方法计算复杂,随着图像尺寸的增加,所需存储空间和计算时间复杂度都会增加。在实现最小最大割算法时,用基于灰度级的权值矩阵代替通常所用的基于图像像素的权值矩阵来描述图像各像素的关系,确定分割的阈值。实验表明,此方法实现的最小最大割算法实现简单、实时性高,具有自动分割等优越的分割性能。

城市集中型充电站规划方法

为实现城市集中型充电站合理规划,在分析影响电动汽车充电站规划因素的基础上,根据电动汽车空间分布特点,提出基于图论的集中型充电站选址图模型。结合图中央点理论对K-means聚类算法进行改进,提出了集中型充电站服务范围最优划分和站点选址算法。采用某中央城区实际规划算例计算,并与K-means和Vor-onoi图计算几何法比较,计算结果表明,本文所提方法具有更好的规划效果,获得更均衡的服务区域划分和更短的充电路径距离。

基于改进贪心算法的无人机集群协同任务分配

无人机集群由于其强大的信息共享与行为协作等优势,在军事、民用及科研等领域发挥了重要作用。然而无人机集群在执行大规模任务时,任务的时间约束、时序关系以及性能要求都对集群任务的协同规划与分配提出了巨大的挑战。针对多无人机协同飞行约束下的任务分配问题,本文提出了一种基于改进贪心算法的无人机集群协同任务分配算法,在保证无人机间协同飞行以及任务间时序约束的前提下,优化无人机集群的飞行时间与距离。该算法借鉴图论中的有向图来表示任务间协同飞行约束关系,并依据改进的贪心算法对任务进行局部最优分配、优化,有效获得时间最优、距离最优两种策略下的近似最佳飞行路径。在构建的覆盖扫描任务场景上进行试验对比,验证了本文所提算法的有效性,该算法相较于传统解决方法在时间与距离性能上最高能提升20%。

呼和浩特市国土空间功能评价及优化分区研究

市域国土空间功能评价研究是市级国土空间规划编制的基础,准确评价国土空间功能及分区可为规划实施和用途管制提供科学依据。以乡级行政单位为评价单元,通过归并分类、全局与局部空间自相关等方法分析国土空间功能及其空间分布特征;采用两维图论聚类算法,在空间邻接性和区域完整性前提下对国土空间功能进行分区,并根据分区结果提出发展建议。结果表明:1)生产、生活功能高值在城市建成区高度聚集,并呈圈层状向外递减;生态功能具有山水尺度依赖效应,其功能值在建成区下降明显,生产、生活功能的高度集聚对生态功能具有一定的胁迫效应。2)生产、生活、生态功能空间分布均呈空间正相关性,为显著集聚状态;生产功能与生活功能在中部有较高的协同性,生态功能协同性较低。3)研究区划分为城市生产生活核心发展区、工农生产功能主导区、大青山生态功能屏障区、阴山中山农业生产主导区、生产生活功能提升区。4)根据各分区特征提出功能提升发展建议。

基于集合论与图论的餐饮推荐聚类算法

为了提高餐饮推荐系统的准确率,提出一种基于集合论和图论的餐饮高维非数值型数据聚类算法.首先将菜品数据进行预处理,找出需要的特征,删除不必要的特征,再将这些特征以集合的形式输入到系统中,使用改进的杰卡德相似系数对集合进行相似度计算,得到以集合表示方式的菜品数据间的相似度,接着将所有的数据转换为无向图,最后利用图形聚类算法进行聚类分析.实验结果表明:所提出算法的聚类过程不受噪声影响,具有很好的实用价值.