最大化問題を分枝限定法で解くとき、ある部分問題の探索を打ち切ってよいのは、どのような場合か。

解説

正解は「その部分問題から得られる値の上界が、暫定解の値以下のとき」です。分枝限定法は、問題を部分問題に分ける分枝と、見込みのない部分問題を切り捨てる限定を組み合わせた方法です。最大化問題では、それまでの最良の解（暫定解）を記録し、ある部分問題の上界が暫定解以下なら、その先を調べても暫定解を超えられないので打ち切ります。ナップサック問題では、品物を分割できると仮定した値を上界に使えます。「その部分問題から得られる値の上界が、暫定解の値より大きいとき」は、より良い解の可能性があるので探索を続けます。「その部分問題が、探索木の最も深いところにあるとき」や「その部分問題に含まれる解の候補の数が多いとき」は、打ち切りの基準ではありません。