宽度优先搜索

1、宽度优先搜索应用实例朱全民宽度优先遍历算法框架 从某个未被访问的顶点从某个未被访问的顶点v出发出发,依次访问依次访问v的各个未曾访问过的各个未曾访问过的邻接点的邻接点.然后分别从这些邻接点出发广度优先搜索遍历然后分别从这些邻接点出发广度优先搜索遍历,直直到所有已被访问的邻接点都被访问到到所有已被访问的邻接点都被访问到. PROC bfs(v);Visite(v); vistedv:=true;Iniqueue(q); enqueue(q,v);While not empty(q) do v:=dlqueue(q);w:=FIRSTADJ(v);While w0 do if not visite

2、dw then visite(w);visitedw:=true; enqueue(q,w) w:=NEXTADJ(v,w); ENDP神经网络神经网络(NOIP2003-1) 在兰兰的模型中，神经网络就是一张有向图，图中的节点在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：图是一个神经元的例子： 图中，图中，X1X3X1X3是信息输入渠道，是信息输入渠道，Y1Y1Y2Y2是信息输出渠道，是信息输出渠道，C1C1表示神经元目前的状态，表示神经元目前的状态，UiUi是阈值，

3、可视为神经元的一个是阈值，可视为神经元的一个内在参数。内在参数。 神经元按一定的顺序排列，构成整个神经网络。在兰兰神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。输出信息，只从上一层神经元接受信息。 神经网络神经网络兰兰规定，兰兰规定，C Ci i服从公式：（其中服从公式：（其中n n是网络中所有神经元的数目）是网络中所有神经元的数目）E) i , j

