詳解 PICTのヒューリスティック・アルゴリズム

前回はPairwise法（All-Pairs法）の正確な定義を紹介しました。今回はPICTが採用している組み合わせ生成アルゴリズムである「ヒューリスティック・アルゴリズム」について詳しく説明します。この説明は2008年9月17日の記事 で「PICTの組み合わせ生成アルゴリズム」というタイトルで1回行なったことがあります。しかし当時の記事ではフォントの制限から文字の判読がしづらく、説明もほとんどありませんでした。今回はそういうことがないよう、きれいなフォントで読みやすくしました。また注釈を多くつけてできるだけ分かりやすいように配慮しました。

以下で示すPICTのアルゴリズムは、例によってPICTの開発者であるJacek Czerwonka氏が2006年に発表した論文「Pairwise Testing in Real World」からの引用です。そのアルゴリズムを図5に示します。図5で示されているアルゴリズムは最終的にはいくつかのテストケースの集まりとなる組み合わせのうち、1つのテストケースの1つの組み合わせを生成するアルゴリズムを示しています。このアルゴリズムの記述では、説明を簡単にするためにいくつかの仮定（前提条件）が用いられています。

注釈のために数字記号を追記したものを示します。

このアルゴリズムについて、注釈の数字順に従って説明していきます。

以上のアルゴリズムは、1つのテストケースの1つの組み合わせを生成する部分についてのものです。このアルゴリズムを繰り返し実行することで、組み合わせの集合P において除外組み合わせを除いた残りのすべての組み合わせが網羅とマーキングされ、かつテストケース ri のすべてのパラメータに値があるとき、必要とされるすべてのテストケースの生成は完了します。

⑧と⑮で「未網羅組み合わせを最も多く網羅する」スロットを選択していますが、この部分が「グリーディ」（どん欲な）と呼ばれる部分です。できるだけ少ないテストケース数ですべての可能な組み合わせを網羅しようとする、言い換えれば、うまく行けば最適解、最適解でなくともできるだけ最適解に近い結果を得ようとすることから、PICTが採用しているアルゴリズムは、正確には「グリーディ・ヒューリスティック・アルゴリズム」と呼ばれます。ヒューリステックとは自己発見的という意味です。いつも同じ結果となるアルゴリズムと異なり、シード値という初期条件によって異なる結果となります。おそらく組み合わせの制約をサポートするには、ヒューリステック・アルゴリズムが最適と考えられます。