応用情報技術者 2010年 春期 午前2 問48

出次数による最小テスト数【午前2解説】

正解の理由

解法ステップ

1. 各判定ノードの「出次数（そのノードから出る異なる矢印の数）」を数える。今回は上段=3、中段=2、下段=3。
2. 命令網羅（各命令を少なくとも1回実行すること）を満たすためには、各分岐先に到達する必要がある。各判定ノードで異なる分岐を同一実行で複数取ることはできないため、あるノードの全分岐を網羅するにはそのノードの出次数分のテストが必要。
3. 全ノードの分岐を同時にカバーする最小数は、個別に必要なテスト数の最大値に等しい（どのノードにも十分な試行回数が確保されれば、出次数の小さいノードはその範囲内で分岐を分配できるため）。
4. よって答えは $\max (3,2,3)=3$。

• テスト1：D1→左、D2→左、D3→左
• テスト2：D1→下、D2→右、D3→下
• テスト3：D1→右、D2→左、D3→右 このように3ケースで各判定ノードのすべての出力先を少なくとも一度ずつ通ります。

選択肢別の誤答解説

• ア（3）
  • 正答。上で示したとおり、出次数の最大値 $\max (3,2,3)=3$ により最小テスト数は3になる。
• イ（6）
  • 誤り。6は（例えば各ノードの一部を重複せずに数えた）誤った集計の結果に見えるが、出次数が小さいノードの分岐は限られたテストケース内で割り当て可能なので必ずしも6ケースは不要である。
• ウ（8）
  • 誤り。8は各ノードの出次数を単純に合算した値（3+2+3=8）に相当するが、合算する考え方は間違い。合算すると「同じテストで複数の異なるノードの分岐を別々に実行できない」前提を無視している。異なる判定ノードの分岐は1つのテストで同時に取れるため、合算は過大評価となる。
• エ（18）
  • 誤り。18は全分岐の組み合わせ数（経路数）を求めた場合の積 $3\times 2\times 3=18$ に相当する。これは経路網羅（すべての分岐の組合せごとの実行）を目指すときに必要な最大ケース数だが、本問の網羅基準は命令網羅（各命令を少なくとも一度実行）であり、経路網羅ほど厳しくないため18は不要である。

よくある誤解

• 「判断ノードの個数＝必要テスト数」と考える誤解
  • 判断ノードが3つでも、各ノードの出次数が全て2以下なら2ケースで足りることがある（必要数は出次数の最大値に依存する）。
• 「全ての分岐の組合せ（全経路）を全て試す必要がある」と考える誤解
  • 命令網羅は各命令（分岐先の処理など）を少なくとも1回実行することを要求するに留まり、全経路を試す経路網羅とは異なる（経路網羅は通常より多くのテストが必要）。

補足コラム

• 命令網羅（statement coverage）と分岐網羅（branch coverage）の関係：
  命令網羅は「すべての命令を1回実行する」こと、分岐網羅は「各分岐のそれぞれの方向（真／偽や各選択肢）を少なくとも1回通る」ことを要求します。本問では分岐ごとの矩形ノード内の命令を実行する必要が前提のため、事実上「各分岐を1回通る」ことが必要になり、命令網羅と分岐網羅が同程度の厳しさになります。
• 依存による増加：問題文で「各判定条件は先行命令の結果から影響を受けない」とある点が重要です。もし判定条件が前段の結果（状態）に依存していた場合、出次数の最大値だけでは足りず、より多くのテストが必要になる可能性があります（最悪、経路の組合せ数に近い数が必要になることもあります）。

FAQ