Greedy
証明方法
https://youtu.be/k2fzO_U7RnA?t=3359
貪欲法の戦略$ s^*とします.
そして,ある問題を解くアルゴリズムを途中まで戦略$ s^{*}とします.
そして,あるタイミングで異なる戦略$ s'に変更し,それによって得られる利得が最大になったと仮定します.(背理法)
しかし,実際には利得が減少している可能性があり,これを部分的交換などをしてもとの戦略$ s^{*}の状態にまでもっていき,やはり貪欲法が正しい最適解を得られるということを示します.
ここで,部分的交換は必ず「現状より悪くならない」ような変化のみが許容されます.
もし一回でも悪くなるような操作があるのであれば,貪欲法の上で最適性がなくなります.
また,必ず良くなるわけではありません.各操作によって,「同じ」か「改善される」が行われるだけであり,必ず良くなるわけではありません.
https://gyazo.com/0b66e6227ace03b43c0ebaf37d48e78f