概要

枝苅りつきの組合せ探索を行なうことによって望まれる解を全て生成する. もっ とも単純に考えるとこれは, スタック領域の数をNとして, 通りの可能 性を試すことになるが, 以下のような前処理および動的な枝苅りによって探索 空間の数を減らす.

前処理

これはあらかじめスタック領域の集合を分割しておき, 一つ の分割に入るスタック領域はどの二つも互いに共存不可能であるように しておく. 分割の一つ一つを, incompatible islet [1] と呼ぶ. 分割のしかたから, 各々のincompatible isletからは高々一つのスタッ ク領域しかとれないので, 探索は, 各incompatible isletから0個または1個の 要素を選んでいく形で行なわれる. すなわち 探索木の深さはincompatibleisletの数になる.

枝苅り

探索の各段階で, その時点で未処理のincompatible islet全 てから最大のエネルギーを得たとして達成できるエネルギーを評価し, それが 解になり得ないとわかる場合その時点で探索を打ち切る. 具体的には, その時 点で求まっている最大のエネルギーをEとして, 評価値がE - T未満であ る場合に探索を打ち切る. ここでこの評価を効果的にするためにも incompatible isletが働いている.

上述のE(各時点で求まっているエネルギーの最大値)は, 時間の経過ととも に更新され, 更新した時にはプロセッサ間でそれを伝え合う機構が必要である.

以下, 前処理(incompatible isletを求める処理), (並列)探索, 解の更新の機 構について説明する.