双向广搜 DBFS

双向广搜 DBFS

双向：简而言之就是从起点（正向搜索）和终点（逆向搜索）同时开始搜索，当两个搜索产生的一个子状态相同时就结束搜索。

通常有两种实现方法：

1、用一个队列来储存子状态，起点和终点先后入队，正向搜索和逆向搜索交替进行，两个方向的搜索交替扩展子状态。直到两个方向的搜索产生相同的子状态结束。

2、两个方向的搜索虽然是交替扩展子状态的。但是两个方向生成的子状态的速度不一定平衡。所以，可以每次选择子状态数较少的那个方向先进行扩展。这样就不会出现两个方向生成子状态的速度的不平衡，可以明显的提高效率哦。

这里只给出用第一种方法实现的代码。因为双向广搜要判断两个方向搜索产生的子状态是否相同，所以要用到标记数组和记录结果的数组一个或两个任选，这里用的是一个数组来标记，正向标记为1，逆向标记为2，0表示未访问。

模板

void TBFS()
{bool found = false;memset(visited, 0, sizeof(visited)); // 判重数组while (!Q1.empty())Q1.pop(); // 正向队列while (!Q2.empty())Q2.pop(); // 反向队列//======正向扩展的状态标记为1，反向扩展标记为2visited[s1.state] = 1; // 初始状态标记为1visited[s2.state] = 2; // 结束状态标记为2Q1.push(s1);           // 初始状态入正向队列Q2.push(s2);           // 结束状态入反向队列while (!Q1.empty() || !Q2.empty()){if (!Q1.empty())BFS_expand(Q1, true); // 在正向队列中搜索if (found)                // 搜索结束return;if (!Q2.empty())BFS_expand(Q2, false); // 在反向队列中搜索if (found)                 // 搜索结束return;}
}
void BFS_expand(queue<Status> &Q, bool flag)
{s = Q.front(); // 从队列中得到头结点sQ.pop();for (每个s 的子节点 t){t.state = Gethash(t.temp) // 获取子节点的状态if (flag)             // 在正向队列中判断{if (visited[t.state]!=1）// 没在正向队列出现过｛if(visited[t.state]==2)  // 该状态在反向队列中出现过{各种操作；found = true；return;}visited[t.state]=1;   // 标记为在在正向队列中Q.push(t);  // 入队｝｝else    // 在反向队列中判断{if (visited[t.state]!=2） // 没在反向队列出现过｛if(visited[t.state]==1)  // 该状态在正向向队列中出现过{各种操作；found = true；return;}visited[t.state]=2;  // 标记为在反向队列中 Q.push(t);  // 入队｝ ｝              
}