最短経路問題をマトリックスで解く (17レス)
上
下
前
次
1-
新
12
(1)
: 2022/10/22(土)12:23
ID:ZeJTKsrd0(1)
AA×
[240|
320
|
480
|
600
|
100%
|
JPG
|
べ
|
レス栞
|
レス消
]
12: [] 2022/10/22(土) 12:23:12.15 ID:ZeJTKsrd0 マトリックス法の計算量はエッジ数が少なければ次のようになると思う。 エッジ数=E,ノード数=Nとする。 左側のマトリックスは無限大の要素を省いてとりだして並べておくとする(E個の要素)。 右側はマトリックスのままにしておく。 これによって一回目のマトリックス計算量はEに比例する。 一か所立ち寄る計算をするたびにエッジ数が2倍に増えるとみこまれ、 計算量合計はE+2E+4E+・・・+(2**log2N)E=NE 各ノードについて隣接するノード数が少なく、小さな一定数を超えなければEはNに置き換わり、 マトリックス法の計算量はO(N×N)となる。間違ってます?。 http://rio2016.5ch.net/test/read.cgi/informatics/1662792731/12
マトリックス法の計算量はエッジ数が少なければ次のようになると思う エッジ数ノード数とする 左側のマトリックスは無限大の要素を省いてとりだして並べておくとする個の要素 右側はマトリックスのままにしておく これによって一回目のマトリックス計算量はに比例する 一か所立ち寄る計算をするたびにエッジ数が倍に増えるとみこまれ 計算量合計は242 各ノードについて隣接するノード数が少なく小さな一定数を超えなければはに置き換わり マトリックス法の計算量はとなる間違ってます?
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 5 レスあります
スレ情報
赤レス抽出
画像レス抽出
歴の未読スレ
AAサムネイル
ぬこの手
ぬこTOP
0.038s