数据结构和算法--回溯法
2022/5/27 1:21:22
本文主要是介绍数据结构和算法--回溯法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
回溯算法
定义:回溯算法,又称“试探法”。解决问题时, 每一步都是尝试态度,如果发现并不是好的,
或者这么走下去很定达不到目标,立刻返回重新操作, 这种走不通就回退的方法为回溯算法。
回溯 vs 递归
很多人认为 回溯 和 递归 是一样的, 其实不然。回归中可以看到递归的影子
但是两者是有区别的。
回溯: 从问题本身出发,寻找可能实现的所有可能情况。和
穷举法的思想相近,不同于穷举法是将所有的情况列举出来以后在一一筛选,而回溯法是在列举
过程中,如果发现当前情况不对,就停止后续工作,返回上一步,进行新的尝试。
递归: 是从问题的结果出发,例如求n!的结果,就需要知道
n(n-1)! 的结果,而要想知道 (n-1)! 结果,就需要提前知道 (n-1)(n-2)!。这样不断地向
自己提问,不断地调用自己的思想就是递归。
两者联系: 回溯可以用递归思想实现
实现过程:
使用回溯法解决问题的过程,实际上是建立一棵“状态树”的过程。例如,在解决列举集合{1,2,3}
所有子集的问题中,对于每个元素,都有两种状态,取还是舍,所以构建的状态树为:
回溯算法的求解过程实质上是先序遍历“状态树”的过程。树中每一个叶子结点,都有可能是问题的
答案。图 1 中的状态树是满二叉树,得到的叶子结点全部都是问题的解。
在某些情况下,回溯算法解决问题的过程中创建的状态树并不都是满二叉树,因为在试探的过程中,
有时会发现此种情况下,再往下进行没有意义,所以会放弃这条死路,回溯到上一步。在树中的体现,
就是在树的最后一层不是满的,即不是满二叉树,需要自己判断哪些叶子结点代表的是正确的结果。
这篇关于数据结构和算法--回溯法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?