以下の内容はhttps://blog.hamayanhamayan.com/entry/2017/12/23/155922より取得しました。
枝刈り
- たまに枝刈り全探索みたいな解法が想定解の場合がある
- 「貪欲に枝刈りをしていくとなぜか通ってしまう」とか「validな状態はそんなに無いから実装が楽な枝刈り全探索」とかそういうのがある
- 枝刈りで計算量が落とせる名前がついている手法
- 二乗の木DP
- 木DPをする際にDPの使われていない要素は枝刈りをして更新をしない
- 分枝限定法
- 参考
- 簡単な方針で求めた下界や上界の範囲内で全探索を行うと計算量が減る
- テストケースに悪意がない（ランダム生成）の場合は特に有効
以上の内容はhttps://blog.hamayanhamayan.com/entry/2017/12/23/155922より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14
