制約処理について（承前）

JCUnitでいかにして制約処理(禁則処理)を行っているか？結局のところ、以下の実装がその本質である。

jcunit/IpoGplus.java at 0.8.x-develop · dakusui/jcunit · GitHub

組み合わせテストにおいて、テストスイートの生成と制約処理は同時並行で行わなくてはならない。なぜか？

素朴には、まず制約を度外視してテストスイートを生成しておき、制約に違反するテストケースを取り除き、カバーされていないタプルのために新しいテストケースを生成・・・このプロセスを全ての可能なタプルが網羅されるまで反復する。というアルゴリズムが考えられる。

しかし、この過程は実用的な時間で終わるのだろうか？

実験や調査をしたことはないが、これははなはだ疑問なのである。 なぜかといえば、組み合わせテストにおいてテストケースは、テストスイートができるだけ小さくなるよう生成される。その一方、制約は複雑になりがちである。このため制約を考慮せずに生成したテストスイートはそこに含まれるテストケースの大部分、もしくは全部が制約に違反していることがあり得るからである。

上述の実装は、このことを踏まえて設計されている。基本的なテストスイート生成アルゴリズムはIPO-Gと呼ばれるものである。テストスイート生成の過程で、制約に違反したタプルは網羅されるべき組み合わせから除外しておき、制約に違反しないテストケースを生成する工夫が組み込まれている。性能の最適化のために、制約に適合する組み合わせを選択するための処理はメモ化されていたりとかの工夫もしている。

私や私のチームで使用している限りでは、今のところ実用的な性能を発揮している。しかし残念ながら、NISTのACTSには速度上まったく及ばない。制約定義方法の柔軟さではかなりの優位性を主張できるが。

もしも、このアルゴリズムについてのさらなる解説に興味をお持ちの場合、このブログにその旨のコメントを残して欲しい。