X



最短経路問題をマトリックスで解く
0001名無しさん@お腹いっぱい。
垢版 |
2023/09/27(水) 16:28:33.25ID:tnyU32uQ0
次のような4×4マトリックスA0があるとします。
a b c d
a 0 5 2 3
b 4 0 5 2
c 3 4 0 2
d 6 1 2 0
A0(c,b)=4はcからbに行くには4時間かかるという意味です。
対角線が0なのは自分自身へは時間は不要という意味です。

ここでAのc行(3,4,0,2)とAのb列(5,0,4,1)を足しますと(8,4,4,3)となります。
最小値は3で、その意味は「cからbへは一か所経由すれば3時間で行ける」となります。
最小値3は4番目にありますからdを通過すればよいことがわかります。
この操作にはc〜c〜bやc〜b〜bも含まれますので、「一か所経由」は正確には「最大でも一か所経由」です。

A0のあらゆる行と列の組み合わせに対してこの演算をやりますと新たなマトリックスA1ができ、対応する経由地のマトリックスQ1も得られます。

次にA1に対してA0に行った操作をしてA2を得ます。
A2は最大3か所立ち寄った場合の最短時間となります。
この例の場合ノード数は4しかありませんのですべてのノード間の最短時間が得られました。
経由地マトリックスQ2も得られます。
i〜jの最短時間はA2(i,j)にあります。
i〜jの最短経路はまずi〜Q2(i,j)〜jが得られます。
i〜Q2(i,j)にQ1を適用し、Q2(i,j)〜jにQ1を適用すれば、具体的な最短経路が得られます。

添付: https://sites.google.com/view/mathlife2-1
0002名無しさん@お腹いっぱい。
垢版 |
2023/11/06(月) 16:39:56.91ID:PYF4TvWq0
被害者の証言によれば、一部の集スト犯罪者は特権をもらってて

悪いことをやってても捕まらないそうです
レスを投稿する


ニューススポーツなんでも実況