「テスト時の消費電力削減」問題の解答

最小の消費電力は,...

t1,t2,t3,t4の並べ方は24通りあります.
テストパターンが多くなるとすべての通りを調べることは不可能です.

例えばt1から始めるとする.
t1からできるだけ電力の少ないものを順に選ぶと,
t1-t3-t2-t4という順番が得られ,消費電力は5+5+6=16となる.
このようにその時点でできるだけ最適なもの(ここでは電力の少ないもの)を選ぶような手法をグリーディ法と言います.

もしt4から始めると,t4-t2-t3-t1という順番が得られ,
この時消費電力は4+4+6=14で最小となります.