最短経路問題をマトリックスで解く
次のような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時間で行ける」となります。 最小値3は4番目にありますからdを通過すればよいことがわかります。 この操作にはc〜c〜bやc〜b〜bも含まれますので、「一か所経由」は正確には「最大でも一か所経由」です。 A0のあらゆる行と列の組み合わせに対してこの演算をやりますと新たなマトリックスA1ができ、対応する経由地のマトリックスQ1も得られます。 次にA1に対してA0に行った操作をしてA2を得ます。 A2は最大3か所立ち寄った場合の最短時間となります。 この例の場合ノード数は4しかありませんのですべてのノード間の最短時間が得られました。 経由地マトリックスQ2も得られます。 i〜jの最短時間はA2(i,j)にあります。 i〜jの最短経路はまずi〜Q2(i,j)〜jが得られます。 i〜Q2(i,j)にQ1を適用し、Q2(i,j)〜jにQ1を適用すれば、具体的な最短経路が得られます。 添付: https://sites.google.com/view/mathlife2-1 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 _____ /::::::::::::::::::::::::::\ _ /::::::::::::::::::::::::::::::::::::::\ /  ̄  ̄ \ |:::::::::::::::::|_|_|_|_| /、 ヽ |;;;;;;;;;;ノ /,, ,,\ ヽ |・ |―-、 | |::( 6 ー─□─□ ) q -´ 二 ヽ | はあ?いいから働けウンコ製造機 |ノ (∵∴ ( o o)∴) ノ_ ー | | /| < ∵ 3 ∵> \. ̄` | / ::::::\ ヽ ノ\ O===== | :::::::::::::\_____ノ:::::::::::\ / | 1980年代初頭にマトリックスの方法を考え出した。 重みづけのない経路問題を解かせているのは組み合わせ問題 ノード数をnとすると計算量はマトリックス積をlogn回だからあっという間に解ける チューリング賞受賞のアイバーソンが開発したAPLを用いた。 APLはマトリックス演算を特徴とする言語で、たとえば、マトリックスの積を+と×を用いて表現していた。 その+と×は他の演算に置き換え可能で、この場合、最小値を取る演算子と+演算子を用いれば プログラミングすることなく、その場で、最短時間が計算できたのであった。 ダイクストラ法の計算量はN×Nだから、 すべてのノード間の最短経路はさらにN×N倍必要でN×N×N×Nとなる。 マトリックス法はN×N×log2Nですべてのノード間の最短時間と経路が解る。 どう思います? この方法N×N×logNではなくない? 行列積の O(N^2) 時間はまだ見つかってないはず。 >>9 ありがとうございます。 全ノード間の最短時間計算の計算量は最大N×N×N×logNとなります。 マトリックス法の計算量はエッジ数が少なければ次のようになると思う。 エッジ数=E,ノード数=Nとする。 左側のマトリックスは無限大の要素を省いてとりだして並べておくとする(E個の要素)。 右側はマトリックスのままにしておく。 これによって一回目のマトリックス計算量はEに比例する。 一か所立ち寄る計算をするたびにエッジ数が2倍に増えるとみこまれ、 計算量合計はE+2E+4E+・・・+(2**log2N)E=NE 各ノードについて隣接するノード数が少なく、小さな一定数を超えなければEはNに置き換わり、 マトリックス法の計算量はO(N×N)となる。間違ってます?。 >>12 間違ってました。 エッジ数が少ない場合については考え直します。 エッジ数が少なくても最終的には全ノードに亘って計算しますのでやはりN×N×N×logNのオーダーです。 【ワク超過死亡】 葬儀屋 >>> 保険・年金会社 ://egg.5ch.net/test/read.cgi/hoken/1668065551/l50 read.cgi ver 07.5.1 2024/04/28 Walang Kapalit ★ | Donguri System Team 5ちゃんねる