InSAR相位解缠最大流/最小割权值改进算法

InSAR已经在高精度DEM反演中得到了广泛应用,相位解缠技术是影响DEM获取精度的关键步骤之一,然而大梯度变化区域一直是影响解缠结果精度的核心问题。针对该问题,本文提出一种基于势函数改进权值的最大流/最小割相位解缠算法。首先,针对PUMA模型权值设置不合理的问题进行研究,利用外部已有DEM获取相位梯度变化的先验信息,将窗口最大绝对相位梯度值代入相应的势函数公式中获取权值;然后,通过对势函数权值的设置进行阈值调节,解决由于势函数权值设置不合理导致PUMA势函数无法发挥作用引起的解缠错误问题,进而提高大梯度变化区域相位解缠精度;最后,通过仿真数据和真实TanDEM-X InSAR数据对本文算法进行验证,并与已有方法进行对比。结果表明,仿真数据中本文算法可以提高至少44.93%的解缠精度,真实数据中在大梯度变化区域,本文算法较已有算法可以获得更大范围的有效解缠结果。

枚举一个无向图所有最小割集的一种简单算法

本文给出了一种求两终端无向图最小割集的新算法,此算法只需使用最简单的集合运算即可完成,得到的结果与用其它方法得到的结果完全相同,而这种算法无论对于手算还是计算机来完成都是容易的,在本文中算法的具体实现通过例子来说明.

最小割多路径路由算法

在最小割理论基础上提出了最小割多路径(min-cut multi-path,简称MCMP)路由算法,为流量请求选取少量关键路径,并在这些路径间均衡流量,在获得方法易实现性的同时能够有效地控制网络瓶颈链路拥塞.通过实际流量数据在北美和欧洲骨干网络中的实验,对比常用的OSPF(open shortest path first)路由算法和模型中的多路径路由算法,MCMP路由算法可降低拥塞链路负载分别达到41%和20%以上.

网络可靠度分析的最小割递推分解算法

基于不交最小割求解系统失效概率的思想,提出了求解网络系统失效概率的最小割递推分解算法。在此基础上,利用概率不等式给出了失效概率的上、下界,从而可以通过控制上、下界之间的误差来获得计算精度和计算时间之间的平衡。计算实例分析表明,该算法能计算给出中、小型网络失效概率的精确值,并能够高效、高精度地求解出大型复杂网络系统的失效概率。

一种基于最小割的稠密视差图恢复算法

针对经典最小割算法计算量大和适应性不足的问题,提出一种改进的基于网络最小割计算稠密深度图的全局优化方法.首先,根据视差变化与不连续区域之间的关系,定义了具有一定适应性的平滑约束和遮挡约束,然后使用网络最小割算法,求解遮挡情况下的稠密视差.其次,在分析最小割算法复杂性的基础上,给出了一种受限α-扩展(α-expansion)操作,该操作根据灰度连通性和特征点匹配的结果对每次网络构造的顶点进行控制,减少网络中顶点和边的数目,可有效提高计算效率.实验结果显示,该算法在保证视差恢复准确性的前提下,能以较快的速度计算出较理想的稠密视差图.

基于感知机的故障树最小割集算法

在人工神经元网络原理的基础上,提出了一种计算复杂系统最小割集的方法。该方法根据逻辑“与”和“或”门具有线性可分割的特点,选用了基于M-P模型算法的感知机网络作为计算模型,理论推导出故障树中的逻辑关系与感知机模型中神经网络基本单元之间的转换规则,利用该规则可将所建故障树转化成便于编程求解的由神经网络基本单元组成的神经网络树。实例计算结果表明,感知机网络模型适合表达故障树中的逻辑关系,神经网络树所反映的基本事件与顶事件之间的映射关系便于编程求解,并可快速准确地获得复杂系统故障树的最小割集。

网络可靠度分析的改进最小割递推分解算法

