第1回 よい組合せの見つけ方 -食べたいものから順に食べた方がいい理由- 藤井 海斗 私たちは日々「組合せ」を選んでいます。例えば、ファミレスで料理をいくつか注文するとき、よい「組合せ」を選ぶことが大切です。しかし多くの場合、考えられる組合せは非常に多く、すべての組合せを一つ一つ確認することはできません。では、よい組合せを効率的に発見するにはどうすればいいでしょうか。このような問題を考えるのが「組合せ最適化」という分野です。 組合せ最適化にはさまざまな技法がありますが、なかでもよく用いられるのが 「貪欲法」です。貪欲法は、その名前の通り、欲しいものを順に選ぶという単純なアルゴリズムです。しかし、単純であるにもかかわらず、「劣モジュラ性」という自然な条件のもとで、よい組合せを見つけることが理論的に保証されています。 本講座では、劣モジュラ性がどのような性質なのかを紹介し、さらにその発展的な利
![2022年度 市民講座 「情報学最前線」 - イベント - 国立情報学研究所 / National Institute of Informatics](https://cdn-ak-scissors.b.st-hatena.com/image/square/ea0e488675c836672525ef747b51b23405f9f6fd/height=288;version=1;width=512/https%3A%2F%2Fwww.nii.ac.jp%2Fevent%2Fupload%2FD_YT_TM_00.jpg)