-
题名最小割问题的算法研究综述
- 1
-
-
作者
胡思敏
王晓峰
宋家欢
锁小娜
颜冬
-
机构
北方民族大学计算机科学与工程学院
北方民族大学图形图像智能处理国家民委重点实验室
-
出处
《计算机工程与应用》
北大核心
2026年第3期40-56,共17页
-
基金
宁夏自然科学基金(2024AAC03165,2024AAC03169)
宁夏青年拔尖人才项目(2021)。
-
文摘
最小割问题是图论中的经典NP-难问题,广泛应用于数字医学图像视差处理、图像分割等方面。最小割问题在不同模型下展现出多样的复杂性特征,近年来针对其求解的算法研究不断推进,主要包括基于流的算法、基于树结构的算法、基于收缩的算法、分布式与并行环境下的算法以及其他组合优化策略在最小割问题中的应用等。系统梳理了最小割问题的研究现状与算法发展脉络,从算法设计原理、结构适应性、性能对比等方面展开综述。总结各类算法的优势与局限,归纳适用场景与发展趋势,并展望最小割问题在复杂图结构下的研究方向,旨在为相关研究提供理论支持与方法指导。
-
关键词
最小割问题
最大流问题
图算法
-
Keywords
minimum cut problem
maximum flow problem
graph algorithms
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名一个制造网络的最大流算法
被引量：3
- 2
-
-
作者
张远福
叶正道
唐静波
-
机构
九江学院理学院
-
出处
《工程数学学报》
CSCD
北大核心
2005年第5期774-780,共7页
-
文摘
制造网络流广泛应用于解决水源的调度及工厂的产品运输、分配、合成等问题。本文提出一个制造网络流的最大流算法。
-
关键词
制造网络流问题
最大流
层数
最小截
-
Keywords
manufacturing network flow problem
maximum flow
layer
minimum cut
-
分类号
O224
[理学—运筹学与控制论]
O22
[理学—运筹学与控制论]
-
-
题名多种故障树求解方法的测试与分析
被引量：4
- 3
-
-
作者
蔡佳昆
宋海平
-
机构
北京航空工程技术研究中心
-
出处
《强度与环境》
2004年第2期33-39,共7页
-
文摘
在完善故障树分析中主要参数最小割集、最小路集、不交化最小割集和不交化最小路集之间相互转化运算的基础上,建立了故障树的定性、定量分析的多种方法,提出了不同结构故障树选择适用方法所应遵循的原则。这些方法和选用原则的合理应用能有效的降低FTA的“NP”困难,为FTA的简化提供了新的途径。
-
关键词
故障树
割集矩阵
动态矩阵
不交化最小割集
NP问题
可靠性工程
-
Keywords
fault tree
cut sets matrix
dynamic matrix
non-intersect minimum cut sets
NP problem
-
分类号
TB114.3
[理学—概率论与数理统计]
-
-
题名网络最大流求解算法的研究
被引量：4
- 4
-
-
作者
孙泽宇
丁国强
程志谦
-
机构
洛阳理工学院计算机与信息工程系
-
出处
《微计算机信息》
2010年第3期143-145,共3页
-
文摘
近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展。文章简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法。此算法使得计算网络最大流变得简便,且具有很强的实用性。
-
关键词
网络最大流
算法
最大流问题
最小截
-
Keywords
The maximum flows
Algorithm
Maximum flow problem
The minimum cut
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名基于标号法求解网络最大流算法的研究
被引量：5
- 5
-
-
作者
孙泽宇
-
机构
洛阳理工学院计算机与信息工程系
-
出处
《甘肃联合大学学报（自然科学版）》
2009年第4期64-66,共3页
-
基金
洛阳理工学院基金项目
-
文摘
近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展.本文简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法.此算法使得计算网络最大流变得简便,且具有很强的实用性.
-
关键词
网络最大流
算法
最大流问题
最小截
-
Keywords
The maximum flows
Algorithm
Maximum flow problem） The minimum cut
-
分类号
TP393.3
[自动化与计算机技术—计算机应用技术]
-
-
题名用木桶原理改进最大流算法
被引量：1
- 6
-
-
作者
李苑辉
-
机构
三亚航空旅游职业学院数学教研室
-
出处
《长春大学学报》
2011年第6期47-49,共3页
-
文摘
传统求网络最大流算法需要反复将网络图进行标号和增流,存在步骤繁复、计算量大的问题。本文提出了一种寻找最大流的改进标号法。此方法通过寻找网络中可能的最小割进行标号、分配流量,可以简化计算过程,提高运算效率。
-
关键词
最大流问题
Ford-FuIkerson标号法
木桶原理
最小割
-
Keywords
maximum flow problem
Ford-FuIkerson Labeling Method
Barrel Principle
minimum cut
-
分类号
O157.5
[理学—基础数学]
-
-
题名加权拉普拉斯方法及其理论应用
被引量：1
- 7
-
-
作者
许仕杰
方佳艳
李向阳
-
机构
中国科学技术大学计算机科学与技术学院
-
出处
《微电子学与计算机》
北大核心
2020年第7期12-15,20,共5页
-
基金
科技部网络空间安全项目(2018YFB080340)
基金委杰出青年项目(61625205)
中国科学院前沿科学重点研究项目(QYZDY-SSW-JSC002)。
-
文摘
受到图拉普拉斯理论的部分启发,本文提出了一种加权拉普拉斯方法来更加方便地研究现阶段比较流行的图问题,例如,多层图分割,以及平衡最小割问题.由于加权拉普拉斯策略继承了谱方法的众多优点,因此相比于其他现有的启发式算法,用加权拉普拉斯设计图算法在算法性能上具有更强的理论保证.为了说明其在理论与实际中的强有力的应用价值,我们将分别给出加权拉普拉斯方法在多层图分割和平衡最小割问题上的应用.借助变分法和偏微分方程(PDE)理论,我们在加权分割问题(weighted cut problem),平衡最小割问题(balanced minimum cut problem),以及初始聚类问题(initial clustering problem)之间建立了等价性.其中,初始聚类问题会在基于多层结构的图分割算法的中间阶段出现.这些等价性的建立为基于加权拉普拉斯方法的图算法提供了很强的理论支撑.另外,从加权拉普拉斯方法在平衡最小割问题的应用的角度看,加权拉普拉斯方法使得偏微分方程数值解这一成熟的理论得以应用到图问题的算法设计当中,这也进一步证实了我们提出的加权拉普拉斯方法的有效性.
-
关键词
谱聚类
图分割
图拉普拉斯
偏微分方程
最小割问题
-
Keywords
spectral clustering
graph partitioning
graph Laplacian
PDEs
minimum-cut problem
-
分类号
TP181
[自动化与计算机技术—控制理论与控制工程]
-
-
题名一个改进的网络选址反问题的算法
- 8
-
-
作者
杨保华
陈光亭
柳舟
-
机构
杭州电子科技大学运筹与控制研究所
-
出处
《杭州电子科技大学学报（自然科学版）》
2008年第1期82-85,共4页
-
基金
国家自然科学基金资助项目(10371028)
-
文摘
网络选址问题是研究在给定的网络中,如何放置设施,使得总的花费最小。其反问题可描述为:若设施在网络中的位置已经确定,如何在给定的费用约束下改进网络中的参数,使得在改进后的网络中,距设施最远的节点到设施的距离最小。该文对树网络结构下此类问题的算法做出改进,得到了O(n2)的算法。
-
关键词
选址理论
反问题
树网络
最小割
-
Keywords
location theory
reverse problem
tree network
minimum cut
-
分类号
O224
[理学—运筹学与控制论]
-
