массив Монжа

Тип математического объекта

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

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

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

получаем ^[1]

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

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

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

${\displaystyle {\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. Четыре элемента:

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

17 + 7 = 24

23 + 11 = 34

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

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

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

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

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

Приложения

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

• Когда задача коммивояжера имеет матрицу затрат, которая является матрицей Монжа, ее можно решить за квадратичное время. ^{[1] [2]}
• Квадратная матрица Монжа, которая также симметрична относительно своей главной диагонали , называется матрицей Супника (в честь Фреда Супника). Любая линейная комбинация матриц Супника сама по себе является матрицей Супника, ^[1] и когда матрица затрат в задаче коммивояжера является матрицей Супника, оптимальным решением является предопределенный маршрут, не зависящий от конкретных значений внутри матрицы. ^[2]

Ссылки

1. Буркард, Райнер Э.; Клинц, Беттина; Рудольф, Рюдигер (1996). «Перспективы свойств Монжа в оптимизации». Дискретная прикладная математика . 70 (2). ELSEVIER: 95–96. doi :10.1016/0166-218x(95)00103-x.
2. Burkard, Rainer E.; Deineko, Vladimir G.; van Dal, René; van der Veen, Jack AA; Woeginger, Gerhard J. (1998). «Хорошо разрешимые особые случаи задачи коммивояжера: обзор». SIAM Review . 40 (3): 496–546. doi :10.1137/S0036144596297514. ISSN  0036-1445.

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