首页 > 代码库 > c2java 回溯，下一个排列和子集和
c2java 回溯，下一个排列和子集和
穷举:生成所有候选解，然后找出需要的解。
回溯:把解表示成向量，每个分量取自一个有限集合。从部分解开始，每次添加解的一个分量，然后判断如果有可能扩展成完整解则递归下去，否则换成下一个。可以看做是隐式图上的深度优先搜索。
回溯/穷举的复杂度，最坏时和后者一样，通常情形因为不必遍历所有子节点，还是比较快的。
回溯框架:
backtrack(a[], k)
if a[0,...,k] is a solution
output;
else
k = k + 1;
for c: the i-th of candidates
a[k] = c;
bactrack(a, k);
剪枝
把快死的或者齐心怪状的树枝剪掉。对于搜索树来说，就是把候选范围缩小。
例1，八皇后问题: 把八个皇后放在8x8棋盘上，使得任意两个不在同一行或者同一列或者对角线上。
直接以棋盘格为编号，解空间为2^64, 以皇后为编号，64^8, 不同行，8^8, 不同列，8!。
如果在生成排列后再做检测，这就是穷举；如果在for分支前先做检测，这就是回溯剪枝了。
例2，子集和问题:从一个正整数集合中找一个子集，使得其元素和为给定的数d。
记当前部分和为s。 如果选择e, s + e > d 或者s + 剩下所有元素 < d，该分支肯定无解，应该剪掉。
回溯:把解表示成向量，每个分量取自一个有限集合。从部分解开始，每次添加解的一个分量，然后判断如果有可能扩展成完整解则递归下去，否则换成下一个。可以看做是隐式图上的深度优先搜索。
回溯/穷举的复杂度，最坏时和后者一样，通常情形因为不必遍历所有子节点，还是比较快的。
回溯框架:
backtrack(a[], k)
if a[0,...,k] is a solution
output;
else
k = k + 1;
for c: the i-th of candidates
a[k] = c;
bactrack(a, k);
剪枝
把快死的或者齐心怪状的树枝剪掉。对于搜索树来说，就是把候选范围缩小。
例1，八皇后问题: 把八个皇后放在8x8棋盘上，使得任意两个不在同一行或者同一列或者对角线上。
直接以棋盘格为编号，解空间为2^64, 以皇后为编号，64^8, 不同行，8^8, 不同列，8!。
如果在生成排列后再做检测，这就是穷举；如果在for分支前先做检测，这就是回溯剪枝了。
例2，子集和问题:从一个正整数集合中找一个子集，使得其元素和为给定的数d。
记当前部分和为s。 如果选择e, s + e > d 或者s + 剩下所有元素 < d，该分支肯定无解，应该剪掉。
只有我们在验证所有叶子都可达确认算法正确后，才可用剪枝。一开始上剪枝可能导致结果不正确，比如下面的求连续可重复子集和sumBT()。
代码：
<script src="https://code.csdn.net/snippets/365871.js" type="text/javascript"></script>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。