ダブル3,トリプル3を例にしてMatrix Methodの概要を説明します。
まず初めにダブル3,トリプル3のうちのいくつかを選択します。ここではダブルとトリプルを1つづつ選びました。そして次のような行列Aを作ります。
|
D |
D |
T |
T |
D |
T |
D |
1 |
0 |
0 |
0 |
1 |
0 |
D |
0 |
1 |
0 |
0 |
1 |
0 |
T |
0 |
0 |
1 |
0 |
0 |
1 |
T |
0 |
0 |
0 |
1 |
0 |
2 |
左の4列と各行が選択されなかったものに対応しており、そこは必ず単位行列となります。右端の2列が選択したダブルとトリプルです。列と行はそれぞれダブルかトリプルに対応付けられていて、それが異なる場所(青いマス)は0、同じ場所(茶のマス)には0or1(ダブルの場合)か0or1or2(トリプルの場合)が入ります。
次に選択されなかったダブル2,トリプル2について、SAやTabu探索などを行うのですが、ルールが少し異なります。下の表は0000がカバーするものを示しています。*が自分自身、+が1ビット違いのものです。これは見方を変えると0000に上の表の1-4列目のいずれか1つを加えたものと考えることができます。そこで、5列目,6列目についても同じように扱うことにするわけです。それが下の表の#で表した所です。0000に0012を2回加えると0021になることに注意して下さい。ダブルの場合は2でトリプルの場合は3でmodということです。(3等保証を考える場合はここで各列のうち2つを加えることを許します。)
D |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
D |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
T |
0 |
0 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
0 |
0 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
0 |
0 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
0 |
0 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
T |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
0 |
1 |
2 |
* | + | + | + | # | + | # | + | + | # |
以下に完全な表を示します。
000000000000000000111111111111111111 000000000111111111000000000111111111 000111222000111222000111222000111222 012012012012012012012012012012012012 0000*+++ #+# + + # 0001+*+#+ +# + + # 0002++* #+# + + + # 0010+# *+++ # + + # 0011 +#+*+#+ + + # 0012# +++* #+ + + # 0020+ #+# *++ + + # 0021#+ +#+*+ + + # 0022 #+# +++* + + # 0100+ *+++ #+# # + 0101 + +*+#+ +# # + 0102 + ++* #+# + # + 0110 + +# *+++ # # + 0111 + +#+*+#+ # + 0112 + # +++* #+ # + 0120 + + #+# *++ # + 0121 + #+ +#+*+ # + 0122 + #+# +++* # + 1000+ # *+++ #+# + 1001 + # +*+#+ +# + 1002 + # ++* #+# + + 1010 + # +# *+++ # + 1011 + # +#+*+#+ + 1012 + # # +++* #+ + 1020 + # + #+# *++ + 1021 + # #+ +#+*+ + 1022 + # #+# +++* + 1100# + + *+++ #+# 1101 # + + +*+#+ +# 1102 # + + ++* #+# + 1110 # + + +# *+++ # 1111 # + + +#+*+#+ 1112 # + + # +++* #+ 1120 # + + + #+# *++ 1121 # + + #+ +#+*+ 1122 # + + #+# +++*
探索は通常の場合と同様に行います。つまり、各行にいずれかのシンポルが含まれるように、いくつかの列を選択します。ここでは0000,0111,1022,1111の4列でその条件を満たすことが出来ます。
そして最後にこの4本のベクトルを元にして、ダブル3,トリプル3をカバーするような候補を導きます。具体的には、最初に作った行列をA,ここで求まった4本のベクトルをsとすると、
s = Aw
となるようなwを求めます。Awは通常の行列とベクトルの掛け算ですが、上と同様にmodを適用する必要があります。wの下2桁として00,01,02,10,11,12の6通りが考えられるので、4*6=24通りの候補が求まります。以下にそのすべてを示します。
0000 : 000000, 002101, 001202, 110010, 112111, 111212
0111 : 011100, 010201, 012002, 101110, 100211, 102012
1022 : 102200, 101001, 100102, 012210, 011011, 010112
1111 : 111100, 110201, 112002, 001110, 000211, 002012
この24本でダブル3,トリプル3をカバーすることが出来ます。
このページに対するご意見ご感想は (ara999 あっと gmail.com ) までお願いします