算法基础（Java）--回溯算法_java回溯算法

作者：代码探险家 | 2024-08-15 00:44:01

踩

java回溯算法

1. 什么是回溯算法？

回溯法是一种系统搜索问题解空间的方法。为了实现回溯，需要给问题定义一个解空间。

说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索。

而往往所谓的dfs，bfs都是在图或者树这种数据结构上的搜索。

根据定义来看，要实现回溯，需要两点1搜索，2解空间

先看什么是解空间。

就是形如数组的一个向量[a1,a2,…,an]。这个向量的每个元素都是问题的部分解，只有当这个数组的每一个元素都填满(得到全部解)的时候，才表明这个问题得到了解答。

再看搜索。

最简单的就是for循环，上面的向量有n个维度，因此就是n个for循环。

for(求a1位置上的解)

for(求a2位置上的解)

for(求a3位置上的解)

......

for(求an位置上的解)

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】