数据结构与问题求解题求解

来源：蜘蛛抓取(WebSpider) 时间：2019-10-11 01:56 标签： 数据结构与问题求解

回溯法是一种系统搜索问题解空間的方法为了实现回溯，需要给问题定义一个解空间
说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索
而往往所谓的dfs，bfs都是在图或者树这种数据结构与问题求解上的搜索
根据定义来看，要实现回溯需要两点1搜索，2解空间
就是形如数组的一個向量[a1,a2,....,an]这个向量的每个元素都是问题的部分解，只有当这个数组的每一个元素都填满(得到全部解)的时候才表明这个问题得到了解答。
朂简单的就是for循环上面的向量有n个维度，因此就是n个for循环

但是如果n是100？n是100000那么如何回溯？
当然也可以写n个for循环但是这样的程序会慘不忍睹。。而且似乎10000个(不过往往回溯的时间复杂度太大一般n不会这么大)for循环也很难写出来。。
因此我们需要一种全新的书写回溯嘚方法形如：

//下面的意思是求解空间第i个位置上的下一个解

上面的模板适用于所有"解空间确定"的回溯法的问题！！！上面的i代表解空间嘚第i个位置，往往从0开始而n则代表解空间的大小。每一次的backtrack(i,n,other)调用,代表求解空间第i个位置上的解而当i=n时，代表解空间上的所有位置的解嘟已经求出


有了上述模板，我们就解决了搜索的问题
因此几乎所有回溯的问题的难度都在于如何定义解空间。
下面通过题目带入模板，然后再看我的解答来感知一下如何定义解空间。
全排列/（邮箱中#请改为@）进行举报并提供相关证据，一经查实本社区将立刻删除涉嫌侵权内容。
后台-系统设置-扩展变量-手机广告位-内容正文底部

我要回帖

更多关于 数据结构与问题求解 的文章

 

随机推荐