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