グラフ探索問題について、最良優先探索アルゴリズム(GBFS)を並列化すると、しばしば逐次GBFSでは展開しないようなノードを展開し、無秩序な挙動をする。そこで探索をGBFSが探索する可能性のある空間、BTS(Bench Transition System)内に制限する手法PUHFが提案された。しかし、PUHFではBTSに含まれることが保証された状態のみを探索するために展開に制約を設け、スレッドが多くの待機時間を費やす。本研究で我々はPUHFの改良を提案し、待機時間を大幅に削減し探索性能を向上させる手法を開発・評価した。