バシク行列システムから派生した亜種ルールを分類したものです。目的は、各ルールの違いを比べることです。
The English version is Here.
ルールセット
| ルールセット名 作者 初出 |
定義 | bad root 探索 |
bad part上昇 | bad part上昇改変 | 議論 |
| BM1 バシク 2015.8.21 |
左隣法 | 全枝有効方式 | 改変なし | ||
| rTSS rpakr 2018.5.25 |
左隣法 | 全枝有効方式 | 改変なし |
|
|
| BM1.1[1] バシク 2016.5.18 |
上行枝無視方式 | 全枝有効方式 | 改変なし | ||
|
BM2.1 koteitan 2018.3.4 |
上行枝無視方式 | 全枝有効方式 | 改変なし | ||
| Bubby3's fix Bubby3 2018.3.25 |
上行枝無視方式 | 全枝有効方式 | 改変なし |
|
|
| BM2 バシク 2016.6.25 |
上行枝無視方式 | BM2方式 | 改変なし | ||
| BM4 バシク 1st Sep.,'18 |
上行枝無視方式 | 上行枝無視方式 | 改変なし |
|
|
| BM2.3 koteitan 2018.6.18 |
上行枝無視方式 | 上行枝無視方式 | 改変なし |
|
|
| BM3.1 Nish 2018.7.18 |
|
上行枝無視方式 | BM2方式 | all 1 or (\(a_{xy}\),0,…,0) |
|
| BM3.2 Nish 2018.7.23 |
|
上行枝無視方式 | 上行枝無視方式 | all 1 or (\(a'_{xy}\),0,…,0) |
|
| BM3.1.1 Ecl1psed 2018.7.20 |
|
上行枝無視方式 | BM2方式 | all 1 or all 0 |
|
| BM2.2 koteitan 2018.3.8 |
共通先祖探索 | 全枝有効方式 | 改変なし |
|
- bad root
- bad part(悪い部分)の最左列のことです。
共通ルール
- バシク行列は要素が自然数である行列と、ブラケットと呼ばれる一つの自然数から成る。
- バシク行列では\(\begin{pmatrix}c_{11}&c_{21}\\c_{12}&c_{22}\end{pmatrix}\)を\((c_{11},c_{12})(c_{21},c_{22})\)のように列の要素を横に並べて書くことが多いのでこの資料でもそのように表記することにする。
- \(f(n)\)は自然数から自然数への関数で、BM1, rTSS, BM1.1, Bubby3's fix, BM2, BM4 では\(f(n)=n^2\)、BM2.1, BM2.2, BM2.3 では\(f(n)=n+1\) である。
バシク行列を１段階展開する手順は下記の通りである。
- 最右列を \(C=(c_1, c_2, \cdots c_N)\) とする。
- \(C\) のすべての要素が \(0\) である場合は、bad root が見つからなかったとして 5 にジャンプ。
- \(C\) の非零である最下行のインデックスを \(t\) とする。(\(c_t\gt 0\land \forall k(k\gt t\rightarrow c_k=0)\))
- bad root 探索ルールに従って bad root \(R=(r_1, r_2, \cdots, r_N)\) を決定する。
- 最右列 \(C\) を消す。
- \([n]\) を \([f(n)]\) に変更する。
- bat root が見つからなかった場合は終わる。
- bad root \(R\) とそれより右にある列を合わせた行列を bad part \(B=(b_{11},b_{12},\cdots,b_{1N})(b_{21},b_{22},\cdots,b_{1N})\cdots(b_{L1},b_{L2},\cdots,b_{LN})\) とする。
- この後、bad root がコピーされるが、コピーの際の値の上昇値として
\(\Delta=(\delta_{11}, \cdots, \delta_{1N})\cdots(\delta_{L1},\cdots,\delta_{LN})\)を次のように定義する。\(\forall x~\delta_{xy}=\begin{cases}c_y-r_y&(y\lt t)\\0&(y \geq t)\end{cases}\) - 上昇を行うかどうかのフラグとして、上昇検討行列 \(A'=(a'_{11}, a'_{12}, \cdots, a'_{1N})(a'_{21}, a'_{22}, \cdots, a'_{2N})\cdots(a'_{L1}, a'_{L2}, \cdots, a'_{LN})\) を上昇ルールに従って定義する。
- 上昇改変ルールに従って、上昇検討行列 \(A'\) から上昇行列 \(A\) を求める。
- ブラケット\(n\) の値に従って次に定義する \(B_1, B_2, \cdots, B_n\) をもとの行列に順に右に連結する。
- \(B_1 = B + A \otimes \Delta\)
- \(B_{k+1} = B_k + A \otimes \Delta\)
- \(\otimes\) は行列と行列の要素積で、
\((a_{11},\cdots, a_{1N})\cdots(a_{L1},\cdots, a_{LN}) \otimes (b_{11},\cdots, b_{1N})\cdots(b_{L1},\cdots, b_{LN}) \)
\(= (a_{11}b_{11},\cdots, a_{1N}b_{1N})\cdots(a_{L1}b_{L1},\cdots, a_{LN}b_{LN})\)
以上。
以上の展開を繰り返し、行列がなくなったときのブラケットの値が元のバシク行列に対応する巨大数となる。
bad root 探索ルール
左隣法
- \(t\) とそれより上の全ての行 \(y \leq t\) で \(m_y > c_y\) を満たし、かつ \(c\) より左にある列 \(M=(m_1, \cdots, m_N)\) が存在すれば、その最右列 \(M\) を bad root \(R\) とする。なければ bad root は見つからなかったとする。
上行枝無視方式 (Upper-Branch-Ignoring-Model)
- 要素 \(c\) 自身、または、\(c\) の直系先祖の親を、「\(c\) の直系先祖」と再帰的に定義する。
- 要素 \(c\) に対して、
- \(c\) と同じ行にある
- \(c\) より左にある
- \(c\) より値が小さい
- 最上行にあるか、または、\(c\) のひとつ上の要素の直系先祖のいずれかと同じ列にある
をすべて満たす最右の要素 \(m\) を \(c\) の親と定義する。
- \(C\) の非零最下行要素 \(c_t\) の親がいる場合は、その親のいる列を bad root \(R\) とする。親がいない場合は bad root は見つからなかったとする。
共通先祖探索 (concestor method)
- 要素 \(c\) 自身、または、\(c\) の直系先祖の親を、「\(c\) の直系先祖」と再帰的に定義する。
- 要素 \(c\) に対して、
- \(c\) と同じ行にある
- \(c\) より左にある
- \(c\)より値が小さい
をすべて満たす最右の要素 \(m\) を \(c\) の親と定義する。
- 非零最下行 \(t\) とそれ以上の全ての行 \(y \geq t\) において、 \(m_y\) が \(c_y\) の直系先祖であるような列 \(M=(m_1, \cdots, m_N)\) が存在すれば、その中の最右列を bad root \(R\) とする。そのような列が無ければ bad root は見つからなかったとする。
bad part 上昇ルール
全枝有効方式
- \(\forall x,y(a'_{xy}=1)\)
BM2 方式
\(a'_{xy}\) を下記で定める。
\[p(x)=\max\left\{k|k \lt x \land b_{k1} \lt b_{x1}\right\}\] \[\forall y \left(a'_{1y}=１\right)\] \[\forall x\gt 1,~y (a'_{xy}=１ \leftrightarrow a'_{p(x)y}=1 \land b_{1y} \lt b_{xy}) \]
\(p(x)\) は列 \(x\) の親の列を表す。これは最上行のみで決まる。
2行目は bad root は常に上昇することを表している。
3行めは \(b_{xy}\) は「\(b_{xy}\) と同じ行にあり親の列にある要素が上昇する」かつ「\(b_{xy}\) が \(b_{xy}\)と同じ行にあり bad root の列にある要素の値よりも大きい」を満たす時その時のみ上昇することを表す。
上行枝無視方式 (Upper-Branch-Ignoring-Model)
- 要素 \(c\) 自身、または、\(c\) の直系先祖の親を、「\(c\) の直系先祖」と再帰的に定義する。
- 要素 \(c\) に対して、
- \(c\) と同じ行にある
- \(c\) より左にある
- \(c\) より値が小さい
- 最上行にあるか、または、\(c\) のひとつ上の要素の直系先祖のいずれかと同じ列にある
をすべて満たす最右の要素 \(m\) を \(c\) の親と定義する。
- \(r_y\) が \(b_{xy}\) の直系先祖であるような \(x, y\) の組について \(a'_{xy}=1\)、それ以外の時 \(a'_{xy}=0\)
上昇改変ルール
改変なし
\(\forall xy (a_{xy}=a'_{xy})\)
All 1 or (\(a'_{xy}\),0,…,0)
ある列 \(x\) について、下記のように \(a'_{xy}\) から \(a_{xy}\) を定める。
- もし\(\forall y \leq t(a'_{xy}=1)\) なら \(\forall y(a_{xy}=1)\)、そうでなければ、\(a_{x1}=a'_{xy}\) かつ \(\forall y \gt 1(a_{xy}=0)\)。
All 1 or All 0
ある列 \(x\) について、下記のように \(a'_{xy}\) から \(a_{xy}\) を定める。
- もし\(\forall y\leq t(a'_{xy}=1)\) なら \(\forall y(a_{xy}=1)\)、そうでなければ、\(\forall y(a_{xy}=0)\)。
注釈
- ↑ 正式名が無かったので、BM1.1というのはこのページで私が勝手に仮につけた名前です。