深度优先搜索在编程中的应用学习任务单-2025-2026学年浙教版高中信息技术一轮复习

| 6页
| 541人阅读
| 0人下载
普通

学科网 zxxk.com学科网 zxxk.com

信息技术一轮复习拓展——深度优先搜索在编程中的应用

班级(        )姓名(        )学号(        )

 

【情景展示】战争情报的加密与解密。在某次战争中,甲方欲传达几组长度不等的仅由数字0到9构成的情报,为防止情报泄露给乙方,甲方采用了一种加密方式:针对每一位数字,若该数字为奇数,则把该位数字编译成1;若该数字为偶数,则把该为数字编译成0,例如,数字“29085”编译成“01001”。在甲方将加密好的情报传递给某一较远基地时,由于突发情况,情报及加密方法泄露给了乙方,现乙方想根据该加密方式对情报进行解密,并列举出所有可能性。现要编写一段Python代码,辅助完成情报的加密工作和解密工作。

 

【课前热身】下面给出的代码是甲方为完成情报加密工作所使用的代码。请在横线处填写合适的代码。

 

sm=input('请输入需要加密的情报:')

sd=''

for i in range(len(sm)):

    if           ▲          :

        sd=sd+'0'

    else:

        sd=sd+'1'

print(sd)

 

【课上探索】【方案构思】乙方想根据该加密方式对情报进行解密,并列举出所有可能性。他们应该编写什么样的代码快速高效地列举所有可能性?尝试用已有的知识帮助他们构思几个方案。

                                                                     

                                                                     

                                                                     

(提示:可以考虑枚举、解析等方式提供多样化的方案)

 

【经验运用】某小组尝试用枚举的方式编写代码,其编写的完整代码如下。

s=input('请输入需要解密的情报:')

list1,list2=[],[]

for i in range(len(s)):

    if s[i]=='1':

        x=1

    elif s[i]=='0':

        x=0

    for m in range(1,5**len(s)+1,1):

        if m%(5**(len(s)-i-1))==0:

            list2.append(x)

            x=(x+2)%10

        else:page number 0

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


学科网 zxxk.com学科网 zxxk.com

            list2.append(x)

    list1.append(list2)

    list2=[]

for n in range(len(list1[0])):

    ans=''

    for m in range(len(list1)):

        ans=ans+str(list1[m][n])

print(ans)

 阅读上述代码,讲讲这段代码背后的运行逻辑。

                                                                     

                                                                     

                                                                     

 

【回顾思考】仔细阅读代码,思考上述代码是否存在一定的缺陷。如有,倾泻在下面的横线上。

                                                                     

                                                                     

                                                                     

如果要修改上面的代码,你觉得可以从哪些方面入手,进行一定程度的修改?

                                                                     

                                                                     

                                                                     

 

【创新探索】在进行研究时,小组意外了解到“深度优先搜索”和“宽度优先搜索”概念。

资料:深度优先搜索

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止,然后返回到某一个HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。

事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。

图举例说明之:下图是一个无向图,如果我们从A点发起深度优先搜索(以下的访问次序并不是唯一的,第二个点既可以是B也可以是C、D),则我们可能得到如下的一个访问过程:A->B->E(没有路,回溯到A)->C->F->H->G->D(没有路,最终回溯到A,A也没有未访问的相邻节点,本次搜索结束)。

图简要说明深度优先搜索的特点:每次深度优先搜索的结果必然是图的一个连通分量。深度优先搜索可以从多点发起,如果将每个节page number 1

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


学科网 zxxk.com学科网 zxxk.com

点在深度优先搜索过程中的“结束时间”排序(具体做法是创建一个list,然后在每个节点的相邻节点都已被访问的情况下,将该节点加入list结尾,然后逆转整个链表),则我们可以得到所谓的“拓扑排序”,即topological sort。

深度优先遍历图的方法是,从图中某顶点v出发:

(1)访问顶点v;

(2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

(3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。

资料:宽度优先搜索

宽度优先搜索算法(又称广度优先搜索)是最简便的图论搜索算法之一,这一算法也是很多重要的图论算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。一般可以用于边的权值相等的最短路搜索。

BFS,其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里,其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中(例如队列或是链表),而被检验过的节点则被放置在被称为 closed 的容器中。

已知图G=(V,E)和一个源顶点s,宽度优先搜索以一种系统的方式探寻G的边,从而“发现”s所能到达的所有顶点,并计算s到所有这些顶点的距离(最少边数),该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v,宽度优先树中从s到v的路径对应于图G中从s到v的最短路径,即包含最小边数的路径。该算法对有向图和无向图同样适用。

之所以称之为宽度优先算法,是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展,就是说,算法首先搜索和s距离为k的所有顶点,然后再去搜索和S距离为k+l的其他顶点。

为了保持搜索的轨迹,宽度优先搜索为每个顶点着色:白色、灰色或黑色。算法开始前所有顶点都是白色,随着搜索的进行,各顶点会逐渐变成灰色,然后成为黑色。在搜索中第一次碰到一顶点时,我们说该顶点被发现,此时该顶点变为非白色顶点。因此,灰色和黑色顶点都已被发现,但是,宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色,那么顶点v要么是灰色,要么是黑色,就是说,所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接,它们代表着已找到和未找到顶点之间的边界。

在宽度优先搜索过程中建立了一棵宽度优先树,起始时只包含根节点,即源顶点s.在扫描已发现顶点u的邻接表的过程中每发现一个白色顶点v,该顶点v及边(u,v)就被添加到树中。在宽度优先树中,我们称结点u 是结点v的先辈或父page number 2

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。