4、(ijjiiUCWC 公式中的公式中的WjiWji（可能为负值）表示连接（可能为负值）表示连接j j号神经元和号神经元和 i i号神经号神经元的边的权值。当元的边的权值。当 CiCi大于大于0 0时，该神经元处于兴奋状态，否时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为向其他神经元传送信号，信号的强度为CiCi。 如此在输入层如此在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当

5、前输入层神经元的行运作。现在，给定一个神经网络，及当前输入层神经元的状态（状态（CiCi），要求你的程序运算出最后网络输出层的状态。），要求你的程序运算出最后网络输出层的状态。 【输入格式】【输入格式】 第一行是两个整数第一行是两个整数n n（1n201n20）和）和p p。接下来。接下来n n行，每行两个行，每行两个整数，第整数，第i i1 1行是神经元行是神经元i i最初状态和其阈值（最初状态和其阈值（UiUi），非输入），非输入层的神经元开始时状态必然为层的神经元开始时状态必然为0 0。再下面。再下面P P行，每行由两个整行，每行由两个整数数i i，j j及一个整数及一个整数WijWij

6、，表示连接神经元，表示连接神经元i i、j j的边权值为的边权值为WijWij。【输出格式】【输出格式】 输出包含若干行，每行有两个整数，分别对应一个神经元的输出包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。编号，及其最后的状态，两个整数间以空格分隔。仅输出最仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！序输出！ 若输出层的神经元最后状态均为若输出层的神经元最后状态均为 0 0，则输出，则输出 NULLNULL。分析 理解问题的第一步就是认真理解问题的第一步就是认真“读题读题

7、”。那么我们先来看。那么我们先来看一看这个题目涉及的问题。研究一下题目中所给的图的一看这个题目涉及的问题。研究一下题目中所给的图的一些性质，可以发现如下特点：一些性质，可以发现如下特点：1 1图中所有的节点都有一个确定的等级，我们记作图中所有的节点都有一个确定的等级，我们记作Level(i)Level(i)2 2图中所有的边都是有向的，并且从图中所有的边都是有向的，并且从LevelLevel值为值为i-1i-1的节的节点指向点指向LevelLevel值为值为i i的节点的节点 我们不妨将其抽象为我们不妨将其抽象为“阶段图阶段图”。 更一般地，我们可以发现所有的阶段图都是有向无环的，更一般地，我

8、们可以发现所有的阶段图都是有向无环的，这样我们可以通过拓扑排序来得到期望的处理节点的顺这样我们可以通过拓扑排序来得到期望的处理节点的顺序。序。可行算法 由于阶段图的性质使得该图的所有边所连接节点的等级由于阶段图的性质使得该图的所有边所连接节点的等级都是相邻的，因此就可以设计出一个基于宽度优先搜索都是相邻的，因此就可以设计出一个基于宽度优先搜索（即（即BFSBFS）的算法：）的算法：1 1初始时将所有输入层的节点放入队列；初始时将所有输入层的节点放入队列；2 2取出队列中的一个元素，不重复地扩展并处理该节点所发出的取出队列中的一个元素，不重复地扩展并处理该节点所发出的边的目标节点；边的目标节点；

9、3 3如果队列非空，则转向如果队列非空，则转向2 2；4 4输出输出层中所有满足条件的节点。输出输出层中所有满足条件的节点。 但是由于本题在问题描述中并没有明确的给出判断一个但是由于本题在问题描述中并没有明确的给出判断一个节点是否是输入节点，因此需要在算法进行的过程当中节点是否是输入节点，因此需要在算法进行的过程当中额外地考虑一些边界情况的数据（这个过程即便是真实额外地考虑一些边界情况的数据（这个过程即便是真实数据没有这样出也是要有的），下面给出的更一般的算数据没有这样出也是要有的），下面给出的更一般的算法可能会更好的跳过这些边界情况。法可能会更好的跳过这些边界情况。1 1对原图中所有的节点进

10、行一次拓扑排序；对原图中所有的节点进行一次拓扑排序；2 2按照拓扑顺序处理每一个节点；按照拓扑顺序处理每一个节点；3 3输出输出层中所有满足条件的节点。输出输出层中所有满足条件的节点。聪明的打字员聪明的打字员(nOI2001第一试第三题第一试第三题)阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定阿兰是某机密部门的打字员，她现在接到一个任务：需要在一天之内输入几百个长度固定为为6 6的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。的密码。当然，她希望输入的过程中敲击键盘的总次数越少越好。不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘

11、上没有数字不幸的是，出于保密的需要，该部门用于输入密码的键盘是特殊设计的，键盘上没有数字键，而只有以下六个键：键，而只有以下六个键：Swap0, Swap1, Up, Down, Left, RightSwap0, Swap1, Up, Down, Left, Right，为了说明这，为了说明这6 6个键的作个键的作用，我们先定义录入区的用，我们先定义录入区的6 6个位置的编号，从左至右依次为个位置的编号，从左至右依次为1 1，2 2，3 3，4 4，5 5，6 6。下面列出。下面列出每个键的作用：每个键的作用：Swap0Swap0：按：按Swap0Swap0，光标位置不变，将光标所在位置的数

12、字与录入区的，光标位置不变，将光标所在位置的数字与录入区的1 1号位置的数字（左号位置的数字（左起第一个数字）交换。如果光标已经处在录入区的起第一个数字）交换。如果光标已经处在录入区的1 1号位置，则按号位置，则按Swap0Swap0键之后，录入区的键之后，录入区的数字不变；数字不变；Swap1Swap1：按：按Swap1Swap1，光标位置不变，将光标所在位置的数字与录入区的，光标位置不变，将光标所在位置的数字与录入区的6 6号位置的数字（左号位置的数字（左起第六个数字）交换。如果光标已经处在录入区的起第六个数字）交换。如果光标已经处在录入区的6 6号位置，则按号位置，则按Swap1Swap

13、1键之后，录入区的键之后，录入区的数字不变；数字不变；UpUp：按：按UpUp，光标位置不变，将光标所在位置的数字加，光标位置不变，将光标所在位置的数字加1 1（除非该数字是（除非该数字是9 9）。例如，如果光）。例如，如果光标所在位置的数字为标所在位置的数字为2 2，按，按UpUp之后，该处的数字变为之后，该处的数字变为3 3；如果该处数字为；如果该处数字为9 9，则按，则按UpUp之后，之后，数字不变，光标位置也不变；数字不变，光标位置也不变；DownDown：按：按DownDown，光标位置不变，将光标所在位置的数字减，光标位置不变，将光标所在位置的数字减1 1（除非该数字是（除非该数字

14、是0 0），如果该处），如果该处数字为数字为0 0，则按，则按DownDown之后，数字不变，光标位置也不变；之后，数字不变，光标位置也不变；LeftLeft：按：按LeftLeft，光标左移一个位置，如果光标已经在录入区的，光标左移一个位置，如果光标已经在录入区的1 1号位置（左起第一个位置）号位置（左起第一个位置）上，则光标不动；上，则光标不动；RightRight：按：按RightRight，光标右移一个位置，如果光标已经在录入区的，光标右移一个位置，如果光标已经在录入区的6 6号位置（左起第六个位号位置（左起第六个位置）上，则光标不动。置）上，则光标不动。当然，为了使这样的键盘发挥作用

15、，每次录入密码之前，录入区总会随机出现一个长度为当然，为了使这样的键盘发挥作用，每次录入密码之前，录入区总会随机出现一个长度为6 6的初始密码，而且光标固定出现在的初始密码，而且光标固定出现在1 1号位置上。当巧妙地使用上述六个特殊键之后，可以号位置上。当巧妙地使用上述六个特殊键之后，可以得到目标密码，这时光标允许停在任何一个位置。得到目标密码，这时光标允许停在任何一个位置。现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。现在，阿兰需要你的帮助，编写一个程序，求出录入一个密码需要的最少的击键次数。 产生式规则设当前状态为设当前状态为(S,index)，下一个状态为，

16、下一个状态为(S,index) Swap0 Swap0：if index1 thenif index1 then S S:=S;S:=S;S1:=Sindex;S1:=Sindex;Sindex:=S1;Indexindex:=S1;Index:=index;:=index; Swap1 Swap1：if index6 thenif index6 then S S:=S;S:=S;S6:=Sindex;S6:=Sindex;Sindex:=S6;Indexindex:=S6;Index:=index;:=index; Up Up：if Sindex9 then if Sindex9 then

17、S S:=S;S:=S;Sindex:=Sindex:=Sindex+1;Indexindex+1;Index:=index;:=index; Down Down：if Sindex0 then Sif Sindex0 then S:=S;S:=S;Sindex:=Sindex:=Sindex-index-1;Index1;Index:=index; :=index; Left Left： if index0 then Sif index0 then S:=S; Index:=S; Index:=index-1;:=index-1; Right Right：if index6 then Sif

18、 index6 then S:=S; Index:=S; Index:=index+1;:=index+1;数据结构的处理如果我们用（如果我们用（S,index）表示问题中的一个状态，）表示问题中的一个状态，S为密码，为密码，index表表示光标位置。那么，（示光标位置。那么，（Source，1）为问题的初始状态，（）为问题的初始状态，（Target，pos）为问题的目标状态。其中）为问题的目标状态。其中pos任意。那么综合数据库中可能存任意。那么综合数据库中可能存在的节点数为：在的节点数为：6*106。 const maxl = 6000000; type statetype = array

19、1 . 6 of shortint; Nodetype = record state : statetype; 密码密码 point , step : shortint; 光标位置，按键次数光标位置，按键次数 end; var q : array0 . maxl of Nodetype; 队列队列 app : array1.6,0.9,0.9,0.9,0.9,0.9,0.9 of boolean; 判重数组判重数组 final : statetype; 目标状态目标状态 算法选择 closed := 0; open := 1; q1.point := 1; fillchar(app , siz

20、eof(app) , false); while true do begin closed := closed mod maxl + 1; with qclosed do begin if comparebyte(state , final , 6) = 0 then 打印输出；打印输出； 如果是目标的话如果是目标的话 调用调用6条规则扩展出条规则扩展出state新节点；新节点； if not apppoint,state1,state2,state3,state4,state5,state6 判重判重 then begin open := open mod maxl + 1; qopen.s

21、tate := state; qopen.step := step + 1; qopen.point := point; apppoint,state1,state2,state3,state4,state5,state6:= true; end;Amazing Robots: IOI2003已知条件： 迷宫 i（i=1,2） （每个不会大于20*20） 守卫 Gi（0=Gi=10） （守卫循环移动进行执勤） （守卫巡逻的方格数（2.4）求： 两个机器人都离开迷宫所用的最少指令数目 和离开制指令序列（10000 步以内）。每一步可以发出的命令可以是N, E, S, W中的一种，有4种选择。对每

22、一步具体发出哪个命令，直接搜索。假设最后结果是T。（也就是最少出宫时间）时间复杂度是O(4T)这种方法时间复杂度太高，绝对不可行!5*4和4*4的迷宫第一个机器人的位置是(2,2)第二个机器人的位置是(3,2)当前时间是0。状态(2,2),(3,2),0)状态表示：状态表示： （第一个机器人位置，第二个机器认位置，时间）（第一个机器人位置，第二个机器认位置，时间）E(2,2),(3,2),0)(2,3),(3,3),1)时间已知，则所有Guard的位置可知。Guard、Robot的位置均已知，所以状态可以转移0时刻1时刻2时刻3时刻0时刻和2时刻是一样的1时刻和3时刻是一样的。稍加分析：此Gu

