深度优先搜索法②的名词解释

【深度优先搜索法②名词解释如下】

深度优先搜索法名词解释：
当搜索总是沿着从父节点到子节点的方向不断进行,直到无路可走时,才返回,这样的搜索方式叫做深度优先搜索法。如果从节点P有可能到达节点C,则P叫做C的一个父节点,而C叫做P的一个子节点。如图所示,深度优先搜索,除搜索失败(即搜索不到目标)而要求返回来搜索原先被搁置的其他节点之外,在每一级只检查一个节点。这种搜索方法体现了优先向深度发展的趋势,所以这种深度优先搜索法又称为纵向优先搜索法。这里需要提醒注意的是,深度优先搜索是一个冒失而危险的方法。设想有更复杂的、树形结构层次多得多的树,在这样的结构中进行深度优先搜索过程,很容易出现滑过F节点的层次,而在穷尽下面的树形结构中进行搜索,这会浪费很多时间。对于这种树结构此方法虽然容易实现,却得到了最坏的可能路径。当对复杂、多层次的树形结构进行深度优先搜索时,如果在离初始状态相当远的一段距离内搜索不到目标,我们就希望沿原路返回,去试探其他一些路径,而不继续向前搜索,以致离初始状态太远。在这种情况下,人们常常给搜索树规定一个深度界限,或称最大深度。在考察一个节点时,如果其深度等于深度界限,就可不再向深度搜索,而从原路返回,去探索其他路径。这样有时就可节约时间,尽快搜索到目标。目前这一方法是作为搜索法的基本方法之一而得到广泛应用。

相关阅读：