ある状態からいくつかの近傍をつたってより良い状態へ到達することを考えます。 このとき、より良い状態はある状態と比べて部分的にどこかは改善しているはずです。 そのため、少なくとも 1 つの近傍は部分的な改善を含むことになります。 そこでもし、すべての近傍を少なくとも部分的に改善するものだけに限定したとすると、2 つのメリットが考えられます。
- 部分的に改善するのでトータルでもスコア変化量が悪すぎず、探索空間がなだらかになります。
- 部分的にすら一切改善しない近傍は無数のより良い状態から遠ざかる傾向にあり、それを無くすことは冗長な空間を削ぎ落としランダムウォークの質を高めます。
実際では現行の近傍について変更前の状態・変更後の状態・変更のされ方から近傍を細分化して、不要なものを削るといったやり方をよくします。
- Topcoder GraphDrawing / chokudai, 他最上位多数 / スコアに影響する頂点ただ1点だけを動かす
- Atcoder Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017 / kurenai3110, 他最上位多数
問題によってはスコアを決定する要素が限られたり、スコアが良くならないことが静的にわかることがあります。 それらを近傍から除くことで空間がとても小さくなることがあります。
- Topcoder CrossStitch / hakomo, 他
- Topcoder KnightsAndPawns / hakomo / ペナルティをスコアとみなし valid な部分を能動的に破壊しない
部分最適な部分というのは局所的にはそれ以上改善できません。 もし部分が最適かどうかが高速に求まるなら、部分未最適を改善する近傍だけに限定することができます。 良い状態の大部分が最適なことはよくあるので空間がとても小さくなります。