枝刈り探索が根本的に計算量改善することを示せることがある！！！ 有名な例は最大独立集合問題に対する のアルゴリズムかなと。 指数時間アルゴリズム入門 from Yoichi Iwata www.slideshare.net 問題へのリンク 問題概要 下図 (公式解説より) のように な…

bit 全探索 問題へのリンク 問題概要 個のスイッチがある。スイッチによって 個の電球が点いたり消えたりする。 電球 は 個のスイッチに繋がっており、スイッチ のうち on になっているスイッチの個数を 2 で割った余りが に等しい時に点灯します。 全ての電…