23、ard循环以2为周期循环。状态转移，需要的信息是：Robot位置，Guard位置。Position of Robot1, 2是的作用就是记录Robot位置。Time的作用就是为了计算Guard的位置状态：(position of Robot1, position of Robot2, Time)Time=10000，这是状态数过多的罪魁祸首！题目说：Guard巡逻经过的格子数只可能是2, 3, 4。也就是说机器人巡逻周期只能是2, 4, 6。2, 4, 6=12，所以第0时刻、12时刻、24时刻Guard的状态完全相同。12可以看作Guard的周期。Time只要记录当前是第几个周期。因为周期确

24、定了，Guard的位置也完全确定了！ 0=Time=11状态数状态数(n*n)*(n*n)*12=12n4。用用BFS算法，标志数组判重。算法，标志数组判重。时间复杂度时间复杂度O(12n4)。n=20完全可以承受完全可以承受 -街道赛跑街道赛跑 下图给出了一个沿街道赛跑的路线。图中有许多点，给下图给出了一个沿街道赛跑的路线。图中有许多点，给以标号以标号0，1，N(此图中此图中N=9)，点之间可以用含箭，点之间可以用含箭头的线相连。标号为头的线相连。标号为0的点是起点；标号为的点是起点；标号为N的点为终点。的点为终点。含箭头的线表示单向通行的街道。运动员沿箭头所指方含箭头的线表示单向通行的街道

