# leetcode **Repository Path**: liuyoupei123/leetcode ## Basic Information - **Project Name**: leetcode - **Description**: No description available - **Primary Language**: Unknown - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 1 - **Created**: 2024-11-25 - **Last Updated**: 2024-11-25 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README @[TOC] 课程笔记 ~~~bash https://gitee.com/fakerlove/leetcode ~~~ 课程视屏 ~~~bash https://www.bilibili.com/video/BV1254y1r71T ~~~ # 0. 开篇三个问题 ## 0.1 货郎问题---计算复杂性 ### 01背包 ## 0.2 调度和投资问题 ### 贪心算法 ## 0.3 计算复杂度的界定--排序问题 # 1. 算法分析技术 ## 1.1 影响程序运行时间的因素 **算法** 有限条指令的序列，这个指令序列确定了解决某个问题的一系列运算或操作 ### 1.1.1 因素 * 程序所依赖的算法 * 问题输入的规模和分布 * 计算机系统性能 + 硬件系统 + 软件系统 ### 1.1.2 抽象机 设抽象机提供由$m$个基本运算(也可称为语句)组成的运算集 $O=\{O_1,O_2.\cdots,O_m\}$ 每个基本运算的执行时间是有限常量 设执行第$i$个运算$O_i$所需的时间是$\alpha_i,1\le i\le m$​​ ### 1.1.3 算法的时间复杂度 **概念** 针对指定基本运算，计数算法所做运算次数 **基本运算** 比较，加法，乘法，指针，交换 ## 1.2 渐近表示法表示的算法时间复杂度 使用渐近表示法表示的算法时间复杂度 ### 1.2.1 五种符号 #### 1) 大$O$​记号 定义:设f和g是定义域为自然数集N上的函数，若存在正数c和$n_0$,使得对一切$n\ge n_0$有 $$ 0\le f(n)\le cg(n) $$ 成立，则称f(n)的渐近的上界是$g(n)$, 记作$f(n)=O(g(n))$ 比如$f(n)=n^2+n,$则$f(n)=O(n^2)$,取$c=2,n_0=1$即可 #### 2) 大$\Omega$​记号 设f和g是定义域为自然数集N上的函数，若存在正数c和$n_0$,使得对一切$n\ge n_0$有 $$ 0\le cg(n) \le f(n) $$ 成立，则称f(n)的渐近的下界是$g(n)$​​​ 记作$f(n)=\Omega(g(n))$​ #### 3) 小$w$​​记号 设f和g是定义域为自然数集N上的函数，对于任意正数c都存在$n_0$,使得对一切$n\ge n_0$有 $$ 0\le cg(n) \le f(n) $$ 成立，则记作$f(n)=w(g(n))$​​ #### 4) 小$o$​记号 定义:设f和g是定义域为自然数集N上的函数，若对于任意正数c都存在$n_0$,使得对一切$n\ge n_0$有 $$ 0\le f(n)\le cg(n) $$ 成立，则记作$f(n)=o(g(n))$ #### 5) 大$\Theta$​​​记号 若$f(n)=O(g(n))$,且$f(n)=\Omega(g(n))$, 则记作 $$ f(n)=\Theta(g(n)) $$ 例子$f(n)=n^2+n,g(n)=100n^2$,那么有$f(n)=\Theta(g(n))$​ * f(n)的阶与 g(n)的阶相等. * 对前面有限个n值可以不满足条件 ![image-20211117212342026](picture/image-20211117212342026.png) ### 1.2.2 渐近线定理 * 如果$\lim_{n\to \infty}\frac{f(n)}{g(n)}$​存在，并且等于某个常数$c>0$​,那么$f(n)=\Theta(g(n))$​ * 如果$\lim_{n\to \infty}\frac{f(n)}{g(n)}=0$,那么$f(n)=o(g(n))$​ * 如果$\lim_{n\to \infty}\frac{f(n)}{g(n)}=+\infty$​,那么$f(n)=w(g(n))$​ * 如果$f=\Omega(g)$且$g=\Omega(h)$,那么$f=\Omega(h)$ * 如果$f=\Theta(g)$​且$g=\Theta(h)$​,那么$f=\Theta(h)$​ **例子** $f(n)=\frac{1}{2}n^2-3n$ 满足$f=\Theta(n^2),f=O(n^2),f=o(n^3)$ ### 1.2.2 算法按时间复杂度分类 * 对数多项式级 * 多项式时间算法 $n,n^2,nlogn,n^{\frac{1}{2}},\cdots$​ * 指数时间算法 $2^n,3^n,n!,\cdots$ ## 1.3 递推关系 ### 1.3.1 概念和例子 * 替换法 * 公式法 + 特征方程，特征根 + 递推方程的解和特征根的关系 + 解的线性性质 + 无重根下的通解结构 + 求解实例 * 迭代法 + 直接迭代 插入排序最坏情况下的时间分析 + 换元法 + 迭代归纳(差消) + 递归树 * 尝试法 * 主方法 + 主定理 + 主定理的特殊形式 + AKRA Bazzi定理 设序列$a_0,a_1,\cdots,a_n,\cdots$，简记为$\{a_n\}$,一个把$a_n$与某些个$a_i(i主要讲主定理 参考资料 ~~~bash https://zhuanlan.zhihu.com/p/100531135 ~~~ **问题描述** 我们要处理一个 规模为n的问题通过分冶，得到a个规模为$\frac{n}{b}$的问题，分解子问题和合并子问题的时间是$f(n)$ $T(n)=aT(\frac{n}{b})+f(n)$ **主定理的内容** ![这里写图片描述](picture/2016090616344130.png) ![img](picture/v2-a0299344bcf4a294e5c05d0dd65e6009_720w.jpg) #### 主定理的例子 Karatsuba大整数的快速乘积算法的运行时间（时间复杂度的递推关系式）为$T(n)=O(n)+4T(\frac{n}{2})$ 时间复杂度$O(n^2)$ **例子** $T(n)=16T(\frac{n}{4})+n$ $a=16,b=4,n^{log_b^a}=n^2,f(n)=n标准形 常系数线性齐次递推方程的标准形 $$ \begin{cases} H(n)-a_1H(n-1)-a_2H(n-2)=\cdots-a_kH(n-k)=0 \\ H(0)=b_0,H(1)=b_1,H(2)=b_2,\cdots,H(k-1)=b_{k-1} \end{cases} $$ 称为k阶常系数线性齐次递推方程 **例子** 斐波那契数列 特征方程与特征根 递推方程 $$ \begin{cases} H(n)-a_1H(n-1)-a_2H(n-2)=\cdots-a_kH(n-k)=0 \\ H(0)=b_0,H(1)=b_1,H(2)=b_2,\cdots,H(k-1)=b_{k-1} \end{cases} $$ 特征方程 $$ x^k-a_1x^{k-1}-\cdots-a_k=0 $$ 递推方程的特征根=特征方程的根 **例子** $f_n=f_{n-1}+f_{n-2}$ 特征根$\frac{(1\pm \sqrt{5})}{2}$ 递推方程的解与特征根的关系 ![image-20211130194032231](picture/image-20211130194032231.png) 递推方程的解的性质 定理 $h_1(n)$​和$h_2(n)$​是递推方程的解，$c_1,c_2$​为任意常数，则$c_1h_1(n)+c_2h_2(n)$​是递推方程的解 推论​​​ 若$q_1,q_2,\cdots,q_n$是递推方程的特征根，则$c_1q_1^n+c_2q_2^n+\cdots+c_kq_k^n$是递推方程的解，其中$c_1,c_2,\cdots,c_k$是任意常数 无重根下的通解结构 定义 若对$k$阶递推方程的每个解$h(n)$都存在一组常数$c_1^\prime,c_2^\prime,\cdots,c_k^\prime$使得 $h(n)=c_1^\prime q_1^n+c_2^\prime q_2^n+\dots+c_k^\prime q_k^n$​ 成立，则称$c_1^\prime q_1^n+c_2^\prime q_2^n+\dots+c_k^\prime q_k^n$为通解 定理 设$q_1,q_2,\cdots,q_k$是$k$阶递推方程不等的特征根，则通解为 $H(n)=c_1q_1^n+c_2q_2^n+\cdots+c_kq_k^n$ **例子** ![image-20211130195750182](picture/image-20211130195750182.png) 有重根下求解中的问题 $$ \begin{cases} H(n)-4H(n-1)+4H(n-2)=0 \\ H(0)=0,H(1)=1 \end{cases} $$ 特征方程$x^2-4x+4=0$ 通解$H(n)=c_12^n+c_22^n=c2^n$​，带入初值，无解 有重根下的通结构 设$q_1,q_2,\cdots,q_t$是递推方程的不相等的特征根，且$q_i$的重数为$e^i$，令 $H_i(n)=(c_{i1}+c_{i2}n+c_{i3}n^2+\cdots+c_{ie}n^{e^i-1})q_i^n$​ **例子** ![image-20211130200514712](picture/image-20211130200514712.png) 总结 ![image-20211130195809443](picture/image-20211130195809443.png) #### 2) 常系数线性非齐次递推方程 $$ \begin{cases} H(n)-a_1H(n-1)-a_2H(n-2)=\cdots-a_kH(n-k)=0 \\ n\ge k \\ a_k\ne 0 \\ f(n)\ne 0 \end{cases} $$ 通解 定理非齐次递推方程的通解结构为 $$ H(n)=\overline{H(n)}+H^*(n) $$ 其中$\overline{H(n)}$是对应齐次方程的通解 $H^*(n)$是一个特解 求解关键 用**待定系数法**确定一个特解$H^*(n)$​ 特解的待定系数法求解 将$f(n)$化为如下形式 $f(n)=\beta^nP^{(t)}(n)$ 则特解设$H^*(n)=n^e\beta^nQ^{(t)}(n)$ 其中 * 常数$\beta$是递推方程的$e$重特征根 * $P^{(t)}(n)$是n的$t$次多项式 * $O^{(t)}(n)$是与$P^{(t)}(n)$​同次的满项多项式，其系数记为待定系数​​ ![image-20211130201253850](picture/image-20211130201253850.png) ![image-20211130201303477](picture/image-20211130201303477.png) ![image-20211130201318205](picture/image-20211130201318205.png) ### 1.3.6 Akra-Bazzi方法 # 2. 算法通用设计技术 ## 2.1 分治法 ### 2.1.1 概念 #### 1) 概念 分冶策略 * 将原问题划分或者归结为规模较小的子问题， * 递归或迭代求解每个子问题 * 将子问题的解综合得到原问题的解 分冶算法的特点 * 将原问题规约为规模小的子问题，**子问题与原问题具有相同的性质** * 子问题规模足够小时直接求解 * 算法可以递归也可以迭代实现 * 算法的分析方法，递推方程 #### 2) 约束条件(注意点) * **子问题与原始问题性子完全一样** * **子问题之间可彼此独立地求解** * 递归停止时子问题可直接求解 #### 3) 两类常见的递推方程 $$ f(n)=\sum_{i=1}^ka_if(n-i)+g(n) \\ f(n)=af(\frac{n}{b})+d(n) $$ 汉诺塔是$W(n)=2W(n-1)+1$是第一类问题 二分检索$W(n)=W(\frac{n}{2})+1$ 归并排序$W(n)=2W(\frac{n}{2})+n-1$​是第二类问题​ 求解方法 方程1：迭代法，递归树 方程2：迭代法，换元法，递归树，主定理 **二分检索，汉诺塔的设计思想** * 将原问题归结为规模为n-1的2个子问题 * 继续规约，将原问题归结为规模为n-2的4个问题继续，当子问题规模为1时，规约过程截止 * 从规模1到n-1,陆续组合两个子问题的解，直到规模为n ### 2.1.2 例子 #### 1) 芯片测试 ![image-20211118200921350](picture/image-20211118200921350.png) ![image-20211118200931435](picture/image-20211118200931435.png) **输入** n片芯片，其中好芯片最少比坏芯片多一块 **问题** 设计一种测试算法，通过测试从n片芯片中挑出一片好芯片 **要求** 使用最少的测试次数 #### 2) 幂乘算法 输入：a为给定实数，n为自然数 输出$a^n$ 传统算法:顺序相乘 乘法次数$\Theta(n)$​ 以乘法作为基本运算 子问题规模，不超过$\frac{n}{2}$ 两个规模近似$\frac{n}{2}$的子问题完全一样，只要计算1次 $W(n)=W(\frac{n}{2})+\Theta(1)$ $W(n)=\Theta(\log n)$ **斐波那契数列** $\{F_n\}$为斐波那契数构成的数列，那么 $\begin{bmatrix}F_{n+1}&F_n\\ F_n& F_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\ 1& 0\end{bmatrix}^n$ 使用归纳证明来证明上面的式子 假设对于任意正整数$n$命题成立，即 $\begin{bmatrix}F_{n+1}&F_n\\ F_n& F_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\ 1& 0\end{bmatrix}^n$ 那么$\begin{bmatrix}F_{n+2}&F_{n+1}\\ F_{n+1}& F_{n}\end{bmatrix}=\begin{bmatrix}F_{n+1}&F_n\\ F_n& F_{n-1}\end{bmatrix}\begin{bmatrix}1&1\\ 1& 0\end{bmatrix}$ =$\begin{bmatrix}1&1\\ 1& 0\end{bmatrix}^n\begin{bmatrix}1&1\\ 1& 0\end{bmatrix}=\begin{bmatrix}1&1\\ 1& 0\end{bmatrix}^{n+1}$​ #### 3) 快速排序 * 用首元素x作为划分标准，将输入数组A划分成不超过x的元素构成的数组$A_L$,大于x的元素构成的数组$A_R$,其中$A_L,A_R$从左往右存放在数组A的位置上 * 递归的对子问题$A_L$和$A_R$​进行排序，直到子问题的规模为1时停止 联系题目 ~~~bash https://www.luogu.com.cn/problem/P1177 ~~~ **题目描述** 利用快速排序算法将读入的$N$个数从小到大排序后输出。 快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 `STL`，虽然你可以使用 `sort` 一遍过，但是你并没有掌握快速排序算法的精髓。） **输入格式** 第 1行为一个正整数 N，第 2行包含 N*N* 个空格隔开的正整数$a_i$，为你需要进行排序的数，数据保证了$A_i$ 不超过$10^9$。 **输出格式** 将给定的 N个数从小到大输出，数之间空格隔开，行末换行且无空格。 **输入输出样例** **输入 #1**复制 ``` 5 4 2 4 5 1 ``` **输出 #1**复制 ``` 1 2 4 4 5 ``` ### 2.1.3 分治法应用 #### 1) 选择问题 输入:集合L(含n个不等的实数) 输出：L中第i个小元素 ##### 选最大 ![image-20211119152809805](picture/image-20211119152809805.png) ##### 选最大最小 * 顺序比较，先选最大max * 顺序比较，在剩余数组中选最小min，类似于选最大算法，但比较时保留较小的数 时间复杂性 $W(n)=n-1+n-2=2n-3$​ **分治算法** * 将数组$L$​从中间划分为两个子数组$L_1$和$L_2$ * 递归得在$L_1$中求最大$max_1$和$min_1$ * 递归的在$L-2$中求最大$max_2$和$min_2$ * $max\leftarrow max\{max_1,max_2\}$ * $min\leftarrow min\{min_1,min_2\}$ ![image-20211119152938939](picture/image-20211119152938939.png) ##### 选第二大 **锦标赛算法** * 两两分组，大者进入下一轮，直到剩下一个元素max为止 * 在每次比较中淘汰较小元素，将被淘汰元素记录在淘汰它的元素的链表上 * 检查max的链表，从中找到最大元，即second ![image-20211119153529829](picture/image-20211119153529829.png) **小结** * 调用两次最大：2n-3 * 锦标赛算法n+logn-2 主要的技术：用空间换时间 #### 2) 信号平滑处理 ##### 卷积 ##### 快速傅里叶变换FFT算法 #### 3) 计算几何 ##### 平面点集的凸包 ### 2.1.4 降低分治算法的时间复杂度 #### 1) 代数变换 通过代数变换，减少子问题个数 降低a的数值，减少子问题的个数 #### 2) 预处理 利用预处理减少递推操作 降低d(n)的阶，增加预处理 ## 2.2 贪心法 ### 2.2.1 贪心算法的例子 #### 0-1背包 #### 最优装载问题 集装箱集合$N=\{1,2,\cdots,n\}$,集装箱$i$的重量$w,i=1,2,\cdots,n$ 输出:$I\in N$，准备装入船的集装箱集合​​​​ ### 2.2.2 贪心算法的正确性 ### 2.2.3 贪心算法的应用 #### 1) 最优前缀码和哈夫曼树 用01字符串作为代码表示字符，要求任何字符的代码都不能作为其他字符代码的前缀 非前缀码的例子 a:001,b:00,c:010,d:01 #### 2) Prim算法 #### 3) Kruskal算法 #### 4) dijkstra算法 ## 2.3 动态规划DP ### 2.3.1 概念 #### 1) 基本思想 #### 2) 设计要素 * **优化原则:最优子结构性质** 优化函数的特点: 任何最短路的子路径相对于子问题始，终点最短 优化原则: 一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列 * 重叠的子问题 #### 3) 设计步骤 * 刻画最优解的结构特性 * 递归定义最优解值 * 以自底向上方式计算最优解值 * 根据计算得到的信息构造一个最优解 最优解值是最优解的目标函数的值 ### 2.3.2 最短路径 问题： 输出:起点集合$\{S_1,S_2,\cdots,S_n\}$ 终点集合$T_1,T_2,\cdots,T_m$ 中间节点集，边集E,对于任意边$e$​都有长度​ 输出:一条从起点到终点的最短路 ![image-20211119144246274](picture/image-20211119144246274.png) 多阶段决策过程每步求解的问题是后面阶段求解问题的子问题每步决策将依赖于以前步骤的决策结果 ![image-20211119144323320](picture/image-20211119144323320.png) ![image-20211119144346536](picture/image-20211119144346536.png) ### 2.3.3 矩阵链相乘 问题：设$A_1,A_2,\cdots,A_n$为矩阵序列，$A_i$为$P_{i-1}\times P_i$阶矩阵，$i=1,2,\cdots,n$试确定矩阵的乘法顺序，使得元素相乘的总次数最少 输入：向量$P=$,其中$P_0,P_1,\cdots ,P_n$为n个矩阵的行数与列数 输出：矩阵链乘法加括号的位置 **例子** 实例$P=<10,100,5,50>,A_1:10\times 100,A_2:100\times 5,A_3:5\times 50$ 乘法次序 $(A_1A_2)A_3=10\times100\times 5+10\times 5\times 50=7500$ $A_1(A_2A_3)=10\times100\times 50+100\times 5\times 50=75000$ 第一种次序很好 ![image-20211119151218410](picture/image-20211119151218410.png) #### 1) 递归实现 ![image-20211119155044733](picture/image-20211119155044733.png) #### 2) 算法时间复杂度 $$ T_n\ge \begin{cases}O(1)& n=1\\ \sum_{k=1}^{n-1}(T(k)+T(n-k)+O(1))&n>1\end{cases} \\ T(n)\ge O(n)+\sum_{k=1}^{n-1}T(k)+\sum_{k=1}^{n-1}T(n-k) \\ T(n)\ge O(n)+2\sum_{k=1}^{n-1}T(k) $$ #### 3) 迭代实现 迭代计算的关键 * 每个子问题指计算一次 * 迭代过程 + 从最小的子问题算起 + 考虑计算顺序，以保证后面用到的值前面已经计算好 + 存储结构保存计算结果--备忘录 * 解的追踪 + 设计标记函数标记每步的决策 + 考虑根据标记函数追踪解的算法 #### 4) 备忘录法 ![image-20211119154854480](picture/image-20211119154854480.png) ### 2.3.4 投资问题 问题 $m$元钱，$n$项投资，$f_i(x)$将$x$元投入第$i$​个项目的效益，求使得总效益最大的投资方案。 建模： 问题的解是向量$,x_i$是投给项目$i$的钱数，$i=1,2,\cdots,n$ 目标函数$max\{f_1(x)+f_2(x_2)+\cdots+f_n(x_n)\}$, 约束条件$x_1+x_2+\cdots x_n=m,x_i\in N$ ![image-20211119155511871](picture/image-20211119155511871.png) ### 2.3.5 背包问题 ### 2.3.6 最长公共子序列 ### 2.3.7 动态规划算法的重要应用 #### 1) 图像压缩 #### 2) 最大子段和 #### 3) 最优二叉检索树 #### 4) RNA二级结构预测 #### 5) 序列比对 ## 2.4 回溯法 ### 2.4.1 回溯算法的例子 #### 1) n后问题 在4*4的方格棋盘上放置4个皇后，使得没有两个皇后在同一行，同一列，也不在同一条45度的斜线上，问有多少种可能的布局？ ![image-20211120105454302](picture/image-20211120105454302.png) > 解是4位向量$$ > > 解为$<2,3,1,3>,<3,1,4,2>$​ > > 推广到8皇后 > > 解是8维向量，有92个 > > 例如$<1,5,8,6,3,7,2,4>$​是解​ **怎么求解？？？** 可以使用一下4叉树，来进行求解 ![image-20211120105635061](picture/image-20211120105635061.png) #### 2) 0-1背包问题 问有$n$种物品，每种物品只有1个，第$i$​种物品价值为$v_i$,重量为$w_i,i=1,2,\cdots,n$,问如何选择放入背包的物品，使得总重量不超过$B$,而价值达到最大 **实例** $V=\{12,11,9,8\},W=\{8,6,4,3\},B=13$ 最优解 $<0,1,1,1,>$，价值28，重量13 **这么求解呢？？？？** ![image-20211120110040905](picture/image-20211120110040905.png) #### 3) 货郎问题 有n个城市，已知任两个城市之间的距离，求一条每个城市恰好经过一次的回路，使得总长度最小 ![image-20211120110149954](https://gitee.com/fakerlove/picture_1/raw/master/image-20211120110149954.png) **怎么求解呢？？？？** ![image-20211120110202924](picture/image-20211120110202924.png) #### 4) 小结 | 问题 | 解的性质 | 解描述向量 | 搜索空间 | 搜索方式 | 约束条件 | | ----------- | -------- | ------------------------------------- | -------- | -------------- | ---------------- | | n后问题 | 可行解 | $$ | n叉数 | 深度，宽度优先 | 彼此不攻击 | | 0-1背包问题 | 最优解 | $$ | 子集树 | 深度，宽度优先 | 不超过背包重量 | | 货郎问题 | 最优解 | $$,1,2...,n的排列 | 排列数 | 深度，宽度优先 | 选没有经过的城市 | | 特点 | 搜索解 | 向量，不断扩张部分向量 | 树 | 跳跃式遍历 | 约定条件回溯判定 | #### 5) 蒙特卡罗(Monte Carlo) 计算搜索树中平均遍历的结点数 ![image-20211130205016266](picture/image-20211130205016266.png) ![image-20211130205029185](picture/image-20211130205029185.png) ### 2.4.2 基本思想 ![image-20211120110654239](picture/image-20211120110654239.png) #### 适用条件 多米诺性质 $P(x_1,x_2,\cdots,x_{k+1})\to P(x_1,x_2,\cdots,x_{k}),o剪枝函数 回溯法和分支限界法在搜索过程中，使用剪枝函数减去不必要搜索的子树，减少问题求解所需实际生成的状态结点数 约束函数 用**约束函数**在扩展结点处剪去不满足约束的子树； 限界函数 用**限界函数**剪去得不到最优解的子树。 **这两类函数统称为剪枝函数。** 采用剪枝函数，可避免无效搜索，提高回溯法的搜索效率。 在分支限界法中使用剪枝函数， 可以加速搜索。 该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。如果这个上界不比当前最优值更大， 则说明相应的子树中不含问题的最优解，因而可以剪去。 约束函数减去不可能包含可行解的子树 限界函数剪去不可能包含最优解的子树 #### 2) 基本思想 目标函数:极大化或极小化 约束条件:解满足的条件 可行解:搜索空间满足约束条件的解 最优解:使得目标函数达到极大(或极小)的解 代价函数 * 计算位置：搜索树的结点 * 值：极大化问题是以该点为根的子树所有可能解的值的上界 * 性质，对极大化问题父结点代价不小于子结点代价（极小化问题相反） ![image-20211120113225461](picture/image-20211120113225461.png) 界 * 含义:当前得到可行解的目标函数的最大值 * 初值：：极大化问题初值为0 * 更新：得到更好的可行解 ![image-20211120113426820](picture/image-20211120113426820.png) 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 **另一种说法** 分支限界法首先要确定一个合理的**限界函数**（bound funciton）， 并根据限界函数确定目标函数的界[down ,up]， 按照广度优先策略搜索问题的解空间树，在分直结点上依次扩展该结点的孩子结点，分别估算孩子结点的目标函数可能值， 如果某孩子结点的目标函数可能超出目标函数的界，则将其丢弃； 否则将其加入待处理结点表（简称PT表），依次从表PT中选取使目标函数取得极值的结点成为当前扩展结点，重复上述过程，直到得到最优解。 #### 3) 一般步骤 1. 将问题的解空间转化为图或者树的结构表示，维护一张活叶子表（可以是优先队列）。 2. 初始将根节点计算一个限界后加入活叶子表。 3. 当活叶子表不为空时，**从活叶子表中取出一个限界最优的结点作为扩展结点，并将该节点去除出表**。当活结点表为空时，算法结束。 4. 判断当前的扩展结点是否可以满足所有约束，并且得到一个可行解（该扩展结点是叶子节点）。 * 如果是，判断优于当前最优解后，记录并更新最优解，随后将当前最优解与所有活叶子节点的限界做比较，**对于限界差于最优解的活叶子结点，去除出活叶子表**，并返回（3） * 如果不是，则进入（5）。 5. 计算扩展结点的所有子节点是否满足约束条件，对于不满足约束条件的子节点，将以该节点为根的子树剪枝（丢弃）。 6. 根据限界函数，计算该节点满足约束的所有子节点的限界。**对于限界差于当前最优解的子节点**（ps：废了，没潜力），**将以该子节点为根的子树丢弃**；**对于限界优于当前最优解的子节点**（ps：还有潜力），**将这些潜力节点作为活叶子结点添加到活叶子表**，并返回（3） ​ （ps：对于上述步骤的推导，参考了《算法分析与设计基础》12.2 分支限界法 ） #### 4) 分支限界法和回溯法的区别 * 求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 * 搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 #### 5) 常见的两种分支限界法 * 队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。 * 优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。 #### 6) 难点 > （1）解空间的构造，即状态空间树的构造方法（节点的生成顺序） > > （2）剪枝函数的确定，即约束规则的确定 > > （3）限界函数的确定，边界的评估方法 ### 2.5.1 背包问题 4种物品，价值$v_i$和重量$w_i$分别为 $v_1=1,v_2=3,v_3=5,v_4=9$ $w_1=2,w_2=3,w_3=4,w_4=7$ 背包重量限制为10 $$ max\ x_1+3x_2+5x_3+9x_4 \\ s.t.\ 2x_1+3x_2+4x_3+7x_4\le 10 \\ x_i\in N,i=1,2,3,4 $$ **代价函数的设定** * 对结点$$,估计以该结点为根的子树中可行解的上界 * 按$\frac{v_i}{w_i}$从大到小排序，$i=1,2,\cdots,n$ * 代价函数=已经装入价值+$\Delta$ $\Delta$​：还可以继续装入最大价值的上界​ $\Delta$=背包剩余重量$\times \frac{v_{k+1}}{w_{k+1}}$（可装） $\Delta$​=0,(不可装) 对每个物品的单位重量价值进行排序，排序后 $$ max\ 9x_1+5x_2+4x_3+x_4 \\ s.t.\ 7x_1+4x_2+3x_3+2x_4\le 10 \\ x_i\in N,i=1,2,3,4 $$ 结合$$的代价函数 $\sum_{i=1}^kv_ix_i+(b-\sum_{i=1}^kw_ix_i)\frac{v_{k+1}}{w_{k+1}}$ 若对某个$j>k$有$b-\sum_{i=1}^kw_ix_i\ge w_j$​​，就是剩下未挑选物品的重量比背包剩下的重量还要重。 则代价函数=$\sum_{i=1}^kv_ix_i$​，程序结束​ **分支策略-深度优先** ![image-20211121105842921](picture/image-20211121105842921.png) **小结** * 分支限界适用于组合优化问题 * 对结点$$​，$V$是顶点的集合，$E$是边的集合，求G的最大图, G的子图:$G^\prime=$,其中$V^\prime\subseteq V,E^\prime \subseteq E$​ G的补图:$G^\prime=$​,$E^\prime$是$E$​关于完全图边集的补集。原来有边的部分变成没有边，原来没有边的部分，现在变成有边 G中的团:G的完全子图 G的最大团：顶点数最多的团 完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。 ![image-20211121113104366](picture/image-20211121113104366.png) ![image-20211121113436324](picture/image-20211121113436324.png) #### 2) 应用 编码，故障诊断，计算机视觉，聚类分析，经济学，移动通信，VLSI电路设计 #### 3) 最大团 问题:给定无向图$G=$，其中顶点集$V=\{1,2,3,\cdots,n\}$,边集为$E$,求G中的最大团 **分支限界算法设计** 搜索树为子集树 结点$基变量，非基变量是针对某一确定基矩阵而言的 不用的基矩阵对应的基变量和非基变量也不同 ---- ### 3.1.2 标准型 ![标准型](picture/20190714155135529.png) **特点**：**目标函数**求**极大**；**等式约束**；**变量非负**。 令$c=(c_1,c_2,\cdots,c_n),x=(x_1,x_2,\cdots,x_n)^T,A=(a_{ij})_{m*n},b=(b_1,b_2,\cdots,b_m)^T$ 则线性规划标准形的矩阵表达式为： $$ \min \ c^Tx \\ s.t. \ Ax=b \\ x\ge 0 $$ 其中$b\in R^m,A\in R^{m*n},c\in R^n,x\in R^n$ 1. 线性标准型的一般形式化为标准型的方法：添加松弛变量；有自由变量的时候，使用消元或者变量替换的形式. 2. 标准型是为了便于理论分析和算法设计，任何满足线性规划要求的均可转换成标准型，如极小化绝对值的和、极小化逐段线性凸函数等特殊线性形式. ### 3.1.3 如何化标准形 * **目标函数实现极大化**，即$min\ z=cx,$令$w=-z$,则$max\ w=-cx$ * 约束条件为不等式 * 约束条件为“$\le$​​” 不等式，则在约束条件的左端加上一个非负的松弛变量； $\sum a_{ij}x_j\le b_i$​转换为$\sum a_{ij}x_j+x_{n+i}=b_i,x_{n+i}\ge 0$​​是**松弛变量** * 约束条件为“$\ge$​​” 不等式，则在约束条件的左端减去一个非负的松弛变量。 $\sum a_{ij}x_j\ge b_i$​​​转换为$\sum a_{ij}x_j-x_{n+i}=b_i,x_{n+i}\ge 0$​​​是**剩余变量** * 若存在**无约束的变量**$x_k$ 则令$x_k=x_k^\prime-x_k^{\prime\prime}$​​,其中$x_k^{\prime}\ge 0,x_k^{\prime\prime}\ge 0$​​, **例子** ![image-20211115155342220](picture/image-20211115155342220.png) * 因为$x_3$无符号要求，即$x_3$取正值也可以取负值，标准型中要求变量非负，所以令 $x_3=x_3^\prime-x_3^{\prime\prime}$​,其中$x_3^{\prime}\ge 0,x_3^{\prime\prime}\ge 0$​, * 第一个约束条件$\le$号，在$\le$左端加入$x_4\ge 0$,化为等式 * 第二个约束条件是$\ge$号，在$\ge$号左端减去$x_5\ge0$ * 第三个约束条件是$\ge$号且常数项为负数，因此在$\le $左边加入$x_6\ge0$,同时两边乘以$-1$ * 目标函数是最小值，为了化为最大值，令$Z^\prime=-Z$，得到$\max Z^\prime=-Z$,即当$Z$达到最小值时$Z^\prime$达到最大值，反之亦然 ![image-20211115160042816](picture/image-20211115160042816.png) ## 3.2 单纯形法 ### 3.2.0 引出 ![image-20211115160349298](picture/image-20211115160349298.png) ### 3.2.1 概念 高中数学教材已经介绍过简单线性规划的解法了：图解法。但是在变量大于二维时，图解法就很不直观。 单纯形法利用了线性规划的基本定理，即只要穷举多个基本可行解，就一定能找到最优解。 它是一种搜索机制，即从一个初始可行解出发，不断迭代到相邻的可行解，同时让目标函数下降。 **一种逐步逼近最优解的迭代** ### 3.2.2 步骤 ![image-20211115152043091](picture/image-20211115152043091.png) #### 1) 确定初始可行基 #### 2) 最优性检验 #### 3) 基变换 ### 3.2.3 单纯形表 用列表的方法描述单纯形法的全过程 ![image-20211115153537382](picture/image-20211115153537382.png) ### 3.2.4 描述算法思路 * 从可行域中某一个顶点开始，判断此顶点是否是最优解 * 如不是，则再找另一个使得目标数值更加优秀的顶点，判断此点是否是最优解 * 化为标准形(要求$b\ge 0$),确定初始基$B$,建立初始单纯形表（假设$A$矩阵中存在**单位矩阵**）； * 若$\sigma_j\le 0(j=m+1,\cdots,n)$，则已得到最优解，停止。否则转入下一步； * 若$j=m+1,\cdots,n$中,存在$\sigma_k>0$,而$P_k\le 0$,，则无最优解，停止。否则转入下一步； * 由$\max(\sigma_j>0)=\sigma_k$,确定$x_k$为换入变量，按$\theta$规则 $$ \theta=\min_i\{\frac{b_i}{a_{kj}}|a_{kj}>0\}=\frac{b_i}{a_{kj}} $$ 可确定$x_l$​​为换出变量 * 以$a_{lk}$​为主元进行迭代 即将$p_k=\begin{bmatrix}a_{1k}\\ \vdots\\ a_{lk}\\ \vdots\\ a_{mk}\end{bmatrix}$迭代成$\begin{bmatrix}0\\ \vdots\\ 1\\ \vdots\\ 0\end{bmatrix}\to l$行 并将单纯形表$x_B$列中的$x_l$换成$x_k$，得到新的单纯形表； 重复（ⅱ）~（ⅴ）。 ### 3.2.5 例题 用单纯形法求下列线性规划的最优解 $$ \max\ z=2x_1+3x_2 \\ \begin{cases} x_1+2x_2\le 8 \\ 4x_1\le 16 \\ 4x_2\le 12 \\ x_1,x_2\ge 0 \end{cases} $$ 转换为标准形，加入松弛变量$x_3,x_4,x_5$,则标准形为 $$ \max\ z=2x_1+3x_2+0x_3+0x_4+0x_5 \\ \begin{cases} x_1+2x_2+x_3= 8 \\ 4x_1+x_4= 16 \\ 4x_2+x_5=12 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{cases} $$ ![image-20211115154259128](picture/image-20211115154259128.png) ![image-20211115154312762](picture/image-20211115154312762.png) ![image-20211115154319729](picture/image-20211115154319729.png) ![image-20211115154335390](picture/image-20211115154335390.png) ![image-20211115154345213](picture/image-20211115154345213.png) ![image-20211115154358704](picture/image-20211115154358704.png) ![image-20211115154407004](picture/image-20211115154407004.png) **例二** ![image-20211115154424657](picture/image-20211115154424657-16369622651254.png) ![image-20211115154432420](picture/image-20211115154432420.png) ![image-20211115154437966](picture/image-20211115154437966.png) ### 3.2.6 普通单纯形法(python) ![在这里插入图片描述](picture/sadasdoi23i2oru823r8sufhuew.png) data.txt ~~~python 1 14 6 0 0 0 0 0 1 1 1 1 0 0 0 4 1 0 0 0 1 0 0 2 0 0 1 0 0 1 0 3 0 3 1 0 0 0 1 6 ~~~ 代码如下 ~~~python import numpy as np def pivot(): l = list(d[0][:-2]) jnum = l.index(max(l)) # 转入编号 m = [] for i in range(bn): if d[i][jnum] == 0: m.append(0.) else: m.append(d[i][-1] / d[i][jnum]) inum = m.index(min([x for x in m[1:] if x != 0])) # 转出下标 s[inum - 1] = jnum r = d[inum][jnum] d[inum] /= r for i in [x for x in range(bn) if x != inum]: r = d[i][jnum] d[i] -= r * d[inum] def solve(): flag = True while flag: if max(list(d[0][:-1])) <= 0: # 直至所有系数小于等于0 flag = False else: pivot() def printSol(): for i in range(cn - 1): if i in s: print("x" + str(i) + "=%.2f" % d[s.index(i) + 1][-1]) else: print("x" + str(i) + "=0.00") print("objective is %.2f" % (-d[0][-1])) d = np.loadtxt("data.txt", dtype=np.float64) (bn, cn) = d.shape s = list(range(cn - bn, cn - 1)) # 基变量列表 solve() printSol() ~~~ ## 3.3 人工变量法 ### 3.3.1 大M法 ![image-20211130211936410](picture/image-20211130211936410.png) ![image-20211130211956948](picture/image-20211130211956948.png) **总结** ![image-20211130212313116](picture/image-20211130212313116.png) ### 3.3.2 两阶段单纯形法 * 与大M单纯形法的目的类似 将人工变量从基变量中换出，以求出原问题的初始基本可行解 * 将问题分成两个阶段求解 #### 第一阶段 ![image-20211130213058323](picture/image-20211130213058323.png) ![image-20211130213108269](picture/image-20211130213108269.png) ![image-20211130213122570](picture/image-20211130213122570.png) #### 第二阶段 ![image-20211130213149441](picture/image-20211130213149441.png) ## 3.4 对偶性 ![image-20211130213219310](picture/image-20211130213219310.png) # 4. 网络流 ## 4.1 概念 ### 4.1.1 相关概念 #### 1) 概念 设有向连通图$G=$,记为$n=|V|,m=|E|$ - **源点：**有n个点，有m条有向边，有一个点很特殊，只出不进，叫做**源点，记作s**。 - **汇点：**另一个点也很特殊，只进不出，叫做**汇点,记作t**。 - 其余的顶点叫做中间节点 称网络$G$为容量网络，记作$G=$ - **容量和流量：**每条有向边上有两个量，**容量和流量**，从i到j的容量通常用**c[i,j]**表示,流量则通常是**f[i,j]**. - **最大流：**把源点比作工厂的话，问题就是求从工厂最大可以发出多少货物，是不至于超过道路的容量限制，也就是，**最大流**。 设$f:E\to R^*$，其中$R^*$为非负实数集，满足​​ #### 2) 容量网络的限制 * **流量平衡**：即 出流的量=入流的量 ，这个比较好理解，就是说如果你入流了100单位水，可水管只能流出50单位水，那么那另外50单位水就爆水管了。 而对于每个不是源点和汇点的点来说，可以类比的想象成没有存储功能的货物的中转站，所有“进入”他们的流量和等于所有从他本身“出去”的流量。 * **容量限制**:$\forall \in E,f(i,j)\le c(i,j)$,即流量小于容量​ 通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最大的车流量。很显然的，流量<=容量。 #### 3) 的类型 * 饱和边:$f(u,v)=c(u,v)$ * 非饱和边:$f(u,v)0$​ #### 4) 容量网络上合法可行流的特征 * 流量平衡 * 容量限制 * 斜对称性 ### 4.1.2 最大流最小割定理 #### 1) 割的概念 ![img](picture/v2-610ae8f45cb7b49e501be871dd6a4111_720w.jpg) 割的定义:割其实就是把节点分成两部分$(S,T)$,而且$s$位于$S$中，$t$位于$T$中 $capacity(S,T)$：离开$S$​的边的权重之和，​ ![img](picture/v2-8fc6917fa0088e7d77319798cddd7a36_720w.jpg) ![img](picture/v2-3e5ee1ed8abb45925e290db908f346ed_720w.jpg) #### 2) 最小割问题 定义：找到一个最小$capacity(S,T)$​的cut #### 3) 最大流问题 定义：找到到达$sink$​节点$t$​的最大化净流量 如图所示，假如顶点s源源不断有水流出，边的权重代表该边允许通过的最大水流量，顶点t流入的水流量最大是多少？ ![max-flow](picture/sadjkasdaqoibssdb9238237ygduygy2.png) 我们可以从顶点s到顶点t的3条路径着手分析，从源点s到终点t共有3条路径： s -> a -> t：流量被边”s -> a”限制，最大流量为2 s -> b -> t：流量被边”b -> t”限制，最大流量为3 s -> a -> b-> t：边”s -> a”的流量已经被其他路径占满，没有流量 所以，顶点t能够流入的最大水流量为：2 + 3 = 5。 这就是最大流问题。所以，图1的最大流为：2 + 3 = 5。 可以发现图1的最小割和最大流都为5，经过数学证明可以知道，图的最小割问题可以转换为最大流问题。 所以，算法上在**处理最小割问题时，往往先转换为最大流问题。** #### 4) 流与割的关系 令$f$是网络上的流，$(S,T)$是任何s-t cut​​ * 由$S$到达$T$的流，等于到达节点$sink\ t$的流 * $f\le capacity$​ * 如果$f$等于割的容量，则$f$​是最大流，$(S,T)$就是最小割​​ #### 5) 最大流最小割定理 在任何网络中，最大流$f_{max}$的值=最小割的$capacity$​ ![img](picture/v2-fb757562414b83771c856bce5b359d58_720w.jpg) **注意点** 构成集合$S$或$T$的点不需要直接相连，下图中$S,T$划分也是可以的，$S$集合中的点并每一直接相连 ![img](picture/v2-9dd21cf44f190fa063d2557dad7a38cb_720w.jpg) ### 4.1.3 增广路径 #### 1) 概念 在容量网络 `G(V, E)` 中, 设有一可行流 $f=\{f(u,v)\}$, 根据每条弧上流量的多少、以及流量和容量的关系,可将弧分四种类型: - 饱和弧, 即 ; - 非饱和弧,即 ; - 零流弧, 即 ; - 非零流弧, 即 。 **链:** 在容量网络中,称顶点序列为一条链,要求相邻两个顶点之间有一条弧, 如 `` 或 `` 为容量网络中一条弧。沿着 Vs 到 Vt 的一条链, 各弧可分为两类: - **前向弧:** 方向与链的正方向一致的弧, 其集合记为 `P+`; - **后向弧:** 方向与链的正方向相反的弧, 其集合记为 `P-`; **增广路:** 设 f 是一个容量网络 G 中的一个可行流, P 是从 Vs 到 Vt 的一条链, 若 P 满足下列条件: - 在 P 的所有前向弧 `` 上, , 即 `P+` 中每一条弧都是非饱和弧; - 在 P 的所有后向弧 `` 上, , 即 `P–` 中每一条弧是非零流弧。 则称 P 为关于可行流 f 的一条增广路, 简称为 `增广路(或称为增广链、可改进路)`。沿着增广路改进可行流的操作称为`增广` #### 2) 增广路定理 设容量网络 $G(V, E)$的一个可行流为$f, f$为最大流的充要条件是在容量网络中不存在增广路。 #### 3) 等价命题 设容量网络 G(V, E)的一个可行流为 f 则: - f 是容量网络 G 的最大流; - | f |等于容量网络最小割的容量; - 容量网络中不存在增广路; - 残留网络 G’中不存在从源点到汇点的路径。 ### 4.1.4 残量网络 #### 1) 概念 有个重要的工具：残量网络。残量网络其实就是具有残存容量的图。 定义残量网络$N(f)=$ * $E(f)=E^+(f)\cup E^-(f)$ + 前向弧集$E^+(f)$:这些弧在N中是非饱和的 + 后向弧集$E^-(f)$：在这些弧的反向弧在N中是非零流​ * 算法导论上有个普遍公式来定义残存**容量**： $$ c_f(u,v)=\begin{cases}c(u,v)-f(u,v)& if(u,v)\in E\\ f(v,u)&if(v,u)\in E\\ o&otherwise\end{cases} $$ 翻译一下公式，说明的就是对于两点间的残存容量定义为： 1.如果这两点连线原来就是原图的边，那么它的残存容量等于运载上限-运输流量。 2.如果这两点的反向连线是原图的边，那么它的残存容量等于那条边的运输流量。 3.其他情况是0，当做没连通。 #### 2) 画出残量图 * 如果是饱和边的话，边就会变成反向的 * 如果是非饱和边，就会变成两条边，一条前向边(运载上限-运输流量)，一条反向边大小等于运输流量 * 零流边的话，就只会有前向边(运载上限) ![image-20211121170542837](picture/image-20211121170542837.png) 从残量网络中可以清晰的看到 * $r(s,v_2)=3$，从$s$到$v_2$还可以再增加3单位的流量 * $r(v_1,t)=2$​​​​，从$v_1$​​​​到$t$​​​​​还可以再增加2单位的流量 #### 3) 残量网络和原网络关系 残量网络$N(f)$和原网络$N$​​有啥关系？？​​ 设$N$的最大流量为$v^*$,f是$N$上可行流 则$N(f)$的最大流量为$v^*-v(f)$​ #### 4) 流量计算 可行流的流量 ![img](picture/d1b4a3a3cc87dd941b1b6b41c2a6ee0d.png) 割集及其容量 ![img](picture/9feb3124605543d22c24cc82fd0ab61a.png) 辅助网络 ![img](picture/a91689a98de729fde6b51eee4770114c.png) 辅助网络的割集及其容量 ![img](picture/56a7f1e1469848a576ca8b1a661945db.png) ## 4.2 最大流算法 ### 4.2.1 Ford-Fulkerson算法(最大流的增广路算法) 练习题 ~~~bash http://acm.hdu.edu.cn/showproblem.php?pid=3549 ~~~ #### 1) 概念 Ford-Fulkerson算法（FFA）,它被称为“**方法**”而不是“算法”，因为在残差图中找到增广路径的方法没有完全指定，或者在具有不同运行时间的若干实现中指定。 该算法就是不断在残余网络中寻找**增广路**并**增广**，直到找不到增广路为止(也就是说，此时源点和汇点不连通，存在割)。下面给出增广路和增广的含义。 #### 2) 算法思路 ![网络流基础篇——Edmond-Karp算法](picture/291452163127554.jpg) 首先，假如所有边上的流量都没有超过容量(不大于容量)，那么就把这一组流量，或者说，这个流，称为一个**可行流**。 一个最简单的例子就是，**零流**，即所有的流量都是0的流。 - 我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了汇点，并且，这条路上的每一段都满足流量<容量，注意，是严格的<,而不是<=。 - 那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的**最小值**$\Delta$。我们把这条路上每一段的流量都加上这个$\Delta$，一定可以保证这个流依然是可行流，这是显然的。 - 这样我们就得到了一个更大的流，他的流量是之前的流量+$\Delta$，而这条路就叫做**增广路**。我们不断地从起点开始寻找增广路，每次都对其进行增广，直到源点和汇点不连通，也就是找不到增广路为止。 - 当找不到增广路的时候，当前的流量就是最大流，这个结论非常重要。 **补充：** - (1).寻找增广路的时候我们可以简单的从源点开始做BFS，并不断修改这条路上的$\Delta$量，直到找到源点或者找不到增广路。 - (2).在程序实现的时候，我们通常只是用一个c 数组来记录容量，而不记录流量，当流量+$\Delta$ 的时候，我们可以通过容量-$\Delta$​​ 来实现，以方便程序的实现。 #### 3) 例子 ![image-20211121160531946](picture/image-20211121160531946.png) 变成0流的流量网络 ![image-20211121160546577](picture/image-20211121160546577.png) 进行增广链的寻找 ![image-20211121160938756](picture/image-20211121160938756.png) 找到了新的增广。为啥不做4->t。是因为做bfs的访问，访问完3,4以后，第一个先访问边就是3->t。发现可以增广。所以就更新了这条路径 ![image-20211121161337253](picture/image-20211121161337253.png) 我们再找一条流量 ![image-20211121161532525](picture/image-20211121161532525.png) 再找一条 ![image-20211121161742883](picture/image-20211121161742883.png) 再找一条 ![image-20211121161841183](picture/image-20211121161841183.png) 最后 ![image-20211121161947812](picture/image-20211121161947812.png) 进行分割 ![image-20211121162025305](picture/image-20211121162025305.png) 最大网络流为18 #### 4) 影响FF算法的因素 * 找s-t增广链的平均运行时间 * 最大流流量$v^*$与增广链平均$\delta$值之比 #### 5) EK算法 *Edmonds–Karp算法可以说是一种Ford-Fulkerson算法的具体化，或者说是一种变体* **为什么要增加反向边？** 在做增广路时可能会阻塞后面的增广路，或者说，做增广路本来是有个顺序才能找完最大流的。 但我们是任意找的，为了修正，就每次将流量加在了反向弧上，让后面的流能够进行自我调整。 下面给个例子，说明一下，为啥需要反向边 ![img](picture/41bd4fca9e4d1d36be09e6ca.jpg) 我们第一次找到了1-2-3-4这条增广路，这条路上的delta值显然是1。于是我们修改后得到了下面这个流。（图中的数字是容量） ![img](picture/60535f619638686debf8f8ca.jpg) 这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增广路了，当前的流量是1。 但这个答案明显不是最大流，因为我们可以同时走1-2-4和1-3-4，这样可以得到流量为2的流。 那么我们刚刚的算法问题在哪里呢？问题就在于我们没有给程序一个”后悔”的机会，应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢？回溯搜索吗？那么我们的效率就上升到指数级了。 而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i)，反向边也同样有它的容量。 我们直接来看它是如何解决的： 在第一次找到增广路之后，在把路上每一段的容量减少delta的同时，也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时，inc(c[y,x],delta) 我们来看刚才的例子，在找到1-2-3-4这条增广路之后，把容量修改成如下 ![img](picture/2f767e91a00f9ca4a977a4cb.jpg) 这时再找增广路的时候，就会找到1-3-2-4这条可增广量，即delta值为1的可增广路。将这条路增广之后，得到了最大流2。 ![img](picture/6074478cf17bd63bb31bbacb.jpg) 那么，这么做为什么会是对的呢？我来通俗的解释一下吧。 事实上，当我们第二次的增广路走3-2这条反向边的时候，就相当于把2-3这条正向边已经是用了的流量给”退”了回去，不走2-3这条路，而改走从2点出发的其他的路也就是2-4。（有人问如果这里没有2-4怎么办，这时假如没有2-4这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点）同时本来在3-4上的流量由1-3-4这条路来”接管”。而最终2-3这条路正向流量1，反向流量1，等于没有流量。 #### 6) 代码 1.找到一条从源点到汇点的路径，使得路径上任意一条边的**残量>0**（注意是小于而不是小于等于，这意味着这条边还可以分配流量），这条路径便称为**增广路** 2.找到这条路径上最小的F[u][v]（我们设F[u][v]表示u->v这条边上的**残量**即剩余流量），下面记为flow 3.将这条路径上的每一条有向边u->v的残量**减去**flow，同时对于起反向边v->u的残量**加上**flow（为什么呢？我们下面再讲） 4.重复上述过程，直到找不出增广路，此时我们就找到了最大流 ~~~c++ // C++ program for implementation of Ford Fulkerson algorithm #include #include #include #include using namespace std; // 给定图中的顶点数 #define V 6 /* 如果源's'有一条路径可以将't'放入，则返回true * 也填充parent[]来存储路径。 * 更新了parent。同时更新了残差网络 */ bool bfs(int rGraph[V][V], int s, int t, int parent[]) { // 创建一个已访问的数组，并将所有顶点标记为未访问 bool visited[V]; memset(visited, 0, sizeof(visited)); // 创建一个队列，进入源顶点并标记源顶点。因为使用了bfs算法，所以需要队列 // as visited queue q; // 起点值放入 q.push(s); // 起点已经访问过了 visited[s] = true; //地点的前面的点，我们假设是-1 parent[s] = -1; // Standard BFS Loop while (!q.empty()) { // u是最后被加入的点 int u = q.front(); // 退出访问点 q.pop(); for (int v = 0; v < V; v++) { // 如果没有访问过的话，残差网络为0 if (!visited[v] && rGraph[u][v] > 0) { q.push(v); // 访问的前一个点是u parent[v] = u; visited[v] = true; } } } // 如果我们从源开始到达BFS的sink，然后返回 // true, else false return visited[t]; } // 返回给定图形中从s到t的最大流量 // graph 为地图的流量大小 // s 为起点 // t 为重点 int fordFulkerson(int graph[V][V], int s, int t) { int u, v; // 创建残差图，并填充残差图 // 给定原始图中的容量为剩余容量 // 残差图 int rGraph[V][V]; // 残差图，其中rGraph[i][j]表示 // 从I到j边的剩余容量(如果有的话) // 是一个边。如果rGraph[i][j]为0，则不存在) for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; int parent[V]; // 该数组由BFS填充，用于存储路径 int max_flow = 0; // 最初没有流动 // 当有从源到汇的路径时，增加流量 while (bfs(rGraph, s, t, parent)) { // 求沿边的最小剩余容量 // 路径由BFS填充。或者我们可以说找到最大流量 // 通过找到的路径。 int path_flow = INT_MAX; // for (v = t; v != s; v = parent[v]) { u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); } // 更新边缘和反向边缘的剩余容量 // 沿着路径 for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; } // 将路径流添加到总体流中 max_flow += path_flow; } // 返回最大流 return max_flow; } // 驱动程序测试上述功能 int main() { // 让我们创建一个如图所示的图。容量图 // int graph[V][V] = {{0, 16, 13, 0, 0, 0}, // {0, 0, 10, 12, 0, 0}, // {0, 4, 0, 0, 14, 0}, // {0, 0, 9, 0, 0, 20}, // {0, 0, 0, 7, 0, 4}, // {0, 0, 0, 0, 0, 0} // }; // 阎鹏飞老师给的例子的第一例子 int graph[V][V] = {{0, 8, 12, 0, 0, 0}, {0, 0, 0, 6, 10, 0}, {0, 2, 0, 10, 0, 0}, {0, 0, 0, 0, 0, 8}, {0, 0, 0, 2, 0, 10}, {0, 0, 0, 0, 0, 0} }; // 阎鹏飞老师给的例子的第例子 // int graph[V][V] = {{0, 2, 0, 3, 0, 0}, // {0, 0, 5, 0, 3, 0}, // {0, 0, 0, 0, 0, 2}, // {0, 0, 1, 0, 0, 0}, // {0, 0, 0, 0, 0, 4}, // {0, 0, 0, 0, 0, 0} // }; // 起点是0,终点是5 cout << "max" << fordFulkerson(graph, 0, 5); return 0; } ~~~ 分为三个步骤，首先寻找一条增广路（如果没有增广路，则返回最大流），同时保存路径；其次，对路径上的流量求最小值，记为min；最后根据路径修改网络，对于前向边，减去最小值，对于后向边，加上最小值，或者直接修改容量。 增广路：从源点s到汇点t的一条有向路径，如果从源点开始不可以到汇点，那么没有增广路。 保存：用一个数组保存，一般是采用父亲表示法（父链接），保存当前节点的父亲， 寻找的时候采用的是迭代的方式实现求最小值以及修改原网络。 ### 4.2.2 dinic最大流算法 #### 1) 历史 比如说这个，EK算法首先由俄罗斯科学家Dinic在1970年提出，没错，就是dinic算法的创始人，实际上他提出的也正是dinic算法，在EK的基础上加入了层次优化，这个我们以后再说，1972年Jack Edmonds和Richard Karp发表了没有层次优化的EK算法。但实际上他们是比1790年更早的时候就独立弄出来了。 #### 2) 概念 **Dinic算法有三个关键词：增广路，残量网络，层次**。 之前两点并不是Dinic算法独有的，EK算法同样需要， 然而Dinic更优秀的地方就在于第三点，它求增广路前先将图进行分层，逐层递进寻找增广路，这样每条路都是s-t最短路，根据最短增广路算法中的证明（不必深究），可以确定这样找增广路的效率得到大幅提高！ **层次** Dinic算法引入了一个叫做**分层图**的概念。具体就是对于每一个点，我们根据从源点开始的bfs序列，为每一个点分配一个深度，然后我们进行若干遍dfs寻找增广路，每一次由u推出v必须保证v的深度必须是u的深度+1 顶点的层次：在残留网络中，把从源点到顶点u的最短路径长度，称为顶点u的层次。源点 Vs的层次为0.例如下图就是一个分层的过程。 ![img](picture/364303-20161128224818271-1614094192.png) **注意：** * 对残留网路进行分层后，弧可能有3种可能的情况。 + 从第i层顶点指向第i+1层顶点。 + 从第i层顶点指向第i层顶点。 + 从第i层顶点指向第j层顶点（j < i）。 * 不存在从第i层顶点指向第i+k层顶点的弧(k>=2)。 * 并非所有的网络都能分层。 ![img](picture/364303-20161128224906256-1973458966.png) #### 3) 算法流程 Dinic算法的思想也是分阶段地在层次网络中增广。它与最短增广路算法不同之处是：最短增广路每个阶段执行完一次BFS增广后，要重新启动BFS从源点Vs开始寻找另一条增广路;而在Dinic算法中，只需一次DFS过程就可以实现多次增广，这是Dinic算法的巧妙之处。**Dinic算法具体步骤如下:** （1）初始化容量网络和网络流。 （2）构造残留网络和层次网络，若汇点不再层次网络中，则算法结束。 （3）在层次网络中用一次DFS过程进行增广，DFS执行完毕，该阶段的增广也执行完毕。 （4）转步骤（2）。 在Dinic的算法步骤中，只有第（3）步与最短增广路相同。在下面实例中，将会发现DFS过程将会使算法的效率有非常大的提高。 > 1、根据残量网络计算层次图。 > > 2、在层次图中使用DFS进行增广直到不存在增广路。 > > 3、重复以上步骤直到无法增广。 #### 4) 例子 ![img](picture/364303-20161129093036740-31254587.png) **例二** #### 5) 时间复杂度 Dinic算法最多被分为n个阶段，每个阶段包括建层次网络和寻找增广路两部分，其中建立层次网络的复杂度仍是O（n*m)。 现在来分析DFS过程的总复杂度。在每一阶段，将DFS分成两部分分析。 * 修改增广路的流量并后退的花费。在每一阶段，最多增广m次，每次修改流量的费用为O（n）。而一次增广后在增广路中后退的费用也为O(n)。所以在每一阶段中，修改增广路以及后退的复杂度为O(m\*n)。 * DFS遍历时的前进与后退。在DFS遍历时，如果当前路径的最后一个顶点能够继续扩展，则一定是沿着第i层的顶点指向第i+1层顶点的边向汇点前进了一步。因为增广路经长度最长为n，所以最坏的情况下前进n步就会遇到汇点。在前进的过程中，可能会遇到没有边能够沿着继续前进的情况，这时将路径中的最后一个点在层次图中删除。 注意到每后退一次必定会删除一个顶点，所以后退的次数最多为n次。在每一阶段中，后退的复杂度为O（n）。 假设在最坏的情况下，所有的点最后均被退了回来，一共共后退了n次，这也就意味着，有n次的前进被“无情”地退了回来，这n次前进操作都没有起到“寻找增广路”的作用。除去这n次前进和n次后退，其余的前进都对最后找到增广路做了贡献。增广路最多找到m次。每次最多前进n个点。所以所有前进操作最多为n+m\*n次，复杂度为O（n\*m）。 于是得到，在每一阶段中，DFS遍历时前进与后退的花费为O（m\*n）。 综合以上两点，一次DFS的复杂度为O（n\*m）。因此，Dinic算法的总复杂度即O（m\*n\*n）。 #### 6) 代码 个人代码 ~~~c++ // C++ program for implementation of Ford Fulkerson algorithm #include #include #include #include using namespace std; // 给定图中的顶点数 #define V 6 // 点的层次 int level[V]; // 残差网络 int rGraph[V][V]; // 起点，重点 int s, t; /* * 使用bfs对所有的 */ bool bfs() { // 重新初始化层次，设置每个结点层次为0 memset(level, 0, sizeof(level)); // 创建一个队列，进入源顶点并标记源顶点。因为使用了bfs算法，所以需要队列 queue q; // 起点值放入 q.push(s); //s结点，设置层次为1 level[s] = 1; // Standard BFS Loop while (!q.empty()) { // u是最后被加入的点 int u = q.front(); // 退出访问点 q.pop(); for (int v = 0; v < V; v++) { // 层位为0或者残差网络为0,残量网络 if (!level[v] && rGraph[u][v] != 0) { // 后访问的数组，层次加一 level[v] = level[u] + 1; q.push(v); } } } cout << "level -->"; for (int i: level) { cout << i << " "; } cout << endl; // 如果源节点不等于0 return level[t] != 0; } /** * dfs,就是使用递归实现。 * @param u * @param flow * @return */ int dfs(int u, int flow) { // 深度优先搜索，搜索到了终点结点。直接返回 if (u == t) { return flow; } int out = 0; int v, path_flow; // for作用就是找到下一个结点 for (v = 1; v <= V && flow; v++) { // 现在的结点level[u]+1 ==下一层结点level[v] // 残差网络大于0 if ((level[u] + 1 == level[v]) && rGraph[u][v] != 0) { path_flow = dfs(v, min(flow, rGraph[u][v]));// 向下增广 rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; flow -= path_flow; out += path_flow; } } if (out == 0) { level[u] = 0; } return out; } int dinic(int graph[V][V]) { int u, v; // 创建残差图，并填充残差图 // 从I到j边的剩余容量(如果有的话) // 是一个边。如果rGraph[i][j]为0，则不存在) for (u = 0; u < V; u++) for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; int max_flow = 0, f = 0; while (bfs()) { max_flow += dfs(s, INT_MAX); } // 返回最大流 return max_flow; } // 驱动程序测试上述功能 int main() { // 让我们创建一个如图所示的图。容量图,答案应该是23 // int graph[V][V] = {{0, 16, 13, 0, 0, 0}, // {0, 0, 10, 12, 0, 0}, // {0, 4, 0, 0, 14, 0}, // {0, 0, 9, 0, 0, 20}, // {0, 0, 0, 7, 0, 4}, // {0, 0, 0, 0, 0, 0} // }; // 阎鹏飞老师给的例子的第一例子,答案应该是18 int graph[V][V] = {{0, 8, 12, 0, 0, 0}, {0, 0, 0, 6, 10, 0}, {0, 2, 0, 10, 0, 0}, {0, 0, 0, 0, 0, 8}, {0, 0, 0, 2, 0, 10}, {0, 0, 0, 0, 0, 0} }; // 阎鹏飞老师给的例子的第例子,答案应该是3 // int graph[V][V] = {{0, 2, 0, 3, 0, 0}, // {0, 0, 5, 0, 3, 0}, // {0, 0, 0, 0, 0, 2}, // {0, 0, 1, 0, 0, 0}, // {0, 0, 0, 0, 0, 4}, // {0, 0, 0, 0, 0, 0} // }; // 起点是0,终点是5 s = 0; t = 5; cout << "max" << dinic(graph); return 0; } ~~~ 洛谷的题目 ~~~bash https://www.luogu.com.cn/problem/P3376 ~~~ 代码 ~~~c++ #include using namespace std; struct littlestar{ int to; int nxt; int w; }star[200020]; int head[200020],cnt=1; void add(int u,int v,int w) { star[++cnt].to=v; star[cnt].w=w; star[cnt].nxt=head[u]; head[u]=cnt; } int n,m,s,t; queue q; int dep[20020]; bool bfs() { memset(dep,0,sizeof(dep)); while(q.size()) q.pop(); q.push(s); dep[s]=1; while(q.size()){ int tmp=q.front(); q.pop(); for(int i=head[tmp];i;i=star[i].nxt){ int v=star[i].to; if(!dep[v] && star[i].w){ dep[v]=dep[tmp]+1; q.push(v); if(v==t) return 1; } } } return 0; } int maxn,inf=1<<29; int dinic(int u,int flow) { if(u==t) return flow; int rest=flow; int k; for(int i=head[u];i && rest;i=star[i].nxt){ int v=star[i].to; if(star[i].w && dep[v]==dep[u]+1){ k=dinic(v,min(star[i].w,rest)); if(!k) dep[v]=0; //剪枝 star[i].w-=k; star[i^1].w+=k; rest-=k; } } return flow-rest; } int main () { scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,0); } int flow=0; while(bfs()){ while((flow=dinic(s,inf))) maxn+=flow; } cout< 在四种常用的最短路算法 Dijkstra, SPFA, floyd, Bellman-Ford 中, > > Dijks 和 SPFA 的使用较为普遍, 对大多数人来说, 也较为熟悉. > > 然而, floyd 与 BF 算法在一些特定的情况下也是非常管用的, 因此有必要在这里作出一点总结. ### 4.3.1 概念 最大流网络可以看做货物的运输网络 * 仅表明运输网络运输货物的能力 * 但没有考虑运送货物的费用 最小费用流要讨论的内容 运送同样的数量货物的运输方案可能有很多个，从中找出一个输出费用最小的方案 费用容量网络记作$N=(V,E,c,w,s,t)$ 设$f$是$N$上的一个可行流，$f$的费用定义为 $w(f)=\sum_{\in E}w(i,j)f(i,j)$ 在所有流量为$v_0$的可行流中，费用最小的称为流量$v_0$的最小费用流 最小费用流问题:给定容量-费用网络$N$​和流量$v_0$​，求流量$v_0$​​的最小费用流​​​​。 **负回路** 路径中的权为负数的回路称为负回路 **带负权的最短路径问题** * djkstra最短路径算法不再使用 算法要求所有边的权值均为非负 * 最短路存在性的充要条件：无负回路 必要性：若存在负回路，每绕一圈路径权值和必然减少 充分性：最短路必然是简单路径 ### 4.3.1 Floyd算法 #### 1) 算法思想 阶段: 路径所经过最短最大节点编号k $d^{(k)}(i,j)$:路径上点编号不超过k时的最短路长度 它要么是两条$k-1$最短路长度之和 要么本身也是$k-1$最短路长度 **递推方程** $$ d^{(0)}(i,j)=w(i,j) \\ d^{(k)}(i,j)=min\begin{Bmatrix}d^{(k-1)}(i,j)\\ d^{(k-1)}(i,k)+d^{(k-1)}(k,j)\end{Bmatrix} \\ 1\le i,j\le n,i\ne k,i\ne k,1\le k\le n $$ 如果存在负回路，若负回路C经过i,设C经过的除i外的最大编号的节点是k,则必有$d^{(k)}(i,i)<0$ 标记函数:$h^{(k)}(i,j)$记录最短路上i的下一个点， $$ h^{(0)}(i,j)=\begin{cases}j&\in E\\ j&i=j\\ 0&otherwise\end{cases} \\h^{(k)}(i,j)=\begin{cases}h^{(k-1)}(i,j)&^{(k-1)}(i,j)检测负回路 若d(1)到d(n)中，存在某个d(k)(i, i) < 0，即从i经过k回到i权为负，此即为负回路，算法终止。 **回溯最短路径顶点** 1到4的最短路径上，h(4)(1, 4) = 2，即从1到4要经过一下2； 考察中间点2： h(4)(1, 2) = 2，即从1到2要经过一下2，这条路找完了； h(4)(2, 4) = 3，即从2到4要经过一下3，继续回溯； 考察中间点3： h(4)(2, 3) = 3，即从2到3要经过一下3，这条路找完了； h(4)(3, 4) = 4，即从3到4要经过一下4，这条路找完了； 最终路径为1->2->3->4。 #### 3) 代码 我的代码，例子为上面的 ~~~c++ #include using namespace std; #define V 4 void findPath(int s, int t, int h[V][V]) { if (h[s][t] == 0) { cout << s+1 << "->" << t+1 << " No Path" << endl; return; } if (h[s][t]-1 == t) { cout << "->" << t+1; } else { findPath(s, h[s][t]-1, h); findPath(h[s][t]-1, t, h); } } int main() { // s为起点，t为终点 int s = 0, t = 3; // 初始化d和v的结果 int d[V][V] = {{0, -1, 1, INT_MAX}, {2, 0, 1, INT_MAX}, {2, INT_MAX, 0, -1}, {4, INT_MAX, INT_MAX, 0}}; int h[V][V] = {{1, 2, 3, 0}, {1, 2, 3, 0}, {1, 0, 3, 4}, {1, 0, 0, 4}}; for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { cout<<"d---"<2->3->4 ~~~c++ #include #include #include using namespace std; void findPath(int s, int t, vector > &h){ if (h[s][t]==0){ cout << s << "->" << t << " No Path" << endl; return; } if (h[s][t]==t){ cout << "->" << t; } else{ findPath(s, h[s][t], h); findPath(h[s][t], t, h); } } int main(){ int n, m, s, t; cin >> n >> m >> s >> t; vector > d(n+1, vector(n+1, INT_MAX)); vector > h(n+1, vector(n+1, 0)); for (int i=0; i> u >> v >> w; d[u][v] = w; h[u][v] = v; } for (int k=1; k<=n; k++){ for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++){ if (d[i][k]!=INT_MAX && d[k][j]!=INT_MAX && d[i][k]+d[k][j]\in E^+(f)\\ -w(i,j)&\in E^-(f)\end {cases}$ $f$是容量-费用网络$N$上可行流 $g$是残量网络$N(f)$上的可行流 $f^\prime=f+g$ $w(f^\prime)=w(f)+aw(g)$ ##### 圈流 设容量-费用网络$N=$,C是$N$中一条边不重复的回路 $C$​上的圈流$h^C$​定义为 $\forall \in E(C)\ h^C(i,j)=\delta$ $\forall \in E-E(C)\ h^C(i,j)=0$ 其中$h^C$​​**的环流量**$\delta=\min_{\in E(C)}\{C(i,j)\}>0$​​，即环上最小的容量​​ $h^C$​是可行流，流量为零但通常费用非零​ $w(h^C)=\delta\cdot aw(C)$​ $aw(C)=\sum_{in E(C)}w(i,j)$​​ 圈流$h^C$​费用=环流量$\delta\times$​圈上的权重和$aw(C)$​​ ##### 更新思想 $f$是容量-费用网络$N$上的可行流 $h^C$是辅助网络$N(f)$上的圈流 $f^\prime=f+h^C$​ $f^\prime$是$N$上可行流,且 $v(f^\prime)=v(f)$ $w(f^\prime)=w(f)+\delta\cdot aw(C)$​ #### 2) 算法思想 * 先任意找出一个流量为v0的可行流。如何找呢？ 利用最大流算法，找出最大流f，若$v(f) 1. 调用一次最大流算法，求$v_0$的一个可行流f；若最大流小于$v_0$，则输出“无可行流”结束算法 > 2. 构造$N(f)$ > 3. 用Floyd算法检测$N(f)$中是否存在负回路，若没有则输出$f$结束算法 > 4. 令$d\leftarrow min\{ac(i, j), \in E(C)\} $ //hc的环流量为d > 5. 若$ ∈ E$​​， 令$f(i, j) \leftarrow f(i, j) + d; ∈ E，$​​ 令$f(j, i) \leftarrow f(j, i) - d$​​ > 6. 重复步骤2 #### 算法流程 * 从初始最小费用流(零流)开始 * 通过费用最小的$s-t$增广链扩张流$f$ * 直到$f$的流量值等于$v_0$​​为止 #### 代码 没写完，应该是错误的 ~~~c++ #include #include #include using namespace std; #define V 4 // 点的层次 int level[V]; //aw为辅助费用,h为圈流,c为环流量 int s, t, aw = 0, h = 0, C = 0; struct node { // 容量 int capacity; // 残余容量 int rest; // 权重 int w; // 求 int d; // 记录路径使用的 int h; } edge[V][V]; /* * 使用bfs对所有的 */ bool bfs() { // 重新初始化层次，设置每个结点层次为0 memset(level, 0, sizeof(level)); // 创建一个队列，进入源顶点并标记源顶点。因为使用了bfs算法，所以需要队列 queue q; // 起点值放入 q.push(s); //s结点，设置层次为1 level[s] = 1; // Standard BFS Loop while (!q.empty()) { // u是最后被加入的点 int u = q.front(); // 退出访问点 q.pop(); for (int v = 0; v < V; v++) { // 层位为0或者残差网络为0,残量网络 if (!level[v] && edge[u][v].rest != 0) { // 后访问的数组，层次加一 level[v] = level[u] + 1; q.push(v); } } } cout << "level -->"; for (int i: level) { cout << i << " "; } cout << endl; // 如果源节点不等于0 return level[t] != 0; } /** * dfs,就是使用递归实现。 * @param u * @param flow * @return */ int dfs(int u, int flow) { // 深度优先搜索，搜索到了终点结点。直接返回 if (u == t) { return flow; } int out = 0; int v, path_flow; // for作用就是找到下一个结点 for (v = 1; v <= V && flow; v++) { // 现在的结点level[u]+1 ==下一层结点level[v] // 残差网络大于0 if ((level[u] + 1 == level[v]) && edge[u][v].rest != 0) { path_flow = dfs(v, min(flow, edge[u][v].rest));// 向下增广 edge[u][v].rest -= path_flow; edge[v][u].rest += path_flow; flow -= path_flow; out += path_flow; } } if (out == 0) { level[u] = 0; } return out; } /** * 最大流算法 */ int dinic() { int max_flow = 0; while (bfs()) { max_flow += dfs(s, INT_MAX); } // 返回最大流 return max_flow; } /** * floyd算法 寻找路径 * @param start 开始结点 * @param end 结束结点 * @param h */ void findPath(int start, int end) { if (edge[start][end].h == 0) { return; } if (edge[start][end].h - 1 == end) { // 放入队列 aw += edge[start][end].w; C = min(C, edge[start][end].rest); } else { findPath(start, edge[start][end].h - 1); findPath(edge[start][end].h - 1, end); } } /** * 更新残差网络 * @param start * @param end */ void update(int start, int end) { if (edge[start][end].h == 0) { return; } if (edge[start][end].h - 1 == end) { edge[start][end].rest -= h; edge[end][start].rest += h; } else { findPath(start, edge[start][end].h - 1); findPath(edge[start][end].h - 1, end); } } bool floyd() { // 辅助费用为0 for (int k = 0; k < V; k++) { for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (edge[i][k].d != INT_MAX && edge[k][j].d != INT_MAX && edge[i][k].d + edge[k][j].d < edge[i][j].d) { edge[i][j].d = edge[i][k].d + edge[k][j].d; edge[i][j].h = edge[i][k].h; } } // 存在负回路 if (edge[i][i].h < 0) { cout << "negative loop:" << endl; cout << i; aw = 0; h = 0; C = INT_MAX;; findPath(i, i); h = aw * C; // 打印圈流 cout << "hc-->" << h << endl; update(i, i); return true; } } } // findPath(s, t); // 没有负回路了,直接返回f，即可 cout << "没有负回路" << endl; return false; } void draw() { cout << "残差网络---" << endl; for (auto &i: edge) { for (node &j: i) { cout << j.rest << " "; } cout << endl; } cout << "d--" << endl; for (auto &i: edge) { for (node &j: i) { cout << j.d << " "; } cout << endl; } cout << "h---" << endl; for (auto &i: edge) { for (node &j: i) { cout << j.h << " "; } cout << endl; } cout << endl; } void createNf() { for (auto &i: edge) { for (node &j: i) { j.h = 0; if (j.rest != 0) { j.d = j.w; } else { j.d = INT_MAX; } } } for (int i = 0; i < V; i++) { edge[i][i].h = i + 1; } // 测试打印 draw(); } int main() { // 起点，终点 s = 0, t = 3; int v0 = 8; // 初始化d for (auto &i: edge) { for (node &j: i) { j.rest = 0; j.capacity = 0; j.w = 0; } } int m; cin >> m; int u, v, capacity, cost; for (int i = 0; i < m; i++) { // 输入 x,y,容量，费用 cin >> u >> v >> capacity >> cost; edge[u][v].capacity = capacity; edge[u][v].rest = capacity; edge[u][v].w = cost; edge[v][u].w = -cost; edge[u][v].h = v; } // 第一步，获取最大流。如果最大流小于v0，则表示无解 int f = dinic(); cout << "f---" << f << endl; if (f < v0) { // 表示无解，不需要进行了 return 0; } // v(f)>=v0，只需将v(f)修剪成与v0相等即可。我们这里假设就是相等的。 // 如果存在残差网络,就一直更新，如果不存在 do { createNf(); } while (floyd()); return 0; } ~~~ ### 4.3.3 最短路径 **定理** 设$f$是$N$上流量为$v_0$的最小费用流 $P$是$N(f)$中权$aw$的$s-t$最短路径 $g$是$P$上流量为$\theta$的可行流 则$f^\prime=f+g$是流量为$v_0+\theta$的最小费用流​​​​​​ ## 4.4 运输问题 ## 4.5 二部图分配 # 5. 随机/概率算法 ## 5.1 基本概念 ### 5.1.1 概念 基本事件的概率:[0,1]中的数 所有基本时间概率之和等于1 **事件A及其概率** 事件：基本事件的组合 事件A的概率:其基本事件的概率之和，记作Pr[A] **随机变量与分布，期望** 随机变量:随机实验结果的赋值函数 分布：随机变量取值的概率 期望：随机变量的加权平均值 ### 5.1.2 随机算法 **随机化算法**是在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。 以上是百度百科给出的随机化算法解释。通俗的说，就是在算法执行的某个步骤中将生成随机数，而该随机数将会影响到整个算法的最终结果。因此，我们可以将随机算法大致分为以下两类： * 数值随机算法 用于求数值问题的近似解 近似解的精度随着计算时间的增加而提高 * 拉斯维加斯算法 只要求出解，解的答案一定是正确的 * 蒙特卡罗算法 非数值问题和组合问题往往需要求出准确解，近似解无意义 用于求问题的**准确解** 取得的解的正确性是随机的。 * 舍伍德算法 ## 5.2 拉斯维加斯算法 是另一种随机算法，因此它具备随机算法最为重要的特征之一 —— **基于随机数进行求解**。与蒙特卡洛算法 (Monte Carlo)一样，拉斯维加斯算法也不是一种具体的算法，而是一种思想。 但不同的是，拉斯维加斯算法在生成随机值的环节中，会不断的进行尝试，直到生成的随机值令自己满意。 在这过程中也许会一直无法产生这样的随机值，因此拉斯维加斯算法的时间效率通常比蒙特卡洛算法来的低，并且最终可能无法得到问题的解， 但是一旦算法找到一个解，那么这个解一定是问题的正确解。 ### 5.2.1 随机快速排序和排序 #### 1) 传统的快速排序 在这之前，我们先来复习下传统的快速排序算法，传统快速排序算法通常分为两个步骤： * 分：从无序数组A中选择枢轴$x$,将$A$分成两个子数组$L$和$R$,其中$L=\{L_i|L_ix\}$ * 治：分别对$L$​和$R$递归重复上述步骤，直到数组有序 上述优化虽然在理论上达到了$O(n\log n)$的时间复杂度，但由于中值查找算法时间复杂度前的常系数很大，因此在实际应用中，算法的表现效果仍然差于归并排序。随机快速排序是对快速排序的另一种优化，接下来我们来看下它的算法步骤： #### 2) 随机快速排序 * 从数组$A$中随机选择一个元素$x$作为枢轴，数组$A$分成两个子数组$L$和$R$,其中$L=\{L_i|L_ix\wedge R_i\in A\}$ * 当$|L|\le \frac{3}{4}|A|$​​并且$|R|\le \frac{3}{4}|A|$时，我们继续执行算法，递归处理$L$和$R$,否则回到步骤1，重新选择一个枢轴 算法同样是对枢轴的选择进行了优化，但并没采取中值查找，而是随机选择出一个枢轴，同时该枢轴还要满足特定条件。我们来重点分析该算法的时间复杂度： 在这之前，首先来定义“好枢轴”和“坏枢轴”的概念： * **好枢轴**:能满足条件L和R都$\le \frac{3}{4}n$的枢轴 * **坏枢轴**:不能满足条件L和R都$\le \frac{3}{4}n$的枢轴 对于任意一个子问题，“好枢轴”都分布在中间的那部分 ![img](picture/v2-63729509cd50c0711b77da16c613e0b1_720w.jpg) 也就是说$P$(选到好枢轴)$>\frac{1}{2}$,这样的话我们处理每个子问题时选择枢轴的次数的期望值将小于2，即$E$(选到枢轴次数)<2,可以类比投掷硬币，P(正面)=$\frac{1}{2}$,所以在理想的情况下通常我们投掷两次硬币就会出现一次正面。算法在最坏的情况下每次随机选择到的好枢轴都正好是最小或者最大的那个，这样算法时间复杂度的递归式就可以表示为： $$ T(n)\le T(\frac{n}{4})+T(\frac{3n}{4})+E(iterations\ times)O(n) \\ =T(\frac{n}{4})+T(\frac{3n}{4})+2cn $$ 这个递归式无法通过主方法(master method)进行求解，我们使用画递归树的方法求解： ![img](picture/v2-c1110a4dc76df853f876daa59cde2738_720w.jpg) 对于每个子问题，分割(partition)所需要的时间复杂度为$2O(n)$,其中$n$是问题的规模，随着分割的深入$n$不断缩小，假设分割的时间复杂度前的常系数为$c$,则$2O(n)=2cn$​,由于每次分割后子问题的规模大小不一致，所以递归树不同分支的深度不一样，沿$\frac{3}{4}$​（最右边)支一直下去的那条路径最长。 深度为$log_{\frac{4}{3}}2cn$,同时相同层次的时间综合为2cn 因此算法的期望时间复杂度为： $$ T(n)\le 2cn\times log_{\frac{4}{3}}2cn \\ O(n\log n) $$ 这样我们就使算法的期望时间复杂度达到了$O(n\log n)$​ #### 3) 特点 * 设计思想 将确定型算法的某步确定型选择变成随机选择 * 分析方法 运行时间的期望 * 典型例子 随机快速排序，随机选择算法 * 拉斯维加斯算法特点 设计方法算法简单，不会出错 时间的期望一般与确定型算法的平均时间一样 ### 5.2.2 n后问题 在4*4的方格棋盘上放置4个皇后，使得没有两个皇后在同一行，同一列，也不在同一条45度的斜线上，问有多少种可能的布局？ ![image-20211120105454302](picture/image-20211120105454302.png) > 解是4位向量$$ > > 解为$<2,3,1,3>,<3,1,4,2>$​ > > 推广到8皇后 > > 解是8维向量，有92个 > > 例如$<1,5,8,6,3,7,2,4>$​是解​ **确定型算法** 回溯搜索--深度优先 **随机n后搜索算法的设计思想** 每一步对搜索方向的确定型选择改为随机选择 ![image-20211122212947035](picture/image-20211122212947035.png) 我们找不到解可能 ![image-20211122213138229](picture/image-20211122213138229.png) ## 5.3 蒙特卡洛算法 > 蒙特卡洛算法并不是一种具体的算法，而是一类算法的统称。 > > 其基本思想是基于随机事件出现的概率。 > > 蒙特卡洛算法得到的最终结果并不一定是正确的，我们可以通过计算算法出错的概率值，然后进行多次求解，使得最终得到正确结果的可能性变得很高。 > > 接下来我们来讨论一种蒙特卡洛算法 * 非数值问题和组合问题往往需要求出准确解，近似解无意义 * 用于求问题的准确解 * 缺陷 + 不保证求得的解是正确的，即求得的解有时是错误的 错误类型 + 单侧错误，要么只犯弃真的错误，要么只犯取伪的错误 + 双侧错误，可以同时出现上述两种错误 + 通常无法有效地判断所求得的解究竟是否正确 ### 5.3.0 预备知识 #### 1) 求x的m次幂 输入:x为实数 $m=d_kd_{k-1}\cdots d_1d_0$ 输出$x^m$ ![image-20211123213341601](picture/image-20211123213341601.png) #### 2) a模n的m次幂 ![image-20211123214658798](picture/image-20211123214658798.png) #### 3) 素数定理 函数$\pi(t)$：小于t的不同的素数个数 例如$\pi(20)=8$,素数8个 2,3,5,7,11,13,17,19 两个性质 * 素数定理$\pi(t)\approx \frac{t}{\ln t}$ * 若$k<2^n$时，n不太小，整除k的不同素数个数小于$\pi(n)$​ ### 5.3.1 主元素测试 数组中出现超过一半的元素 **问题** 输入: n个元素的数组T 输出: 如果存在主元素则输出"true",后者“false" **确定型算法** 先选中位数，然后计数这个数出现的次数 ![image-20211130214654445](picture/image-20211130214654445.png) 改进算法 ![image-20211130214719159](picture/image-20211130214719159.png) ### 5.3.2 串相等测试 #### 1) 问题 串相等测试 A有串x,B有串y,是否x==y?? #### 2) 方法一 A将x发送给B B测试x=y #### 3) 改进算法 传送串的指纹并比对指纹 **指纹产生** 设x和y的二进制表示为$I(x),I(y)$选择素数p,指纹函数为$I_p(x)=I(x)mod\ p$ 存在一个问题$x==y\to I_p(x)=I_p(y)$ $I_p(x)=I_p(y)\nRightarrow x==y$​ 出错条件：固定 $p|(I(x)-I(y))$ **改进算法二** 随机选择素数p 测试序列 > > 设n为奇素数，存在q,m使得 > > $n-1=2^qm(q\ge 1)$ > > 构造序列 > > $a^m(mod\ n),a^{2m}(mod\ n),a^{2^2m}(mod\ n),\cdots,a^{2^qm}(mod\ n)$​ > > 其最后一项为$a^{n-1}(mod\ n)$​,而且每一项是前面一项的平方 > > 如果后面一项是1的话，那么前面一项就是就是他的根。判断前面的是不是1或者n-1,如果是话，就破坏了判定规则，它就不是素数。 ![image-20211123223101614](picture/image-20211123223101614.png) ![image-20211123223122239](picture/image-20211123223122239.png) ##### 算法流程 * 传入一个数$n,lp=n-1$ 再传入一个随机数$a$，但是一般是质数，如$2,3,5,7,61$ * 把$lp$中的所有质因子2都提出来，提出来之后的数设定为$d$​,s记录2的次数 * 令$t=a^d\ mod\ n$,如果$t==1$或者$t==n-1$则返回true 因为，再把$s$都乘回去的时候，一定会得到$a^{n-1}=1\mod n$ 其实s为0，也可以直接返回false，因为n一定就是一个偶数了。 * 然后不断把s往回乘，其实是平方，因为d在指数的位置。 记录平方之前的数las，之后，如果t==1而las!=1并且las!=n-1那么就返回false （根据二次探测） * s乘完后，如果n是质数，那么t=1，（根据费马小定理）。否则返回false * 是true的话，返回1多试几次。 * 输出结果。 ##### 例子 ![image-20211123220354568](picture/image-20211123220354568.png) ##### 性能分析 1次测试运行时间$O(\log^3n)$ 可证明1次测试出错的概率至多$\frac{1}{2}$ 重复运行k次，出错概率至多$2^{-k}$​ ##### 代码 ~~~c++ #include using namespace std; typedef long long ll; const int N=100000+5; int a[3]={2,7,61}; ll qm(ll x,ll y,ll mod){ ll ret=1; while(y){ if(y&1) (ret*=x)%=mod; (x*=x)%=mod; y>>=1; } return ret; } bool che(ll a,ll x){ int s=0; ll t; ll lp=x-1; while(!(lp&1)){ s++; lp>>=1; } t=qm(a,lp,x); if(t==1||t==x-1) return true; if(s==0) return false; ll las=t; for(int i=0;i