搜索路径

来自计算思维百科
跳转至: 导航搜索
搜索路径1.png

为了迎接春节,某公园希望装饰一条有中国春节特色的道路,但该园的预算只够装饰一条长为150米的路径。于是,管理人画出园内几个游览点,希望以v1为起点,让你来帮他找找是否存在长度为150米的路径。

解决方案

方案一—深度优先搜索

从v1开始搜索,搜索过程如下:

搜索路径2.png

从v1相邻的节点v2继续:

搜索路径3.png

v1->v2路径长度为75,继续搜索v2相邻节点v3:

搜索路径4.png

v1->v2->v3路径长度为136,v3没有未访问的相邻节点了,因此退回上一层v2:

搜索路径5.png

v2没有未访问的相邻节点了,因此退回上一层v1:

搜索路径6.png

v1下一节点为v4,继续:

搜索路径7.png

v1->v4路径长度为55,继续搜索v4相邻节点v5:

搜索路径8.png

v1->v4->v5的路径长度为110,继续搜索v5相邻节点v6:

搜索路径9.png

此时,v1->v4->v5->v6的路径长度为150,搜索结束。

运用的计算思维

该解决方案中采用的深度优先搜索法实际上是回溯法的体现,属于计算思维中的递归思想。

方案二—分治法

已知两两节点连接的路径共有7条,我们可以把人员召集起来分成7组,每组人员负责测量一段路径。测量后再以v1为起点进行加法计算,找出是否存在长度为150米的路径。

各组测量结果综合如下图,因此,通过简单计算可得存在长度为150米的路径:v1->v4->v5->v6

搜索路径10.png

运用的计算思维

该解决方案中的分治法体现了计算思维中分解的思想。采用以空间换取时间的方法,可以提高解决方案的效率,但是这将耗损更多的人力资源。