최소+매트릭스 곱하기

거리 제품이라고도 하는 Min-plus 매트릭스 곱셈은 행렬에 대한 연산이다.

두 $개$의 n ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n$${\displaystyle \}}매트릭스$ A =${\displaystyle {}_{}}$( ${\displaystyle i_{}}$j ) {\$displaystyle$$A$$=($$a_$${\displaystyle {}_{}}$ij$$}})와${\displaystyle }$B$$=${\displaystyle }$($b_${ij$\}\}\},$ 이들의 ${\displaystyle \mathrm{거리}}$ $제품{\displaystyle }$C =${\displaystyle }$( c ${\displaystyle {\mathrm{ij}}_{}}$)${\displaystyle }$= ${\displaystyle A}$ ${\displaystyle \times }$ B$${\$displaystystyle C=(c_{i}})$$A\star B}$은(는) ${\displaystyle {ci}_{}}$ ${\displaystyle j_{}}$= min ${\displaystyle \underset{}{\overset{}{k}}}$= ${\displaystyle \underset{}{\overset{}{}}{min}_{}}$ ${\displaystyle k_{}}$= ${\displaystyle {}_{}}$ + b ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle c_{ij}=\min _{k=1}^{a_{ik}b_{kj}\}}}}}}$과$($와) 같은 $n{\displaystyle }$ n${\displaystytime$ n} $행렬$로 정의된다$$.이것은 미니 컨벤션에서 열대수의 반링을 위한 표준 행렬 곱셈이다.

이 작업은 최단 경로 문제와 밀접한 관련이 있다.$W{\displaystyle }$ ${\displaystyle W}$이(가) 그래프의 에지 가중치를 포함하는 $n{\displaystyle }$ ${\displaystyle \times }$ n ${\displaystyle$ $n$$\times$ n$}$ 행렬인$$ 경우 $W{\displaystyle {}^{}}$ ${\displaystyle k^{}}$ ${\$ W$^{$$k}}}$는 대부분의 $k{\displaystyle }$ ${\displaystyle k}$ 가장자리에서$$ 길이의 경로를 사용하여 정점 사이의 거리를 제공하며$$ $W{\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$은 그래프의 거리 행렬이다.

참조

• 우리 즈윅.2002. 브리징 세트와 직사각형 행렬 곱셈을 사용하여 최단 경로를 쌍으로 구성한다.J. ACM 49, 3(2002년 5월), 289–317.
• 리암 로디티와 아사프 샤피라.2008. 서브선형 적층 오차가 있는 최단 경로를 모두 선택한다.ICALP '08, Part I, LNCS 5125, 페이지 622–633, 2008.

참고 항목

• 플로이드-워셸 알고리즘
• 열대 기하학

이 콤비네이터 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t