春天里,百花香...
回溯法有“通用的解题法“之称。用它可以系统的搜索一个问题的所有解或任一解。会所法是一个既带有系统性又带有跳跃性的搜索算法,他在包含问题的所有解的解空间树中,按照深度有限的策略,从根节点出发搜索解空间树,算法搜索至解空间树的任一节点时,总是先判断该节点是否肯定不包含问题的解。如果肯定不包含,则跳过对该节点为根的子树的系统搜索,逐层向其祖先节点回溯,否则进入该子树,继续按照深度优先的策略进行搜索。回溯法在用来求问题的任一接时,只要搜索到问题的一个解就可以结束。 这种深度优先的解的算法称为回溯法,它适合于解一些组合数较大的问题。
用回溯法解n皇后问题时,可以用一棵完全n叉树来表示其解空间。剪去不满足行列和斜线攻击的子树后,剩下的就是问题的解答。
代码:
posted on 2008-07-08 11:38 sitinspring 阅读(764) 评论(0) 编辑 收藏 所属分类: 算法数据结构
Powered by: BlogJava Copyright © sitinspring