最短経路問題をマトリックスで解く (17レス)
上下前次1-新
1: 2022/09/10(土)15:52 ID:uv+A97qg0(1/2) AAS
次のような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時間で行ける」となります。
省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 ー─□─□ ) q -´ 二 ヽ | はあ?いいから働けウンコ製造機
|ノ (∵∴ ( o o)∴) ノ_ ー | |
/| < ∵ 3 ∵> \. ̄` | /
::::::\ ヽ ノ\ 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×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ですべてのノード間の最短時間と経路が解る。
どう思います?
上下前次1-新書関写板覧索設栞歴
あと 9 レスあります
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ AAサムネイル
ぬこの手 ぬこTOP 0.003s