|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 整数 ： [せいすう] 【名詞】 1. integer ・ 数 ： [すう, かず] 1. (n,n-suf) number 2. figure ・ 計 ： [けい] 1. (n,n-suf) plan ・ 計画 ： [けいかく] 1. (n,vs) plan 2. project 3. schedule 4. scheme 5. program 6. programme ・ 画 ： [かく, が] 【名詞】 1. stroke ・ 問 ： [もん] 【名詞】 1. problem 2. question ・ 問題 ： [もんだい] 【名詞】 1. problem 2. question ・ 題 ： [だい] 1. (n,vs) title 2. subject 3. theme 4. topic
整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトル''x''の各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題には存在しない。 解ベクトルxの各要素を0または1のみに限定したものを、特に0-1整数計画問題という。 == 整数計画問題として解かれる問題の例 == *頂点被覆問題 *ナップサック問題 *ハミルトン閉路問題 *巡回セールスマン問題 *集合被覆問題 *施設配置問題 *最大独立集合問題 *最小極大マッチング問題 *最大クリーク問題 *支配集合問題 *辺支配集合問題 *ビンパッキング問題 *一般化割当問題 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「整数計画問題」の詳細全文を読む スポンサード リンク
|