双方向検索の実装方法に関係していると思います。
BFS の疑似コードは次のようになります。
until frontier.empty?
node <- frontier.pop()
add node to explored
for each child not in expored or frontier:
if child is goal then
return path
add child to frontier
次のような双方向検索の実装を想像してください。
until frontierForward.emtpy? or frontierBackward.empty?
node <- frontierForward.pop()
add node to exploredForward
for each child not in exporedForward or frontierForward:
if child in frontierBackward then
return pathForward + pathBackward
add child to frontierForward
Do something similar but now searching backwards
基本的に、「前方」BFS と「後方」BFS のステップを交互に繰り返します。次のようなグラフを想像してください。
B-C-D
/ \
A E
\ /
F - G
BFS の最初の順方向および逆方向の実行では、次のような状態になります。
1) expandedForward = A ; frontierForward = B, F
2) expandedBackward = E ; frontierBackward = D, G
これで、アルゴリズムは前方フロンティアから拡張する次のノードを選択し、B を選択します。
3) expandedForward = A, B ; frontierForward = F, C
次に、後方 BFS を実行し、ノード D を展開します。D の子である C は前方フロンティアにあるため、パス A - B - C - D - E を返します。
これは、ラッセルとノーヴィグが言及しているものだと思います。実装でこのシナリオが考慮されていない場合、最適ではないソリューションが得られる可能性があります。
最適なソリューションを見つけたと判断する前に、同じ「深さ」を持つフロンティア内のすべてのノードの展開を終了する必要があります。または、ノードではなくレイヤーごとに順方向および逆方向の BFS 検索を交互に行うこともできます (レイヤー 0 のすべてのノードを前方に展開し、レイヤー 0 のすべてのノードを後方に展開し、レイヤー 1 のすべてのノードを前方に展開するなど)。