- 1986年~1992年洋楽絶頂期
96 :名盤さん[sage]:2023/02/09(木) 11:55:18.26 ID:qZLx/vhL - 次のような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を適用すれば、具体的な最短経路が得られます。 次のような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も得られます。
| - 1986年~1992年洋楽絶頂期
97 :名盤さん[sage]:2023/02/09(木) 11:56:50.03 ID:qZLx/vhL - マトリックス法の計算量はエッジ数が少なければ次のようになると思う。
エッジ数=E,ノード数=Nとする。 左側のマトリックスは無限大の要素を省いてとりだして並べておくとする(E個の要素)。 右側はマトリックスのままにしておく。 これによって一回目のマトリックス計算量はEに比例する。 一か所立ち寄る計算をするたびにエッジ数が2倍に増えるとみこまれ、 計算量合計はE+2E+4E+・・・+(2**log2N)E=NE 各ノードについて隣接するノード数が少なく、小さな一定数を超えなければEはNに置き換わり、 マトリックス法の計算量はO(N×N)となる。間違ってます?。 マトリックス法の計算量はエッジ数が少なければ次のようになると思う。 エッジ数=E,ノード数=Nとする。 左側のマトリックスは無限大の要素を省いてとりだして並べておくとする(E個の要素)。 右側はマトリックスのままにしておく。 これによって一回目のマトリックス計算量はEに比例する。 一か所立ち寄る計算をするたびにエッジ数が2倍に増えるとみこまれ、 計算量合計はE+2E+4E+・・・+(2**log2N)E=NE 各ノードについて隣接するノード数が少なく、小さな一定数を超えなければEはNに置き換わり、 マトリックス法の計算量はO(N×N)となる。間違ってます?。 マトリックス法の計算量はエッジ数が少なければ次のようになると思う。 エッジ数=E,ノード数=Nとする。 左側のマトリックスは無限大の要素を省いてとりだして並べておくとする(E個の要素)。 右側はマトリックスのままにしておく。 これによって一回目のマトリックス計算量はEに比例する。 一か所立ち寄る計算をするたびにエッジ数が2倍に増えるとみこまれ、 計算量合計はE+2E+4E+・・・+(2**log2N)E=NE 各ノードについて隣接するノード数が少なく、小さな一定数を超えなければEはNに置き換わり、 マトリックス法の計算量はO(N×N)となる。間違ってます?。
| - 1986年~1992年洋楽絶頂期
98 :名盤さん[sage]:2023/02/09(木) 12:00:48.38 ID:qZLx/vhL - 人が乱数に使うものは乱数ではなく擬似乱数である。
なぜなら次の出目の確率は予測可能である。 つまり完全に予測困難なものではない。 完全な予測困難性をもつものを人は乱数とは認めたくない故に ホワイトノイズのような特定の性質をもったものを乱数としているだけ。 そして有限の矩形を切り取った乱数列を人が求め、それを乱数と 認識したがっている。 完全な予測困難性があるならば有限ではなく無限数列となるわけな。 一般の乱数の答えは出ている。カオスを利用した事実上周期が見えない 超長周期の大きなデータ値を扱えるものである。基本はどれも二重振り子 の原理の延長にすぎない。 真の乱数であるならば、たとえ同じ結果が1億回続いたとしても それを超える無限の流れの1つであるならば別に問題はないわけです。 次に得る乱数が連続してはいけないというルールなど人が決定している だけの理屈にすぎない。それこそ擬似乱数である。 人が乱数に使うものは乱数ではなく擬似乱数である。 なぜなら次の出目の確率は予測可能である。 つまり完全に予測困難なものではない。 完全な予測困難性をもつものを人は乱数とは認めたくない故に ホワイトノイズのような特定の性質をもったものを乱数としているだけ。 そして有限の矩形を切り取った乱数列を人が求め、それを乱数と 認識したがっている。 完全な予測困難性があるならば有限ではなく無限数列となるわけな。 一般の乱数の答えは出ている。カオスを利用した事実上周期が見えない 超長周期の大きなデータ値を扱えるものである。基本はどれも二重振り子 の原理の延長にすぎない。 真の乱数であるならば、たとえ同じ結果が1億回続いたとしても それを超える無限の流れの1つであるならば別に問題はないわけです。 次に得る乱数が連続してはいけないというルールなど人が決定している だけの理屈にすぎない。それこそ擬似乱数である。 人が乱数に使うものは乱数ではなく擬似乱数である。 なぜなら次の出目の確率は予測可能である。
|
|