在网络连通可靠度分析的最小割递推分解算法基础上,充分利用分解过程中获得的信息,采用合并节点以及合并并联边的方法,有效地简化了分解出来的子网,大幅度降低了算法分解出来的不交最小割和不交最小路数量,从而大幅度地减少了计算时间.3个网络实例计算分析表明,与最小割递推分解算法相比,改进最小割递推分解算法能更高效地计算得到网络系统的连通可靠度,为生命线工程网络的抗震可靠性提供了1种更加有效的分析工具.

网络可靠度分析的最小路算法和最小割算法研究

网络可靠度分析是评价城市生命线工程系统整体抗震性能的主要手段。本文分别从最小路和最小割的角度介绍了网络可靠度分析算法,包括:经典不交最小路(割)算法、最小路(割)递推分解算法和改进最小路(割)递推分解算法。在此基础上,通过实例分析,着重进行了改进最小路递推分解算法和改进最小割递推分解算法的对比分析,分析结果表明两种算法在网络单元不同可靠度水平下具有不同的计算效率,并对引起以上区别的三个主要原因进行了分析。

基于改进最大流最小割算法的露天境界优化及应用

最终境界对露天矿开采效益至关重要,而求解速度慢且结果不准确是最大流最小割算法在露天矿境界优化中的一个固有缺陷。对已有最大流最小割算法进行改进,以净现值(NPV)最大为目标,首先以最大几何境界内的价值块构造有向网络图,通过聚合网络图节点减少弧的复杂度,并在残留网络中对负价值节点增加开采约束,以保证得到的最小割集中正价值块受到负价值块的约束,最终通过C++编程实现该算法对露天矿进行境界优化。经实例验证,该方法科学可行,克服了原算法求解速度慢且结果不准确的弊端,且求解效率提高了近600 s,该算法具有理论上的优越性和实用性。

基于最小割理论的交通疏散逆向车道设置

针对城市道路网中的应急交通疏散问题,研究如何选择合适的路段实行逆向管理。基于网络最大流最小割理论,设计了瓶颈释放启发式算法,通过不断寻找网络最小割来释放潜在瓶颈,增加路网的疏散通行能力。本研究旨在为逆向车道路段的选择提供参考。

FAME:一个标准单元模式下基于最小割和枚举的快速详细布局算法(英文)

随着制造工艺的快速进步 ,超大规模集成电路的物理设计技术在速度和质量上面临很大挑战 .提出了一个快速详细布局算法以适应这种要求 .算法继承总体布局得到的单元全局最佳位置 ,然后采用局部优化将单元精确定位 .FM最小割和局部枚举方法分别用于优化 y和 x两个方向的连线长度 ,这两个方向的优化在同一迭代过程中交替进行 .另外 ,采用改进的枚举策略加速算法 ,对于有障碍和宏模块情况下的布局也加以讨论 .实例测试结果表明 ,FAME的运行速度比 RITUAL快 4倍 ,并使总连线长度平均减小 5% .

基于最大流最小割算法的事件检测方案

文中把最大流最小割算法应用于无线传感网络的事件检测中,针对边沿陡峭的事件,设计事件区域检测算法(G-Cut).该算法首先将相邻节点的传感数据转化为权值,形成流网络;利用最大流最小割算法切割流网络,获得事件边界;再根据上传信息隐含的方向,确定事件区域.以野外火灾为例进行仿真实验,结果表明:文中算法事件检测准确度高,节点计算量低;针对多事件区域,在不增加节点计算量和通信量的情况下,仍可保证其检测准确度.

基于参数化最小割方法的SAR图像区域分割

由于SAR图像中存在大量的相干斑噪声,最小割准则(Minimum Cut Criterion)倾向于分割出小的孤立点集,因此最小割准则难以直接应用于SAR图像分割中。本文给出了一种可以根据需要来控制分割区域大小的参数化最小割准则(Parametric Minimum Cut Criterion),由此减少小的孤立点集的产生。该准则通过构建参数化割树(Parametric Cut Tree)得到理论最优解。为了参数化最小割准则更有效地应用于SAR图像分割,结合了区域分割方法中的四叉树分裂合并技术,给出了一种基于图论的SAR图像区域分割算法。在利用四叉树技术分裂图像时,根据SAR图像的统计特性,给出了一种新的区域一致性度量,有效地抑制了相干斑噪声的影响。实验结果表明了本文方法的有效性。

