枝刈り（Branch and Bound）

定義

木構造の探索において、すでに見つかった解より明らかに悪い部分木を探索しないことで計算を効率化する技法。k-NNのkd-tree探索では、仮の最近傍距離を半径とした球が他の領域に侵入しないことが確認できた場合、その領域全体を枝刈りしてスキップできる。