深度优先搜索(dfs)

尽可能“深”地搜索,对于最新发现的顶点,马上进入该状态并对其进行扩展,当前状态不能扩展时进行回溯,整个过程反复进行直到找到目标状态或者遍历完了整棵状态树。

  深度优先的搜索过程正是对数据结构中的栈的操作

→每一次扩展将当前状态的所有儿子压入栈
→每一次扩展结束将当前状态从栈顶弹出
DFS的递归实现是由系统栈自动维护
因此,也可以自己手工维护一个栈来实现DFS的过程


时间复杂度

  假设每个状态可有b种扩展方式,且树的最大深度为m,那么总的时间是和b^m成正比的,因此时间复杂度为O(b^m)


空间复杂度

  只需要从状态树根节点到当前状态路径上的所有状态节点,因此仅为O(m)


代码框架:

DFS( state , depth )
	if ( state == Answer )
		output
		return
	for  ( change = 0 ; change < total ; change++)
		cur_state = doChange( state , change )
		DFS( cur_state , depth+1)
相关文章
相关标签/搜索