Monge Array

释义 Definition

Monge数组（Monge array）：一种满足“Monge性质”的二维数组/矩阵。对任意满足 \(i \[ A[i][j] + A[k][\ell] \le A[i][\ell] + A[k][j] \] 则称 \(A\) 具有Monge性质（常见于最优化与算法设计）。它的结构性可用于加速求每行/每列最小值、动态规划优化等。

发音 Pronunciation (IPA)

/mɔ̃ʒ əˈreɪ/

例句 Examples

A Monge array lets us find row minima faster than scanning every entry.
Monge数组能让我们比逐个扫描元素更快地找到每一行的最小值。

By exploiting the Monge array property, the dynamic programming transition can be optimized from quadratic time to near-linear time in some cases.
利用Monge数组的性质，在某些情况下可以把动态规划的转移从二次时间优化到接近线性时间。

词源 Etymology

Monge 来自法国数学家 Gaspard Monge（加斯帕·蒙日） 的姓氏（/mɔ̃ʒ/，法语发音接近“蒙日”），用于纪念与这类“可利用结构的不等式性质”相关的研究传统；array 意为“数组/排列”。该术语在算法与优化领域中被广泛使用（尤其与“全单调性、行最小值搜索”等结果相联系）。

相关词 Related Words

• Monge Property
• Totally Monotone Matrix
• SMAWK Algorithm
• Dynamic Programming
• DP Optimization
• Quadrangle Inequality
• Convex Optimization
• Transportation Problem

文学与著作中的出现 Notable Works

• SMAWK: A Parallel Algorithm for Finding Row Minima of Totally Monotone Matrices（Aggarwal, Klawe, Moran, Shor, Wilber，1987）——经典论文，常与Monge数组/全单调矩阵的行最小值问题并列讨论。
• The Shortest Path Problem with Monge Properties and the Transportation Problem（相关运筹与优化文献中常见主题）——Monge结构在运输问题、最短路变体等中被系统使用。
• Competitive Programming（竞赛编程教材与讲义中常见章节）——将Monge数组性质用于DP优化（如分治/单调队列/Monge优化相关技巧）。
• The Algorithm Design Manual（Skiena）——在讲解高级算法技巧与结构化矩阵加速方法时，常提及与Monge/全单调性相关的思想与应用场景。