计算机算法设计与分析第一章复习思维导图
计算机设计与分析第二章思维导图知识点总结
计算机设计与分析第三章思维导图知识点总结
计算机设计与分析第四章思维导图知识点总结
计算机设计与分析第五章思维导图知识点的总结(初稿) ) ) ) ) ) ) ) ) )。
计算机设计与分析第6章思维导图知识点的总结(初稿) ) ) ) ) ) ) ) ) ) ) ) ) ) )。
计算机设计与分析第七章思维导图知识点总结(初稿) )。
思维导图
回溯法的概念回溯法(搜索和回溯法)是一种择优搜索法，也叫启发式法，根据择优条件进行前瞻性搜索，实现目标。 但是，在探索了某一步的时候，如果原来的选择不优秀或者没有达到目标，就返回一步重新选择。 这样，如果不顺利就返回的技术是回溯法，将满足有回溯条件的状态的点称为“回溯点”。
溯源法问题的算法框架溯源算法的两种形式(1)递归
)2)迭代
解空间的组织形态(1)子集树：
给定的问题是从n个要素的集合s中找到满足某一性质的部分集合时，对应的解空间是部分集合树
)2)林荫道：
给定的问题是决定n个要素满足某一性质的数组时，对应的解空间树被称为数组树
回溯算法要点：定义“1”问题的解空间
)确定易搜索解空间结构
)3)优先深度搜索解空间，在搜索中应用剪枝函数以减少搜索规模
回溯算法的步骤： (1)确定解向量
)2)确定解空间树
)3)深度优先搜索遍历解空间树
)4)剪枝
回溯法与深度优先搜索的比较回溯：
查找所需节点(活着的节点)，并仅在该节点没有答案时访问其子节点
深度优先搜索：
搜索所有节点直到叶节点
回溯算法效率影响因素发生x [ k ]的时间
满足显性约束的x [ k ]的个数
约束函数的计算时间
计算上限时间
满足限制条件和上边界函数限制的所有x [ k ]的个数
应用例n后的问题解决空间：完全n叉树
想法：
数组x表示n后问题的解。 x [ i ]表示王后I位于国际象棋棋盘第I行的第x [ i ]列。
关于女王I和j，一行一个地放入I！=j，解决行内冲突，一排一个放置x [ i ]！=x [ j ]，解决列内冲突，ABS(I-j )！=ABS(x[I]-x[j] )表示不在同一斜线上，解决斜线冲突。
追溯n解决问题，完整的n叉树表示解空间。 另外，从可行性制约中，扣除不满足行、列、斜线制约的子树。
非递归版本：
数组x记录了从空间树内的根到现在的扩展节点的路径，这些信息中包含了回溯法所需要的空间。 利用包含于数组x的信息，可以以非递归的形式表示上述的回溯法，可以进一步省略o(n )递归堆栈空间。
0-1背包问题解决空间：子集树
想法：
0 - 1背包问题的解空间可以用子集树表示。 在搜索解空间树时，如果其左子节点是可执行节点，则搜索进入其左子树。 只有在右部分树中有可能包含最优解时才进入右部分树的搜索； 否则就砍右边的孩子的树。 如果当前体积被切割到超过最大体积，并且当前价值加上剩余体积，分数后向最大价值小于当前最大价值，则被切割。
时间复杂度o(n*2^n ) ) ) ) ) ) ) )的时间复杂度) ) ) ) ) )。
最大问题解决空间：子集树
假设当前的扩展节点z位于解空间树的第I个层次。 在进入左侧子树之前，必须确保边与从顶点I选择的顶点集的每个顶点相连。 在进入右子树之前，必须确保有足够的可选择顶点，以便算法可能在右子树中找到更大的块。
图的m着色问题的解向量： x [ 1 ] … x [ n ]，x [ i ]表示I节点的颜色
解空间：高度为n 1的完整m叉树
枚举每个节点可执行的颜色，同时检查可行性。 此节点的颜色与相邻节点的颜色不同。 如果可行，则递归继续枚举下一个节点的颜色。 如果所有节点都被枚举，此时的x是合理的染色方案。
旅行销售员问题的解向量： x [ 1 ] … x [ n ]，x [ i ]表示第I步到该点
解空间：排列树
每进行下一步，首先判断下一个节点是否在走，如果是，则剪切，然后判断当前成本和这条边的成本是否大于现有的最小成本，如果是，则剪切。
子集问题解决空间：子集树
想法：
这个问题与0 - 1背包相似，每个物品分为选择和不选择两种状态。
回溯时选择的总价值c被切掉，现值所有剩馀数的价值未达到c时被切掉。