Массив Монге

В математике, применяемой в информатике , массивы Монжа , или матрицы Монжа , представляют собой математические объекты, названные в честь их первооткрывателя, французского математика Гаспара Монжа .

Матрица mxn размером для всех называется массивом Монжа , если $\scriptstyle i,\,j,\,k,\,\ell$ такой, что

$1\leq i<k\leq m{\text{ and }}1\leq j<\ell \leq n$

получается

$A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].\,$

Таким образом, для любых двух строк и двух столбцов массива Монжа (подматрицы 2 × 2) четыре элемента в точках пересечения обладают тем свойством, что сумма верхнего левого и нижнего правого элементов (по главной диагонали ) равна меньше или равно сумме нижнего левого и верхнего правого элементов (по антидиагонали ).

Эта матрица представляет собой массив Монжа:

${\begin{bmatrix}10&17&13&28&23\\17&22&16&29&23\\24&28&22&34&24\\11&13&6&17&7\\45&44&32&37&23\\36&33&19&21&6\\75&66&51&53&34\end{bmatrix}}$

Например, возьмем пересечение строк 2 и 4 со столбцами 1 и 5.Четыре элемента:

${\begin{bmatrix}17&23\\11&7\end{bmatrix}}$

17 + 7 = 24

23 + 11 = 34

Сумма верхнего левого и нижнего правого элементов меньше или равна сумме нижнего левого и верхнего правого элементов.

Характеристики

• Приведенное выше определение эквивалентно утверждению

Матрица является массивом Монжа тогда и только тогда, когда $A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]$ для всех $1\leq i<m$ и $1\leq j<n$.

• Любой подмассив, созданный путем выбора определенных строк и столбцов из исходного массива Monge, сам по себе будет массивом Monge.
• Любая линейная комбинация массивов Монжа с неотрицательными коэффициентами сама по себе является массивом Монжа.
• Каждый массив Монжа полностью монотонен, что означает, что его минимумы строк встречаются в неубывающей последовательности столбцов, и что то же самое свойство справедливо для каждого подмассива. Это свойство позволяет быстро находить минимумы строк с помощью алгоритма SMAWK . Если вы отметите кружком крайний левый минимум каждой строки, вы обнаружите, что ваши круги идут вниз вправо; то есть, если $f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]$, затем $f(j)\leq f(j+1)$ для всех $1\leq j<n$. Симметрично, если вы отметите самый верхний минимум каждого столбца, ваши круги будут двигаться вправо и вниз. строки и столбца Максимумы идут в противоположном направлении: вверх вправо и вниз влево.
• понятие слабых массивов Монжа Было предложено ; слабый массив Монжа — это квадратная матрица размером n × n , которая удовлетворяет свойству Монжа $A[i,i]+A[r,s]\leq A[i,s]+A[r,i]$ только для всех $1\leq i<r,s\leq n$.
• Матрица Монжа — это просто другое название субмодулярной функции двух дискретных переменных. Точнее, A является матрицей Монжа тогда и только тогда, когда A [ i , j ] является субмодулярной функцией переменных i , j .

Приложения

Матрицы Монжа имеют приложения в комбинаторной оптимизации задачах :

• Если задача коммивояжера имеет матрицу затрат, которая является матрицей Монжа, ее можно решить за квадратичное время.
• Квадратная матрица Монжа, которая также симметрична относительно своей главной диагонали , называется матрицей Супника (в честь Фреда Супника ). Любая линейная комбинация матриц Супника сама по себе является матрицей Супника. а когда матрица затрат в задаче коммивояжера представляет собой матрицу Супника, оптимальным решением является заранее определенный маршрут, на который не влияют конкретные значения в матрице.

Ссылки

• Дейнеко Владимир Георгиевич; Вегингер, Герхард Дж. (октябрь 2006 г.). «Некоторые проблемы, связанные с коммивояжёрами, дартсом и евромонетами» (PDF) . Бюллетень Европейской ассоциации теоретической информатики . 90 . EATCS : 43–52. ISSN   0252-9742 .