算法问题的暴力解决及替代方案

暴力搜索与回溯概念是不相同的,在回溯算法中,大量的解决方案并没有被列举而直接被丢弃(例如上文提到的“八皇后问题”的解决方案)。用于在表中查找一个项目,也就是说顺序地检查表中所有条目的暴力方法被称为线性搜索。

暴力搜索的替代方法编辑
对于各不同门类的知识,存在很多的搜索方法或元启发式算法能求得解决方案,启发式方法也可用于提前截断搜索的部分。这样的一个例子就是搜索游戏树的最小化原则,其在搜索的早期消除了许多子树。在某些领域,例如语言分析中,一些技术例如图解法可以利用问题中的约束条件将指数复杂度的问题简化到多项式复杂度的问题。在很多情况下,如在约束满足问题中,通过约束传播可以极大地减小搜索空间,这一点在约束编程语言中被高效实现了。问题的搜索空间可以通过用简化版本代替完整的问题来实现。例如,在计算机象棋中,并不是计算游戏剩余部分所有移动可能的极大极小树,而是计算有限范围内的极大极小可能性的树,即由完整树以特定的移动步数修剪得到,而且这个树须和静态评估函数近似。

上一篇:数据集

下一篇:十大算法【转】

本文转自:https://baike.baidu.com/item/%E6%9A%B4%E5%8A%9B%E6%90%9C%E7%B4%A2/7829649
新加评论 评论标题: