システムとモデリング

modelica, Julia, Design Structure Matrix, SysML, 他モデリング全般について。

トップ > DSM > 可到達行列法のアルゴリズム

可到達行列法のアルゴリズム

DSM

DSMのシーケンシングアルゴリズムの１つである可到達行列法について勉強してみます。

シーケンシングアルゴリズムについては↓の記事で解説して います。 otepipi.hatenablog.com

参考にした資料

Warfield, J. N. (1973). Binary Matrices in System Modeling. IEEE Transactions on Systems, Man and Cybernetics, 3(5), 441–449. https://doi.org/10.1109/TSMC.1973.4309270

Sequencing a DSMdsmweborg.wordpress.com

可到達行列法概略

可到達行列法でDSMのシーケンシングを行う手順は大雑把に以下になります。

  1. 4列のテーブルを作成します。

    • 第1列にはDSMの全ての要素を列挙します。
    • 第2列には、第1列に列記した要素に入力する要素を列挙します。（その要素に対応する可到達行列の行の、非ゼロ要素をもつ列番号を書けば良い）
    • 第3列には、第1列に列記した要素が出力となる要素を列挙します。（その要素に対応する可到達行列の列の、非ゼロ要素をもつ行番号を書けば良い）
    • 第4列には、第2列と第3列の両方に列挙されている要素を列挙します。

  2. 第1列と第4列のデータが等しい要素を、「トップレベル要素」として特定し、その要素をテーブルから削除します。

  3. STEP1へ戻ります

例題

以下の可到達行列を並び替えてみます。

f:id:Otepipi:20190526082719p:plain

TABLE1

まず以下のようなテーブルを作成します。

要素 R(s) A(s) R(s)A(s)
1 1 1, 3, 4, 7, 8, 9, 11, 12, 13 1
2 2 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 2
3 1, 2, 3, 4, 5, 8, 9 3, 7, 8, 11, 12 3, 8
4 1, 2, 4, 5, 9 3, 4, 7, 8, 9, 11, 12, 13 4, 9
5 2, 5 3 ,4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15 5
6 2, 6 6, 10, 14, 15 6
7 1, 2, 3, 4, 5, 7, 8, 9 3, 7, 8, 11, 12 7
8 1, 2, 3, 4, 5, 8, 9 3, 7, 8, 11, 12 3, 8
9 1, 2, 4, 5, 9 3, 4, 7, 8, 9, 11, 12, 13 4, 9
10 2, 5, 6, 10 10, 14, 15 10
11 1, 2, 3, 4, 5, 7, 8, 9, 11 11 11
12 1, 2, 3, 4, 5, 7, 8, 9, 12 12 12
13 1, 2, 4, 5, 9, 13 13 13
14 2, 5, 6, 10, 14 14 14
15 2, 5, 6, 10, 15 15 15

各列の意味は、第1列で順番に列挙した要素に対して以下のようになります。

  • R(s) : 入力元となる要素
  • A(s) : 出力先となる要素
  • R(s)A(s) : R(s)かつA(s)である要素

次に、R(s)とR(S)A(s)の値が等しい要素を探します。Table1ではその要素は1と2です。この２つはトップレベルの要素と特定できます。

TABLE トップレベル要素
TABLE1 1, 2

トップレベル要素である1と2をTABLE1から削除してTABLE2を作成します。。要素1, 2の行を消すだけでなく、各項目の値となっているものも削除します。

TABLE2

要素 R(s) A(s) R(s)A(s)
3 3, 4, 5, 8, 9 3, 7, 8, 11, 12 3, 8
4 4, 5, 9 3, 4, 7, 8, 9, 11, 12, 13 4, 9
5 5 3 ,4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15 5
6 6 6, 10, 14, 15 6
7 3, 4, 5, 7, 8, 9 3, 7, 8, 11, 12 7
8 3, 4, 5, 8, 9 3, 7, 8, 11, 12 3, 8
9 4, 5, 9 3, 4, 7, 8, 9, 11, 12, 13 4, 9
10 5, 6, 10 10, 14, 15 10
11 3, 4, 5, 7, 8, 9, 11 11 11
12 3, 4, 5, 7, 8, 9, 12 12 12
13 4, 5, 9, 13 13 13
14 5, 6, 10, 14 14 14
15 5, 6, 10, 15 15 15

このTABLE2でR(s) = R(S)A(s)となる要素は5と6です。これらをTABLE2のトップレベル要素とします。

TABLE トップレベル要素
TABLE1 1, 2
TABLE2 5, 6

そして、TABLE2から要素5, 6を削除したTABLE3を作成します。

TABLE3

要素 R(s) A(s) R(s)A(s)
3 3, 4, 8, 9 3, 7, 8, 11, 12 3, 8
4 4, 9 3, 4, 7, 8, 9, 11, 12, 13 4, 9
7 3, 4, 7, 8, 9 3, 7, 8, 11, 12 7
8 3, 4, 8, 9 3, 7, 8, 11, 12 3, 8
9 4, 9 3, 4, 7, 8, 9, 11, 12, 13 4, 9
10 10 10, 14, 15 10
11 3, 4, 7, 8, 9, 11 11 11
12 3, 4, 7, 8, 9, 12 12 12
13 4, 9, 13 13 13
14 10, 14 14 14
15 10, 15 15 15

TABLE3のトップレベル要素は要素4, 9, 10 です。

TABLE トップレベル要素
TABLE1 1, 2
TABLE2 5, 6
TABLE3 4, 9,10

トップレベル要素をさらに削除してTABLE4を作成します。

TABLE4

要素 R(s) A(s) R(s)A(s)
3 3, 8 3, 7, 8, 11, 12 3, 8
7 3, 7, 8 3, 7, 8, 11, 12 7
8 3, 8, 3, 7, 8, 11, 12 3, 8
11 3, 7, 8, 11 11 11
12 3, 7, 8, 12 12 12
13 13 13 13
14 14 14 14
15 15 15 15

TABLE4のトップレベル要素は要素3, 8, 13, 14, 15 です。

TABLE トップレベル要素
TABLE1 1, 2
TABLE2 5, 6
TABLE3 4, 9,10
TABLE4 3, 8, 13, 14, 15

トップレベル要素をさらに削除してTABLE5を作成します。

TABLE5

要素 R(s) A(s) R(s)A(s)
7 7 7, 11, 12 7
11 7, 11 11 11
12 7, 12 12 12

TABLE5のトップレベル要素は要素 7です。

TABLE トップレベル要素
TABLE1 1, 2
TABLE2 5, 6
TABLE3 4, 9,10
TABLE4 3, 8, 13, 14, 15
TABLE5 7

トップレベル要素をさらに削除して最後のTABLE6を作成します。

TABLE6

要素 R(s) A(s) R(s)A(s)
11 11 11 11
12 12 12 12

TABLE6のトップレベル要素は要素 11, 12です。

TABLE トップレベル要素
TABLE1 1, 2
TABLE2 5, 6
TABLE3 4, 9,10
TABLE4 3, 8, 13, 14, 15
TABLE5 7
TABLE6 11, 12

これで全ての要素をトップレベル要素に分類できました。

可到達行列の並べ替え

最後に、TABLEで出てきたトップレベル要素の順に可到達行列の要素を並べ替えれば、シーケンシングは完了します。

最後に、シーケンシング完了後の可到達行列を掲載して終わりにします。

f:id:Otepipi:20190526082810p:plain