最短経路問題をマトリックスで解く

**名無しさん＠お腹いっぱい。** · 2022/09/10(土) 15:52:11.21

次のような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

**名無しさん＠お腹いっぱい。** · 2022/09/10(土) 15:58:41.94

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
d 6 1 2 0

**￣￣|／￣￣￣** · 2022/09/12(月) 02:47:09.39

　　　　＿＿＿＿_
　　／::::::::::::::::::::::::::＼　　　　　　　　　　　　　　　　　＿
　 /::::::::::::::::::::::::::::::::::::::＼　　　　　　　　　　　／￣　　￣＼
　 |:::::::::::::::::|＿|＿|＿|＿|　　　　　　　　　　/、　　　　　　　　ヽ　
　 |;;;;;;;;;;ノ　　　／,, ,,＼ヽ　　　　　　　　　　|・ |―-、　　　　　　 |
　 |::（ 6　　ー─□─□　）　　　　　　　　ｑ -´　二ヽ　　　　　 | 　はあ？いいから働けウンコ製造機
　 |ノ　　（∵∴　（ o o）∴）　　　　　　　　ノ＿　ー　 |　　　　　| 　　
／|　　　<　　∵　　３　∵>　　　　　　　　　＼.￣｀　 |　　　　/
::::::＼　　ヽ　　　　　　　ノ＼　　　　　　　　　　O＝＝＝＝＝ |
:::::::::::::＼＿＿＿＿＿ノ:::::::::::＼　　　　　　　　/　　　　　　　　 |

**名無しさん＠お腹いっぱい。** · 2022/09/12(月) 11:21:16.27

1980年代初頭にマトリックスの方法を考え出した。
重みづけのない経路問題を解かせているのは組み合わせ問題

**名無しさん＠お腹いっぱい。** · 2022/09/12(月) 20:38:15.52

計算量はn×ｎ×logn

**名無しさん＠お腹いっぱい。** · 2022/09/15(木) 08:33:33.05

ノード数をnとすると計算量はマトリックス積をlogn回だからあっという間に解ける

**名無しさん＠お腹いっぱい。** · 2022/09/17(土) 20:20:54.84

チューリング賞受賞のアイバーソンが開発したAPLを用いた。
APLはマトリックス演算を特徴とする言語で、たとえば、マトリックスの積を＋と×を用いて表現していた。
その＋と×は他の演算に置き換え可能で、この場合、最小値を取る演算子と+演算子を用いれば
プログラミングすることなく、その場で、最短時間が計算できたのであった。

**名無しさん＠お腹いっぱい。** · 2022/09/27(火) 20:27:42.12

ダイクストラ法の計算量はN×Nだから、
すべてのノード間の最短経路はさらにN×N倍必要でN×N×N×Nとなる。
マトリックス法はN×N×log2Nですべてのノード間の最短時間と経路が解る。
どう思います？

**名無しさん＠お腹いっぱい。** · 2022/10/20(木) 04:05:21.86

この方法N×N×logNではなくない？
行列積の O(N^2) 時間はまだ見つかってないはず。

**名無しさん＠お腹いっぱい。** · 2022/10/21(金) 12:59:12.29

単純に行列積を計算する計算量はN＊＊３でした。

**名無しさん＠お腹いっぱい。** · 2022/10/21(金) 13:25:02.53

>>9
ありがとうございます。
全ノード間の最短時間計算の計算量は最大N×N×N×logNとなります。

**名無しさん＠お腹いっぱい。** · 2022/10/22(土) 12:23:12.15

マトリックス法の計算量はエッジ数が少なければ次のようになると思う。
エッジ数＝E,ノード数＝Nとする。
左側のマトリックスは無限大の要素を省いてとりだして並べておくとする(Ｅ個の要素)。
右側はマトリックスのままにしておく。
これによって一回目のマトリックス計算量はEに比例する。
一か所立ち寄る計算をするたびにエッジ数が2倍に増えるとみこまれ、
計算量合計はE＋２E＋４E＋・・・＋(２＊＊log2N)E＝NE
各ノードについて隣接するノード数が少なく、小さな一定数を超えなければEはNに置き換わり、
マトリックス法の計算量はO(N×N）となる。間違ってます？。

**名無しさん＠お腹いっぱい。** · 2022/10/23(日) 06:28:10.38

>>12
間違ってました。
エッジ数が少ない場合については考え直します。

**名無しさん＠お腹いっぱい。** · 2022/11/05(土) 12:26:09.09

エッジ数が少なくても最終的には全ノードに亘って計算しますのでやはりN×N×N×logNのオーダーです。

**名無しさん＠お腹いっぱい。** · 2022/11/18(金) 16:28:23.94

【ワク超過死亡】　葬儀屋　＞＞＞　保険・年金会社
://egg.5ch.net/test/read.cgi/hoken/1668065551/l50

**名無しさん＠お腹いっぱい。** · 2022/11/23(水) 19:10:30.71

ｙｓ

**名無しさん＠お腹いっぱい。** · 2023/09/13(水) 11:50:11.89

フェラチオ動画　https://www.youtube.com/watch?v=bz09bNWRoQU&t=137s