몽에 배열

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Monge 어레이" – 뉴스 · 신문 · 책 · 학자 · JSTOR(2012년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

컴퓨터 과학에 적용된 수학에서 몽에 배열(Monge arrays) 또는 몽에 행렬(Monge matrices)은 발견자인 프랑스의 수학자 가스파드 몽에(Guffard Monge)의 이름을 딴 수학적 물체다.

m-by-n 행렬은 모든 $i{\displaystyle }$,${\displaystyle j,}$ ${\displaystyle k,}$ ${\displaystyle \ell }$ ${\$에 대해 다음과 같은 경우 M-by-n 행렬이 Monge 배열이라고 한다.

${\displaystyle 1\leq i<k\leq m{\text{ 및 }1}\leq j<\ell \leqn}$

획득하다^[1]

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

따라서 몽게 배열의 2열과 2열(2×2 서브 매트릭스)에 대해 교차점에 있는 4개 원소는 (주 대각선을 가로지르는) 왼쪽 상단과 오른쪽 하단의 원소의 합이 (반대각선을 가로지르는) 하위와 오른쪽 원소의 합보다 작거나 같은 속성을 갖는다.

이 행렬은 Monge 배열이다.

${\displaystyle {\bmatrix}10&17&13&28&23\\17&22&29&23\\24&28&22&34&24\\11&22&34&24\\11&6&13&7\45&34&37&32&32&32&33&19&6\75&66&51&53&34\{bmatrix}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}"$

예를 들어, 1열과 5열이 있는 2열과 4열의 교차점을 취하십시오.네 가지 요소는 다음과 같다.

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

17 + 7 = 24

23 + 11 = 34

왼쪽 위와 오른쪽 아래 원소의 합은 왼쪽 아래 원소와 오른쪽 위 원소의 합보다 작거나 같다.

특성.

• 위의 정의는 문장과 동일하다.

행렬은 $A{\displaystyle }$[ ${\displaystyle i}$, ${\displaystyle j}$ ${\displaystyle ]}$+ A${\displaystyle }$[ ${\displaystyle \mathrm{i}}$+ ${\displaystyle 1}$,${\displaystyle j}$ + ${\displaystyle 1]}$ ${\displaystyle a}$ A${\displaystyle }$[ i${\displaystyle ,j}$ + ${\displaystyle 1]}$ + ${\displaystyle A}$[ ${\displaystyle i}$ + ${\displaystyle 1}$ ] + A [${\displaystyle i}$ +${\displaystyle 1}$]$${\$displaystyle$A[$i,j]+$인 경우에만 몽그 배열이다.$A[i+1,j+1]\leq A[i,j+1]+$ 1 < m$>[\displaystyle 1\leq i<m}$ 및 < $>[\displaystyle 1\leq j<n$에 대한$$ $A[i+1,j]}.$

• 원래 몽게 배열에서 특정 행과 열을 선택하여 생성되는 하위 배열은 그 자체로 몽게 배열일 것이다.
• Monge 배열의 음수가 아닌 계수를 갖는 선형 조합은 그 자체로 Monge 배열이다.
• One interesting property of Monge arrays is that if you mark with a circle the leftmost minimum of each row, you will discover that your circles march downward to the right; that is to say, if ${\displaystyle f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]}$, then ${\displaystyle f(j)\le f(j+1)}$모든 <$$$>$에 대해 {\$displaystyle$ f($j)\$$leq f(j+1)}.$대칭적으로 각 열의 맨 위 최소값을 표시하면 원은 오른쪽 아래로, 아래로 이동한다$.$행과 기둥 맥시마는 반대 방향으로 행진한다: 오른쪽 위, 왼쪽 아래로.
• 약한 몽e 배열의 개념이 제안되었다; 약한 몽e 배열은 사각형 ${\displaystyle \mathrm{n-by-n}}$ 행렬로서 ${\displaystyle \mathrm{몽e}}$ $속성{\displaystyle }$ A${\displaystyle }$[${\displaystyle }$, ${\displaystyle i}$]${\displaystyle }$+ ${\displaystyle A}$[${\displaystyle }$, ${\displaystyle s]}$ + ${\displaystyle A}$ [${\displaystyle }$]${\displaystyle }$+ ${\displaystyle R}$], ${\displaystyle I}$ ${\displaystyle ]}$ ${\displaystyle A[i,i]+$를 만족한다.$A[r,s]\leq A[i,s]+$$A[r,i]}$은(는) 1i < , n{\$displaystyle 1\leq$ i$<r,s\leq$ n$}$에 대해서만
• 모든 몽에 배열은 완전히 단조로운 것으로, 줄의 미니마가 줄지 않는 열 순서에서 발생하며, 하위 배열마다 동일한 속성이 있다는 것을 의미한다.이 속성은 SMAKE 알고리즘을 사용하여 행 미니마를 신속하게 찾을 수 있다.
• Monge 행렬은 두 개의 이산형 변수의 하위 함수의 다른 이름일 뿐이다.정확히 말하자면, A[i,j]가 변수 i,j의 하위 함수인 경우에만 A는 몽그 행렬이다.

적용들

• 주요 대각선에 대해서도 대칭인 사각 몽이 행렬은 Supnick 행렬(Fred Supnick의 뒤를 이어)이라고 불린다. 이러한 종류의 행렬은 여행 중인 세일즈맨 문제에 응용된다(명칭, 거리 행렬을 Supnick 행렬로 쓸 수 있을 때 문제가 쉬운 해결책을 인정한다).Supnick 행렬의 선형 조합은 그 자체로 Supnick 행렬이다.

참조

• Deineko, Vladimir G.; Woeginger, Gerhard J. (October 2006). "Some problems around travelling salesmen, dart boards, and euro-coins" (PDF). Bulletin of the European Association for Theoretical Computer Science. EATCS. 90: 43–52. ISSN 0252-9742.