最短経路問題をマトリックスで解く (2ﾚｽ)
最短経路問題をマトリックスで解く http://rio2016.5ch.net/test/read.cgi/informatics/1695799713/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
1: 名無しさん＠お腹いっぱい。 [sage] 2023/09/27(水) 16:28:33.25 ID:tnyU32uQ0 次のような4×４マトリックスA０があるとします。 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に行くには４時間かかるという意味です。 対角線が０なのは自分自身へは時間は不要という意味です。 ここでＡのc行（３，４，０，２）とAのb列（５，０，４，１）を足しますと（８，４，４，３）となります。 最小値は３で、その意味は「cからbへは一か所経由すれば3時間で行ける」となります。 最小値３は4番目にありますからdを通過すればよいことがわかります。 この操作にはc〜c〜bやc〜b〜bも含まれますので、「一か所経由」は正確には「最大でも一か所経由」です。 A0のあらゆる行と列の組み合わせに対してこの演算をやりますと新たなマトリックスA1ができ、対応する経由地のマトリックスQ1も得られます。 次にA1に対してA0に行った操作をしてA2を得ます。 A2は最大3か所立ち寄った場合の最短時間となります。 この例の場合ノード数は4しかありませんのですべてのノード間の最短時間が得られました。 経由地マトリックスQ2も得られます。 i〜ｊの最短時間はA2(i,j)にあります。 i〜ｊの最短経路はまずi〜Ｑ２(i,j)〜jが得られます。 i〜Ｑ２(i,j)にＱ１を適用し、Ｑ２(i,j)〜jにＱ１を適用すれば、具体的な最短経路が得られます。 添付： https://sites.google.com/view/mathlife2-1 http://rio2016.5ch.net/test/read.cgi/informatics/1695799713/1
2: 名無しさん＠お腹いっぱい。 [sage] 2023/11/06(月) 16:39:56.91 ID:PYF4TvWq0 被害者の証言によれば、一部の集スト犯罪者は特権をもらってて 悪いことをやってても捕まらないそうです http://rio2016.5ch.net/test/read.cgi/informatics/1695799713/2
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.376s*