并行最小割算法及其在金融社交网络中的应用

有效实施金融监管已成为金融健康发展的必要保证.若能够在金融社交网络中,找到一部分承载网络中所有信息流动的关键节点,便能实现整个金融社交网络的有效监管.金融社交网络图规模通常较大,须开发大规模图处理并行算法.本文提出基于分布式图处理平台Pregel的并行最小割算法.实验基于Apache Spark平台开展,所用数据均来自BoardEx数据库.实验结果表明,在大规模社交网络图的处理中,该算法具有良好性能.利用该并行算法得到金融社交网络图的最小割,便可有效实施金融监管.

最小割与深度学习联合优化的室内粘连点云分割方法

随着数字城市的发展,城市三维模型重建对三维点云结构化的需求与精度要求越来越高。如何有效准确地分割室内语义模型与三维重构是当前研究的热点问题。点云分割分类是室内点云结构化的重要基础,如何将粘连点云构件进行准确分割并用于室内点云结构化,是当前城市建模的难点。本文提出了一种面向室内粘连点云数据的分割分类方法。首先,利用深度学习网络处理室内点云数据;其次,对点云数据进行标签分类,得到目标标签点云;然后,利用欧氏算法对目标点云进行聚类分割,通过室内语义构件包围盒信息计算各目标中心点坐标与水平半径;最后,利用点云最小割实现室内粘连点云的准确分割。利用3组室内场景中获取的数据对分割方法的精度及有效性进行了验证。结果表明,该分割优化方法具有较高的精度与数据完整性。

基于最小割模型的快递企业配送中心选址建模研究

同时考虑了同城和城际两种配送业务,引入最大权闭合图,应用最小割原理,给出了一个高效的方法来建立快递企业配送中心。

参数最小割中基于层次化融合的前景种子生成算法

参数最小割是一种常用的似物性推荐方法,主要用于在图像中快速定位物体区域。针对该类方法中容易生成大量无效前景种子影响处理效率,提出一种基于层次化融合逐级筛选的前景种子生成算法。基于由颜色、纹理复杂度控制的层次化融合方法得到候选区域集,从候选区域集中结合尺度变化率选出具有稳定外观的候选前景种子,最后基于似物性分数排序,确定有效的前景种子。实验结果表明,提出的前景种子生成算法具有较高的物体发现率,将其应用于参数最小割方法中,在使用更少的种子、生成较少区域时,可达到与前沿算法相近的区域级物体定位能力。

基于最大流最小割的电网静态安全关键断面辨识方法

提出了一种基于最大流最小割定理的关键输电断面识别方法。算法考虑电网潮流分布及载流能力,转化为有向加权图扫描求解最小割。构建搜索树存储结果,并根据网络分割搜索输电断面,可以快速准确地辨识出全部存在"N-1"、"N-2"过载风险,且具有明确割集特征的输电断面;基于功率转移因子可快速计算输电断面静态安全功率极限。在新英格兰39节点电力系统和IEEE300节点算例中验证了提出方法的准确性。

一种求解最小割的警示传播算法

最小割问题(minimum cut problem)是NP(Non-deterministic Polynomial)难问题,警示传播算法(warning propagation)是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后,选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法.

基于最小割图分割的社区发现算法

该文证明了模块度最大化问题可以被转换成为原网络上的最小割图分割问题,并且基于该证明提出了一种高效的社区发现算法。同时,该文创新性地将模块度理论与当今比较流行的统计推理模型相结合:首先,这些统计推理模型被转化为模块度最大化问题中的零模型;其次,统计推理模型中的目标函数被修改并应用于本文的最优化算法中。实验结果显示,无论是在真实世界网络还是在人工生成网络中,该文提出的算法均具有高效和稳定的发现社区的能力。