「分枝限定法」の版間の差分

: 第一は分枝操作である。場合分けにより部分問題に分割する。つまり、与えられた集合 <math>S</math> に対して、<math>S_1\cup S_2\cup \ldots =S</math> となるような複数の集合 <math>S_1, S_2, \ldots</math> に分割（分枝）する手続きである。<math>S_i</math> における <math>f(x)</math> の最小値を <math>v_i</math> としたとき、<math>S</math> における <math>f(x)</math> の最小値は <math>\min\{v_1, v_2, \ldots\}</math> である。この手続きを再帰的に適用することは'''分枝法''' (branching) と呼ばれ、各ノードが <math>S</math> の部分集合となるような[[木 (数学)|木]]（[[探索木]]）になる。なお <math>S_i \cap S_j \ne \emptyset</math> でも良い。