質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
並列処理

複数の計算が同時に実行される手法

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

最適化

最適化とはメソッドやデザインの最適な処理方法を選択することです。パフォーマンスの向上を目指す為に行われます。プログラミングにおける最適化は、アルゴリズムのスピードアップや、要求されるリソースを減らすことなどを指します。

Q&A

解決済

1回答

381閲覧

組み合わせ: 状態遷移の経路数を求めたい

退会済みユーザー

退会済みユーザー

総合スコア0

並列処理

複数の計算が同時に実行される手法

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

最適化

最適化とはメソッドやデザインの最適な処理方法を選択することです。パフォーマンスの向上を目指す為に行われます。プログラミングにおける最適化は、アルゴリズムのスピードアップや、要求されるリソースを減らすことなどを指します。

0グッド

0クリップ

投稿2021/03/21 08:33

0 から d-1 までの d 個の状態のいずれかを持つことのできる N 個の数値 n_i からなる状態ベクトルを仮定します。任意の要素 n_i を加算してゆき最終的にすべての数値が n_i=d-1 となるような有向グラフを考えています。

例として、以下の図は d=2, N=3 としたときに (0,0,0) から (1,1,1) に至る状態遷移を有向グラフで表しています。

イメージ説明

状態ベクトルの表現は d 進数 N 桁の整数表記と同じですので、状態の個数は d^N 個存在することがわかります (上の例では 2^3=8 個の箱があります)。では状態の遷移数 (なんと言えば良いのか?; 上記の例では矢印の数の 12 を求めたい) が何個になるかはどうすれば求められるでしょうか? あるいは組み合わせ理論でそれに相当する公式などはあるでしょうか?

(元々は並行システムでの処理の進行パターンを考えていて、d 個のステップを持つ N 個のプロセスを実行したとき、個別の状態の遷移数をいくつ検証すればよいかを組み合わせ理論ぽく抽象化してみた質問です。形式手法の文脈になります。)

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

n_iが+1されるような遷移を考えると、ほかの要素の状態によらずn_iが0以上d-1未満であるような状態からそれぞれ一つずつ存在します。

n_iの状態がd-1通り
ほかの要素の状態がd^(N-1)通り
iとしてありうるものがN通り

なので、全体で(d-1) * d^(N-1) * Nです。

投稿2021/03/21 15:14

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2021/03/25 00:11

ありがとうございます! 説明を読んで見直したらすっきり腑に落ちました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問