25、。运动员沿箭头所指方向从一个点跑向另一个点；在每一个点上，运动员可以向从一个点跑向另一个点；在每一个点上，运动员可以选择任何一个箭头选择任何一个箭头(向外的向外的)继续向前跑。继续向前跑。一个完整路线具有如下特点：一个完整路线具有如下特点： 1路线中每一点都可从出发点到达；路线中每一点都可从出发点到达； 2路线中每一点都可到达终点；路线中每一点都可到达终点； 3终点处没有向外的箭头。终点处没有向外的箭头。 运动员要到达终点，但不要求路线运动员要到达终点，但不要求路线(图图)中的每一点都经过。中的每一点都经过。但是路线但是路线(图图)中的某些点是必经之点。上图的例子中，必经中的某些点是必经之点。

26、上图的例子中，必经之点是：之点是：0，3，6，9。 任务任务A: 题目给出一个完整路线（图），请编程找出所有必题目给出一个完整路线（图），请编程找出所有必经之点。请注意，输出必经之点时，应不包括起点和终点。经之点。请注意，输出必经之点时，应不包括起点和终点。 任务任务B: 假定赛跑必须在相邻的假定赛跑必须在相邻的2天来举行。因此，要把原来天来举行。因此，要把原来给定的完整路线（图）分成两个子路线（图）。第给定的完整路线（图）分成两个子路线（图）。第1天从点天从点0出发，结束于出发，结束于“分裂点分裂点”。第。第2天从天从“分裂点分裂点”出发，结出发，结束于点束于点N。 题目给出一个完整路线（图

