Dotcpp  >  编程教程  >  数学相关  >  傅里叶-莫茨金消元法的应用

傅里叶-莫茨金消元法的应用

点击打开在线编译器,边学边练

傅里叶 - 莫茨金消元法的英文名:Fourier-Motzkin Elimination,简称 FME 算法,它是一种用于从线性不等式中消除变量的数学方法。

它的命名源自于在 1827 年和 1936 年独立发现该算法的 Joseph Fourier 和 Theodore Motzkin 的姓氏。


1. 展示

从线性不等式中消除一组变量,是指通过将关系式中的若干个元素有限次地变换,消去其中的某些元素,从而解决问题的一种方法。

如果线性不等式中的所有变量都被消除,那么我们会得到一个常不等式。因为当且仅当原不等式有解时,消元后的不等式才为真,消除所有变量可用于检测不等式系统是否有解。

考虑一个含 n 个不等式的系统S,有从x1xr的r个变量,其中xr为要消除的变量。根据xr系数的符号(正、负或空), S中的线性不等式可以分为三类:

(1)形式为傅里叶-莫茨金消元法1的不等式,对于范围从 1 到 nA傅里叶-莫茨金消元法为这种不等式的数量)的 j,用傅里叶-莫茨金消元法表示; 

(2)形式为傅里叶-莫茨金消元法2的不等式,对于范围从 1 到 nBnB为这种不等式的数量)的 j,用傅里叶-莫茨金消元法表示;

(3)不包含xr的不等式,设它们构成的不等式组为

因此原系统等价于

原系统等价

消元包括产生一个等价于消元的系统。显然,这个公式等价于

消元公式

不等式

消元不等式

等价于对于傅里叶-莫茨金消元法傅里叶-莫茨金消元法,所有傅里叶-莫茨金消元法个不等式不等式构成的不等式组。

因此,我们将原系统S转换为另一个消掉不等式 的系统,这个系统有不等式个不等式。特别地,如果不等式,那么新系统不等式的个数为不等式的个数


2. 例题

考虑以下不等式系统:

不等式系统

为了消除 x,我们可以根据 x 改写不等式:

根据 x 改写不等式

这样我们得到两个≤不等式和两个≥等式;如果每个≤不等式的右侧至少是每个≥不等式的右侧,则系统有一个解。我们有2X2这样的组合:

傅里叶-莫茨金消元法例题

现在我们有了一个新的少了一个变量不等式系统。


3. 时间复杂度

在 n 个不等式上消元可以最多得到时间复杂度个不等式,因此连续运行 d 步可以得到最多双指数复杂度的双指数复杂度。这是由于算法产生了许多不必要的约束(其他约束隐含的约束)。必要约束的数量以单一指数增长。

可以使用线性规划 (Linear Programming, LP) 检测不必要的约束。


4. 应用

信息论的可实现性证明保证了存在性能良好的编码方案的条件。这些条件通常使用线性不等式系统描述。系统的变量包括传输速率和附加辅助速率。通常,人们旨在仅根据问题的参数(即传输速率)来描述通信的基本限制,因此述辅助率需要消除上。而我们正是通过傅立叶 - 莫茨金消元法来做到这一点的。


5. 实现

在编程语言中,Racket,一种基于 Lisp 的多范式编程语言在 fme - Fourier-Motzkin Elimination for Integer Systems) 中对 FME 算法做了简单函数代数实现。



知识点标签:数学 数论


本文固定URL:https://www.dotcpp.com/course/1086

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)