見つけたい最適解に制約をつけて探索範囲を絞る
以下では、最適解を求めることが問題となっている場合を取り扱う。
特定の制約$ Rを探索空間に課すと、探索空間が大幅に縮まるとしよう。
制約$ Rを課しても最適解に到達できることを示しさえすれば、最適解を探るにあたり、探索空間を大幅に縮められる。 その制約$ Rに沿わない最適解が他にもある場合でも、最適解を列挙することが目的でなければ有効。
そもそも探索空間が曖昧だったり、最適解を探る探索範囲が爆大すぎる時に、有力な絞り込みとなる 制約のおかげで、探索範囲が十分に縮まると考えられる。
座標を探索する問題から、点や線ごとに探索する問題に縮められる（正確性・高速化に寄与）
他に最小の内包円はあるかもしれないが、問題となるのは最適解を一つ発見することであり、最適解を列挙できなくても問題ではない。 最適解が一意に定まることが知られているので、実は、この方法で探った最適解は全ての最適解を列挙できている。
---> 期待$ O(N)アルゴリズムの発見
三角形中の点を全て列挙するのはしんどい...というか不可能
というわけで、位相的に状況が変わるような場所だけに着目することで、探索範囲を大きく絞った。
それ以外にも最適解は存在するかもしれないが、そのような戦略でも最適解には到達できる。
全ての戦略は、貪欲法による戦略$ Sに対して、敵に対するポーションの保有時間が$ S"以上"に長い。
code:example.txt
P---P--P-------E-----E---> t
| | | | | <--- このEの部分は固定されている。
| | +-------+ |
+- -+----------------+
<-- 他の戦略を作り出そうとしても、こっち方向に伸ばすしかない
よって、各時刻におけるポーション保有数は貪欲法による戦略より、等しいかより大きくしかならない。
処理機械$ S_i, T_iの導入個数を探索することで、定められたノルマを達成するような最小の導入金額を求めるような時
最適な戦略において、$ S_iと$ T_iのいずれかが特定の台数以下でも問題がないことを示した。
その制約に沿わない最適戦略もありうるかもしれないが、その制約の元で探索しても最適戦略に辿り着ける。
探索範囲に上界をつけ、高速に探索できるようにした