最短経路問題をマトリックスで解く (17ﾚｽ)
上下前次1-新
1: 2022/09/10(土)15:52 ID:uv+A97qg0(1/2) AAS
次のような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時間で行ける」となります。
省11
2: 2022/09/10(土)15:58 ID:uv+A97qg0(2/2) AAS
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は以下のとおりです。
□ a b c d
a 0 5 2 3
b 4 0 5 2
c 3 4 0 2
省1
3: ￣￣|／￣￣￣ 2022/09/12(月)02:47 ID:sdDAxQpX0(1) AAS
＿＿＿＿_
／::::::::::::::::::::::::::＼ ＿
/::::::::::::::::::::::::::::::::::::::＼ ／ ￣ ￣ ＼
|:::::::::::::::::|＿|＿|＿|＿| /、 ヽ
|;;;;;;;;;;ノ ／,, ,,＼ ヽ |・ |―-、 |
|::（ 6 ー─□─□ ） ｑ -´ 二 ヽ | はあ？いいから働けウンコ製造機
|ノ （∵∴ （ o o）∴） ノ＿ ー | |
／| < ∵ ３ ∵> ＼.￣｀ | /
::::::＼ ヽ ノ＼ O＝＝＝＝＝ |
:::::::::::::＼＿＿＿＿＿ノ:::::::::::＼ / |
4: 2022/09/12(月)11:21 ID:Vj4pAHg50(1/2) AAS
1980年代初頭にマトリックスの方法を考え出した。
重みづけのない経路問題を解かせているのは組み合わせ問題
5: 2022/09/12(月)20:38 ID:Vj4pAHg50(2/2) AAS
計算量はn×ｎ×logn
6: 2022/09/15(木)08:33 ID:GbLph7Bn0(1) AAS
ノード数をnとすると計算量はマトリックス積をlogn回だからあっという間に解ける
7: 2022/09/17(土)20:20 ID:xQJqkwox0(1) AAS
チューリング賞受賞のアイバーソンが開発したAPLを用いた。
APLはマトリックス演算を特徴とする言語で、たとえば、マトリックスの積を＋と×を用いて表現していた。
その＋と×は他の演算に置き換え可能で、この場合、最小値を取る演算子と+演算子を用いれば
プログラミングすることなく、その場で、最短時間が計算できたのであった。
8: 2022/09/27(火)20:27 ID:J9HKuKIE0(1) AAS
ダイクストラ法の計算量はN×Nだから、
すべてのノード間の最短経路はさらにN×N倍必要でN×N×N×Nとなる。
マトリックス法はN×N×log2Nですべてのノード間の最短時間と経路が解る。
どう思います？
9(1): 2022/10/20(木)04:05 ID:6hVD30tJ0(1) AAS
この方法N×N×logNではなくない？
行列積の O(N^2) 時間はまだ見つかってないはず。
10: 2022/10/21(金)12:59 ID:vbFCaOY30(1/2) AAS
単純に行列積を計算する計算量はN＊＊３でした。
11: 2022/10/21(金)13:25 ID:vbFCaOY30(2/2) AAS
>>9
ありがとうございます。
全ノード間の最短時間計算の計算量は最大N×N×N×logNとなります。
12(1): 2022/10/22(土)12:23 ID:ZeJTKsrd0(1) AAS
マトリックス法の計算量はエッジ数が少なければ次のようになると思う。
エッジ数＝E,ノード数＝Nとする。
左側のマトリックスは無限大の要素を省いてとりだして並べておくとする(Ｅ個の要素)。
右側はマトリックスのままにしておく。
これによって一回目のマトリックス計算量はEに比例する。
一か所立ち寄る計算をするたびにエッジ数が2倍に増えるとみこまれ、
計算量合計はE＋２E＋４E＋・・・＋(２＊＊log2N)E＝NE
各ノードについて隣接するノード数が少なく、小さな一定数を超えなければEはNに置き換わり、
マトリックス法の計算量はO(N×N）となる。間違ってます？。
13: 2022/10/23(日)06:28 ID:+MQF3vBL0(1) AAS
>>12
間違ってました。
エッジ数が少ない場合については考え直します。
14: 2022/11/05(土)12:26 ID:otd7Xc510(1) AAS
エッジ数が少なくても最終的には全ノードに亘って計算しますのでやはりN×N×N×logNのオーダーです。
15: 2022/11/18(金)16:28 ID:s3Gkpmy+0(1) AAS
【ワク超過死亡】 葬儀屋 ＞＞＞ 保険・年金会社
2chｽﾚ:hoken
sssp://o.5ch.net/1zseh.png
16: 2022/11/23(水)19:10 ID:9Wm2Yln60(1) AAS
ｙｓ
17: 2023/09/13(水)11:50 ID:lPfAvHBR0(1) AAS
フェラチオ動画 https://www.youtube.com/watch?v=bz09bNWRoQU&t=137s
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.319s*