当前位置:   article > 正文

算法基础(Java)--回溯算法_java回溯算法

java回溯算法

1. 什么是回溯算法?

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

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

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

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

先看什么是解空间

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

再看搜索

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

for(求a1位置上的解)

for(求a2位置上的解)

for(求a3位置上的解)

......

......

for(求an位置上的解)

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号