劣モジュラ関数

OR事典

劣モジュラ関数

読み方：れつもじゅらかんすう
【英】：submodular function

分配束 上の関数 が, 任意の に対して

を満たすとき, を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である.

「OR事典」の他の用語

グラフ･ネットワーク：

劣モジュラシステム  劣モジュラフロー問題  劣モジュラ最適化  劣モジュラ関数  同形性  基多面体  基族

ウィキペディア

劣モジュラ関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/12 21:53 UTC 版)

数学の分野において劣モジュラ関数 (英: submodular function) とは集合関数の一種で、簡単にいうと、関数に渡される集合に1つ要素が加わった場合に増える関数の値が、もとの集合が大きくなるにつれ小さくなるような関数を指す。集合関数であることを明示して劣モジュラ集合関数ということもある。劣モジュラ関数の概念は一般のベクトル値関数における凸関数の概念と類似した性質を持つため、近似アルゴリズムやゲーム理論、機械学習などの幅広い応用を持つ。