|
整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトル''x''の各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題には存在しない。 解ベクトルxの各要素を0または1のみに限定したものを、特に0-1整数計画問題という。 == 整数計画問題として解かれる問題の例 == *頂点被覆問題 *ナップサック問題 *ハミルトン閉路問題 *巡回セールスマン問題 *集合被覆問題 *施設配置問題 *最大独立集合問題 *最小極大マッチング問題 *最大クリーク問題 *支配集合問題 *辺支配集合問題 *ビンパッキング問題 *一般化割当問題 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「整数計画問題」の詳細全文を読む スポンサード リンク
|