27、）题目给出一个完整路线（图）C，请编程输出所有可能的，请编程输出所有可能的“分裂点分裂点”（任务（任务B）。）。“分裂点分裂点”S一定不是起点或终点。一定不是起点或终点。C可被可被S分成两个完整的子路线：这两个子路线没有公共的分成两个完整的子路线：这两个子路线没有公共的箭头线，并且箭头线，并且S是这两个子路线的唯一公共点。在上的例子是这两个子路线的唯一公共点。在上的例子中，仅点中，仅点3是是“分裂点分裂点”。 输入数据：输入数据：输入数据描述一个完整路线（最多输入数据描述一个完整路线（最多50个点，最多个点，最多100个箭头），共个箭头），共n1行。前面行。前面n行描述箭头的终行描述箭头的终点

28、，其中第点，其中第i行中的每一个数字表示从点行中的每一个数字表示从点i（1in）出发的每一个箭头的终点，以出发的每一个箭头的终点，以2作为该行的结束。作为该行的结束。最后一行（第最后一行（第n+1行）中有一个数字行）中有一个数字1，表示输，表示输入结束。入结束。 输出数据：输出数据：输出两行数据，第输出两行数据，第1行表示必经点（子任务行表示必经点（子任务A）首先是必经点的总数，其后是必经点的标号，标首先是必经点的总数，其后是必经点的标号，标号的顺序无关紧要。第号的顺序无关紧要。第2行表示行表示“分裂点分裂点”：首先：首先是分裂点的总数，其后是分裂点的标号，标号出是分裂点的总数，其后是分裂点的

29、标号，标号出现的先后顺序无关紧要（子任务现的先后顺序无关紧要（子任务B）。）。分析 必经点必经点:是指运动员从起点是指运动员从起点0出发，沿箭头方向跑，无论走哪条路线，出发，沿箭头方向跑，无论走哪条路线，都经由该点到达终点都经由该点到达终点N。所有这些点组成必经点的集合。反。所有这些点组成必经点的集合。反之，在完整路线中去除必经点集合中的任一个点，无论运动之，在完整路线中去除必经点集合中的任一个点，无论运动员选择哪条路线跑，都不可能从起点员选择哪条路线跑，都不可能从起点0跑至终点跑至终点N。 分裂点分裂点: 某点是必经点；某点是必经点； 在完整路线中去除这个必经点后，由起点出发的运动员无在完整

30、路线中去除这个必经点后，由起点出发的运动员无论如何也不会跑到由这个必经点出发的任一箭头的终点；论如何也不会跑到由这个必经点出发的任一箭头的终点； 完整路线中去除这个必经点后的所有点，分成两个互为独完整路线中去除这个必经点后的所有点，分成两个互为独立的集合立的集合: 可从出发点可从出发点0到达。这些点组成子路径到达。这些点组成子路径1； 无法从出发点无法从出发点0到达。这些点组成子路径到达。这些点组成子路径2； 两个集合中的点之间，无任何箭头相连；两个集合中的点之间，无任何箭头相连；思路 从点从点0开始，按逐层搜索的方法对删除当前判别点后的路开始，按逐层搜索的方法对删除当前判别点后的路线重复进行访问，直至找不到可访问的点为止。广度搜线重复进行访问，直至找不到可