最短経路問題をマトリックスで解く (17ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
12(1): 名無しさん＠お腹いっぱい。 [] 2022/10/22(土) 12:23:12.15 ID:ZeJTKsrd0(1) AAS
マトリックス法の計算量はエッジ数が少なければ次のようになると思う。
エッジ数＝E,ノード数＝Nとする。
左側のマトリックスは無限大の要素を省いてとりだして並べておくとする(Ｅ個の要素)。
右側はマトリックスのままにしておく。
これによって一回目のマトリックス計算量はEに比例する。
一か所立ち寄る計算をするたびにエッジ数が2倍に増えるとみこまれ、
計算量合計はE＋２E＋４E＋・・・＋(２＊＊log2N)E＝NE
各ノードについて隣接するノード数が少なく、小さな一定数を超えなければEはNに置き換わり、
マトリックス法の計算量はO(N×N）となる。間違ってます？。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.015s