Pairwise法(All-Pairs法)のヒューリスティックアルゴリズムを試してみる | 組み合わせテストケース生成ツール 「PictMaster」 とソフトウェアテストの話題

Pairwise法(All-Pairs法)のヒューリスティックアルゴリズムを試してみる

PICTが採用しているPairwise法(All-Pairs法)のヒューリスティックアルゴリズムについては2009年10月09日の記事 で説明しました。今回は、PICTのヒューリスティックアルゴリズムを実際のモデルに適用し、すべてのペアの組み合わせを網羅する具体的な方法を説明します。


この説明に用いるモデルでは、パラメータが6個あり、それぞれが3個の値を持っています。それでは順を追って説明します。


(1)すべてのペアを網羅した全ペア配列を定義します。この配列自体は簡単に定義することができます。このモデルでは9×15=135個のペアの値を持つ配列となります。


(2)生成したテストケースを格納するテストケース配列を定義します。このモデルでは1行が6列からなる配列が17行ほどもあれば十分でしょう。


(3)ここから1つのテストケースを生成する方法の説明となります。


 1)全ペア配列からランダムに1つのペアを取り出し、それぞれの値をそのパラメータの列のテストケース配列に格納します。配列に格納できたら全ペア配列の当該ペアをマーキングします。


 2)すでにテストケース配列に他の値があるときは格納できないので、全ペア配列の当該ペアの位置から下に移動し、テストケース配列に配置できるペアの値を探します。一番下まで探しても見つからないときは右側の列の配列を上から下に探します。最も右側の列を探してもテストケース配列に配置できるペアの値が見つからないときは最も左側の上から下に探します。以降同様に空きのテストケース配列に配置できる値が見つかるまで検索を繰り返します。最後まで検索しても見つからないときは空きのテストケース配列に任意の値を格納します。(※ ここで示した方法はPICTの処理方法とは異なります)


 3)テストケース配列に格納できたら、そのテストケースに配置されたペアの値によって、他のパラメータの値との関係で新たにマーキング可能な全ペア配列のペアがあるかをしらべ、ある場合は、その全ペア配列上の当該ペアをマーキングします。


 4)1つのテストケース配列のすべてのパラメータの列に値が格納されるまで以上の操作を繰り返します。


(4)以上で1つのテストケースが生成できたので、(3)に戻り、次のテストケースを生成します。全ペア配列のすべてのペアがマーキングされたら生成は終了します。このとき、テストケースに空きの値がある時は、任意の値を格納します。


言葉だけの説明では分かりにくいと思いますので図で説明します。このモデルでの全ペア配列とテストケース配列を以下に示します。このモデルでは値の数がすべてのパラメータで同じなので全ペア配列は長方形になりますが、パラメータにより値の数が異なる場合は長方形の下辺がでこぼこした形になります。


多種類テストケース生成ツール MTG (Multi type Test case Generation tool)-ツール

この図は、最初のテストケースを生成しているところで、全ペア配列から5行目11列目のペア(C=2、E=2)を取り出し、テストケース配列に格納し、全ペア配列の当該ペアの文字色を赤色にマーキングしたところです。テストケース配列を基に全ペア配列上のテストケース配列に格納されたすべてのペアの値を赤色にマーキングするのは、人手では間違いやすいので、「マーク」というボタンを設け、このボタンを押すと、テストケース配列で値が格納された最も下のテストケースを調べ、その行に格納されたパラメータの値で構成されるすべてのペアを全ペア配列上で文字色を赤色にマーキングするようにしています。「実行」ボタンは全ペア配列上からランダムにペアを取り出すために、行番号と列番号を決定します。


この図では、パラメータCとEの値がテストケース配列に格納されています。ここで実行ボタンをクリックして全ペア配列からランダムにペアの値を決めます。例えば、B=1、C=1のペアが該当したら、テストケース配列のパラメータCの列には既にC=2の値が格納されているので、B=1、C=1のペアは格納できません。そこで全ペア配列を下に調べて、すぐ下にB=1、C=2のペアがあることが分かります。このペアはテストケース配列に格納することができます。実際に格納するのはB=1だけになります。格納したら、全ペア配列のB=1、C=2のペアの文字色を赤色にマーキングします。


この結果、テストケース配列に格納されている値は、B=1、C=2、E=2の3つとなります。この3つの値から網羅されるペアは、B=1、C=2 と B=1、E=2 と C=2、E=2 の3つのペアとなります。B=1、E=2 はまだ全ペア配列上の値をマーキングしていないのでマーキングを行ないます。このようにテストケース配列に、あるパラメータの値を格納することで、新しく網羅されるペアが発生することがよくあります。


以上の方法(以降、簡易法という)で生成した組み合わせと同じモデルをPICTで生成した組み合わせを並べて示します。簡易法での生成結果がすべてのペアを網羅していることは確認済みです。


多種類テストケース生成ツール MTG (Multi type Test case Generation tool)-生成結果1


PICTでは13個、簡易法では15個となりました。簡易法もランダムな値を用いているので組み合わせの個数が若干変動しますが、何回か試してみた結果、15個が最少でした。


パラメータの個数が同じ6個、パラメータの値が4個の場合でも試してみました。


多種類テストケース生成ツール MTG (Multi type Test case Generation tool)-生成結果2


PICTでは23個、簡易法では27個となりました。PICTの方が少ない個数で済んでいるのはグリーディ(貪欲)なアルゴリズムを採用しているためだと考えられます。簡易法では、テストケース配列に格納するペアをランダムに選んでいますが、グリーディな方法では、テストケース配列に格納できるペアのうち、格納した結果として最も多くのペアを網羅できるペアを選択するようにしています。


簡易法では生成される組み合わせの個数が多くなりがちですが、ランダムな条件で多くの回数生成を繰り返すことによってより少ない組み合わせの個数となることが期待できるかもしれません。