最大流最小割定理
最大流最小割定理是最优化理论的定理。根据该定理，在一个网络流中，从源点到汇点的最大的流量，等于它的最小割中每一条边的容量之和。“割”指的是一种边的集合，如果移除这个集合的全部边，就会断开源点和汇点的连接。 最大流最小割定理是线性规划中的对偶问题的一种特殊情况，并且可以用来推导门格尔定理和König–Egerváry定理。 定义 最大流和最小割定理是图论的一部分，因此为了准确定义，我们需要先定义图、流、割，然后再定义这个定理。 图 设 G…
标签：#组合优化
共 16 篇文章
割
图论中，割（cut）是将图的顶点分为两不交子集的划分。割确定了割集，是两端分别在两子集中的边集，称这些边跨过（cross）了割。连通图中，割集唯一确定一个割，识别割有时是通过割集，而非顶点划分。 网络流中，s–t割指使得源与汇不在同一子集的割，其割集只含源一侧到汇一侧的边。s-t割的容量（capacity）定义为割集中所有边的容量和。 定义 割C=(S,\ T)是将图G=(V,\ E)的顶点V分为两子集S、T的划分。 割C=(S,\ T…
组合优化
的最小生成树。寻找最小生成树是涉及组合优化的常见问题。]] 组合优化（）是数学优化的一个子领域，在应用数学和理论计算机科学的领域中，组合优化是在一个有限集合中找出最优对象的一类问题。在很多组合优化的问题中，穷举搜索／枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。常见的例子有旅行推销员问题和最小生成树。 组合优化涉及运筹学、算法理论和计算复杂性理论，在人工智能、机器学习、拍卖理论、软件…
戴克斯特拉算法
{{Infobox algorithm |class=搜索算法 |image=Dijkstra Animation.gif |caption = 戴克斯特拉算法运行演示（找到A，B之间的最短路），本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。 |data=图 堆/优先队列（算法优化） |best-time= |average-time= |SpaceComp=O(|E|+|V|)…
匈牙利算法
匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的。美国数学家哈罗德·W·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家和艾蓋瓦里·耶內的工作之上创建起来的。 詹姆士·芒克勒斯在1957年回顾了该算法，并发现它的时间复杂度为（强）多项式时间。 此后该算法被称为库恩-芒克勒斯算法或芒克勒斯分配算法。原始算法的时间复杂度为O(n^4)，但与理查德·卡普发现可以修…
旅行推销员问题
旅行商问题（，縮寫：TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每對城市之间的距离，求解访-{}-问每座城市一次并回到起始城市的最短回路。” TSP是与车辆路径问题的一种特殊情况。 作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最…
单纯形法
单纯形法（simplex algorithm）在数学优化领域中常用于线性规划问题的数值求解，由喬治·伯納德·丹齊格发明。 下山单纯形法（Nelder-Mead method）与单纯形法名称相似，但二者关联不大。该方法由Nelder和Mead于1965年发明，是用于优化多维无约束问题的一种数值方法，属于更普遍的搜索算法的类别。这两种方法都使用了单纯形的概念。单纯形是 N 维中的 N+1 个顶点的凸包，是一个多胞体：直线上的一个线段，平面上…
集合覆盖问题
集合覆盖问题（Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。 集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。 定义 给定全集\mathcal{U}，以及一个包含n个集合且这n个集合的并集为全集的集合\mathcal{S}。集合覆盖问题要找到\mathcal{S}的一个最小的子集，使得他们的并集等于全集。 例如\mathcal{U} = \{1, 2, 3, 4, 5\…
最大割問題
最大割問題（）是指，給定一張圖，求一種分割方法，將所有頂點（）分割成两群，同时使得被切斷的邊（）數量最大。该问题是一个NP完备问题。 此問題還有另一個變形的版本：每條邊上有各自的權重，要使得被切斷的邊的權重之和最大。 多項式時間的演算法 雖然最大割問題是 NP-hard 問題，但如果圖本身滿足一些條件之下，是存在多項式時間的演算法的。 圖沒有正邊時（權重都是負的） 可以將圖中所有邊都變號（乘上-1），將最大割問題轉成最小割問題。再使用求…
带宽 (图论)
图论中，图带宽问题是用不同整数f(v_i)给图G的n个顶点v_i贴上标签，使得量\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}最小化的问题（其中E是G的边集）。 这问题可以形象理解为，将图的顶点置于沿x轴的不同整数点上，使最长边最短的问题。这种放置称作线性图排列（linear graph arrangement）、线性图布局（linear graph layout）或线性图放置（linear…
A*搜尋演算法
*A搜索算法*（）是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於遊戲中的NPC的移動計算，或网络游戏的BOT的移動計算上。 该算法综合了和戴克斯特拉算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（需要评估函数满足单调性）。 在此算法中，如果以g(n)表示从起点到任意顶点n的实际距离，h(n)表示任意顶点n到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么A算法的估算函数为： …
整数规划
整数规划是指变量取值要为整数的問題，是数学规划中的一个分支。整数规划分为纯整数规划（所有变量取值均为整数）和混合整数规划（变量中有一部分取值为整数）。還有一类整数规划问题，其变量只取0或1值，称之为0-1规划。 参考文献
极值组合学
极值组合数学是组合数学的一个领域，它本身就是数学的一部分。极值组合数学研究有限对象（数字、图形、向量、集合等）的集合在满足某些限制的情况下可以有多大或多小。 极值组合数学大部分都与集合类有关；这就是所谓的极值集合论。例如，在一个n元素集合的子集中，可以成对相交的k元素子集的最大数量是多少？最多能选取有多少个没有包含关系的子集？后一个问题由Sperner 定理回答，最大数量为\binom{n}{\lceil \frac{n}{2} \rc…
线性规划的松弛
and its LP-relaxation]] 在数学中，0-1整数规划的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： :x_i\in\{0,1\} 我们转而使用一对线性约束来代替： :0 \le x_i \le 1. 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种松弛技术把NP难的最优化问题（整数规划）转化为一个相关的多…
分支切割法
分支切割法是用于解决整数线性问题（ILPs），即部分或全部未知数为整数值的线性规划（LP）的问题的组合优化方法。该方法在分支定界法的基础上，使用切割平面以收紧线性规划松弛。如果切割平面仅用来收紧初始的 LP 松弛，则改称为切割分支法。 算法描述 以下假设 ILP 问题为最大化问题。 该方法首先使用单纯形法解决无整数约束的线性问题。获得最优解后，如果有约束为整数的变量取了非整数值，该算法会使用切割平面法以寻找进一步的线性约束：所有可行的整…
车辆路径问题
车辆路径问题（VRP）是一个组合优化和（回答了“为了交付给定的一组客户，车辆车队的最佳路线集是什么？”）。它概括了众所周知的旅行推销员问题（TSP）。它最初出现在1959年George Dantzig和John Ramser的论文中。这篇论文首先编写了算法，并将其应用于汽油交付。通常，这个问题的背景是将位于中央仓库的货物交付给已经订购此类货物的客户。 VRP的目标是最小化总路由成本。 1964年，Clarke和Wright使用一种称为储…