队列应用——广度优先搜索.doc

队列应用广度优先搜索如图 ：求出从节点 1 到节点 8 的最短路径的长度（ 1 到 8 最少的边数 ）。使用计算机求解的问题中，有许多问题是无法用数学公式进行计算推导找出答案的。就像这一题，需穷举从节点1到节点8的所有路径才能找到答案。穷举是最朴素的搜索。穷举所有路径，面对大规模数据将是很可怕的，采用广度优先搜索法(BFS)，就不必穷举所有路径，大大提高效率。用广度优先搜索法解答此题的过程：1.先搜索所有节点中距节点1最近的点节点1（距离为0）；2.再搜索与节点1 距离为1的节点2，3，5；3.然后搜索与节点1距离为2的节点与节点2，3，5中某点距离为1且尚未搜索过的节点6，7，4，9；4.再搜索距节点1距离为3的节点与节点6，7，4，9中的某点距离为1且尚未搜索过的节点8；由以上过程可以确定1到8的最短距离为3（可以用反证法证明此结论的正确性）。整个过程如下图：可以看出搜索的过程是“一层一层”的，从第一层开始，每层的节点都会被“用”来产生下一层的节点，当这一层的节点被“用完”后，才用它们所产生的下一层节点来产生新的节点层，而同一层的节点可以按任意顺序“使用”，一般采用的原则是先生成的结点先“使用”。对“使用”一词，更恰当的说法是“扩展”。广度优先搜索算法中，为了便于进行搜索，要设置一个表存储所有的节点，为了满足先生成的节点层（节点）先扩展的原则，存储节点的表一般设计成队列的数据结构。搜索过程中不断地从队列头取出节点进行扩展。对生成的新节点，要检查它是否已在队列中存在，还要检查它是否目标节点。如果新节点是目标节点，则搜索成功，程序结束；若新节点不是目标节点，并且未曾在队列中出现过，则将它加入到队列尾，否则将它丢弃，再从队列头取出节点进行扩展.。最终可能产生两种结果：找到目标节点，或扩展完所有节点有找到目标节点。题一 ： 求两点间的最短路径长度在一由 n （1=n=100） 个节点，m (1=m=n*(n-1)/2 ) 条边构成的图中，求出节点 s 到 t 的最短路径长度。输入（ input.txt ）： 第一行 n, m, s, t; 接下来 m 行，每行两个整数 i，j （ 1 =i,j =n )，表示 i，j间有一条边。输出( output.txt )： S 到 t 的最短路径的长度（从s到t经过的最少边数），若从s无法到达t，输出 -1.分析：布尔数组bVisitedi 非零表示节点i 已在队列中，为零表示尚未入队； 布尔数组bAdjij 非零表示节点i 与节点j 之间有一条边，否则无边；队列 q, 队首 iH, 队尾 iT;stepi 表示起点到节点 i 的最短距离。（数据见习题）源代码 ：#include using namespace std;ifstream fin( input.txt );ofstream fout( output.txt );const int LQ = 110, N = 110;int bNoAns,bVisitedN=0, bAdjNN=0;int n, m, s, t, iH, iT, qLQ, stepN=0;int InputDataAndInitialize( void );int BFS( void );int OutputAnswer( void );int main(int argc, char* argv) InputDataAndInitialize(); BFS(); OutputAnswer(); return 0;int InputDataAndInitialize( void ) fin n m s t; int i, j; for( ; m-; ) fin i j; bAdjij = bAdjji = 1; for( i=1; i=n; +i ) bAdjii = 0; iH = 0; iT = 1; q0 = s; bVisiteds = 1; bNoAns = 1; return 1;int BFS( void ) if( q0 = t ) bNoAns = 0; return 1; int i, j; while( iH iT ) i = qiH+; for( j=1; j=n; +j ) if( (!bVisitedj) & (bAdjij) ) qiT+ = j; stepj = stepi + 1; bVisitedj = 1; if( j = t ) bNoAns = 0; return 1; return 1;int OutputAnswer( void ) if( bNoAns ) fout -1n; return 1; fout stept endl; return 1;采用广度优先搜索算法（BFS）解答问题时，需要构造一个表明状态特征和不同状态之间关系的数据结构，这种数据结构称为结点（节点）。根据问题所给定的条件，从一个结点出发，可以生成一个或多个新的结点，这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树，它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。广度优先搜索算法中，解答树上结点的扩展是沿结点深度的“断层”进行，也就是说，结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，.对长度为n+1的任一结点进行扩展之前，必须先考虑长度为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。对于不同的问题，用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否目标结点和是否重复结点的判断等方面则有所不同，对具体的问题需要进行具体分析。题二 ：有两个水桶，编号为1，2，容量分别为A 升,B 升, 还有一个数C，对两个水桶可以有如下操作:FILL(i) 将桶 i （ i = 1，2 ）充满；DROP(i) 将桶 i （ i = 1，2 ）中的水倒掉；POUR(i,j) 将桶 i 中的水倒入桶 j 中，这个操作后，桶j 变满（ 桶 i 中可能还有剩余 ），或桶 i 变空（ 水全部倒入 桶j中 ）；问经过哪几个操作后能使其中一个桶里的水量达到C。输入 ：A, B, C （ 1 = A,B,C = 100, C = MAX( A,B ) );输出 ：第一行最少操作数，接下来每行为一个操作；若无解，只输出“impossible样例输入：3 5 4样例输出：6FILL(2)POUR(2,1)DROP(1)POUR(2,1)FILL(2)POUR(2,1)分析：这个题目可以用bfs把它做出来，对于两个桶的每一种状态，我们都可对它进行六种操作，即FILL(1),FILL(2),DROP(1),DROP(2),POUR(1,2),POUR(2,1),我们可以把它的每一种状态记录下来，一层一层的往下扩展，直到找到我们要找的容量为止。不过这里有一个麻烦，就是要你输出得到容量C的过程。所以对于每一个结点，我们都得对它设置一个pre指针，使它指向其父结点，等到我们找到正确的结果之后，再沿着其父结点返回来找那条正确的路径。具体代码如下：/ 有点长，但思路简单；/ 到北大 OnlineJudge P3414 提交。/ Pots.cpp#include #include using namespace std;int iAA, iBB, iCC; / 输入的数据int InputDataAndInitialize( void ); / 输入数据并初始化 const int N = 400000; / 保存搜索树节点的队列的最大长度int iH, iT; / 队列的首尾元素的下标int iAN; / 桶 1 的状态 int iBN; / 桶 2 的状态int iPreN; / iPrej 得到节点j的节点的下标 int iOperatorN; / iOperatorj 得到节点j的操作的序号 const int M = 110;int bFlagMM=0; / bFlagab 判断1水量为a，2水量为b的情况是否出现过 int BFS( void ); / BFS 主函数 string OPERATOR10; / FILL(1), FILL(2), DROP(1), DROP(2), POUR(1,2), POUR(2,1) / 操作 0 1 2 3 4 5int bNoAnswer; / 有无解标志int OutputAnswer( void ); / 输出 int main(int argc, char* argv) InputDataAndInitialize(); BFS(); OutputAnswer(); return 0;int InputDataAndInitialize( void ) cin iAA iBB iCC; bNoAnswer = 1; iH = 0; iT = 1; iA0 = iB0 = iPre0 = 0; bFlag00 = 1; OPERATOR0 = FILL(1); OPERATOR1 = FILL(2); OPERATOR2 = DROP(1); OPERATOR3 = DROP(2); OPERATOR4 = POUR(1,2); OPERATOR5 = POUR(2,1); return 1;int BFS( void ) while( iH iT ) / 操作 0 if( (iAiHiAA)&(!bFlagiAAiBiH) ) iAiT = iAA; iBiT = iBiH; bFlagiAiTiBiT = 1; iPreiT = iH; iOperatoriT = 0; +iT; if( (iAiT-1=iCC) | (iBiT-1=iCC) ) bNoAnswer = 0; return 1; / 操作 1 if( (iBiH0)&(!bFlag0iBiH) ) iAiT = 0; iBiT = iBiH; bFlagiAiTiBiT = 1; iPreiT = iH; iOperatoriT = 2; +iT; if( (iAiT-1=iCC) | (iBiT-1=iCC) ) bNoAnswer = 0; return 1; / 操作 3 if( (iBiH0) & (!bFlagiAiH0) ) iAiT = iAiH; iBiT = 0; bFlagiAiTiBiT = 1; iPreiT = iH; iOperatoriT = 3; +iT; if( (iAiT-1=iCC) | (iBiT-1=iCC) ) bNoAnswer = 0; return 1; / 操作 4 1 倒完 if( (iAiH0) & (iBiHiBB) & (iAiH0) & (iBiH=iBB-iBiH) & (!bFlagiAiH+iBiH-iBBiBB) ) iAiT = iAiH + iBiH - iBB; iBiT = iBB; bFlagiAiTiBiT = 1; iPreiT = iH; iOperatoriT = 4; +iT; if( (iAiT-1=iCC) | (iBiT-1=iCC) ) bNoAnswer = 0; return 1; / 操作 5 2 倒完 if( (iBiH0) & (iAiHiAA) & (iBiH0) & (iAiH=iAA-iAiH) & (!bFlagiAAiBiH+iAiH-iAA) ) iAiT = iAA; iBiT = iBiH + iAiH - iAA; bFlagiAiTiBiT = 1; iPreiT = iH; iOperatoriT = 5; +iT; if( (iAiT-1=iCC) | (iBiT-1=iCC) ) bNoAnswer = 0; return 1; +iH; return 1;int OutputAnswer( void ) if( bNoAnswer ) cout impossiblen; return 1; int p, oN,to=0; for( p=iT-1; p; p=iPrep ) oto+ = iOperatorp; cout to =0; -p ) cout OPERATORop B1$A2$ - B2$规则的含义为：在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ 。例如：A$abcdB$xyz变换规则为：abc-xuud-yy-yz则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：abcd-xud-xy-xyz共进行了三次变换，使得 A$ 变换为B$。 输入格式 A$ B$A1$ B1$2$ B2$。所有字符串长度的上限为 20。 输出格式 若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出NO ANSWER! 样例输入 abcd wyzabc xuud yy yz 样例输出 3 题五 ： 聪明的打字员 ( NOI2001 ) 阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：Swap0, Swap1, Up, Down, Left, Right，为了说明这6个键的作用，我们先定义录入区的6个位置的编号，从左至右依次为1，2，3，4，5，6。下面列出每个键的作用：Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的