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

分枝限定法には2つの手続きが必要である。第一は「分割」手続きである。これは、与えられた集合 <math>S</math> に対して、<math>S_1\cup S_2\cup \ldots =S</math> となるような複数の集合 <math>S_1, S_2, \ldots</math> に分割する手続きである。<math>SS_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> の部分集合となるような[[木 (数学)|木]]（[[探索木]]）になる。