![[求助] python 如何爬取 网页上调用JS函数打开的视频链接](/aiimages/%5B%E6%B1%82%E5%8A%A9%5D+python+%E5%A6%82%E4%BD%95%E7%88%AC%E5%8F%96+%E7%BD%91%E9%A1%B5%E4%B8%8A%E8%B0%83%E7%94%A8JS%E5%87%BD%E6%95%B0%E6%89%93%E5%BC%80%E7%9A%84%E8%A7%86%E9%A2%91%E9%93%BE%E6%8E%A5.png)
用约束函数在扩展结点处剪去不满足约束的子树； 和用限界函数剪去得不到最优解的子 树。这两类函数统称为剪枝函数。
采用剪枝函数，可避免无效搜索，提高回溯法的搜索效率。 在分支限界法中使用剪枝函数， 可以加速搜索。 该函数给出每一个可行结点相应的子树可能获得的最大价值的上界。如果这个上界不比当前最优值更大， 则说明相应的子树中不含问题的最优解，因而可以剪去。
搜索策略
在当前节点（扩展节点）处，先生成其所有的子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处；
计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。
以上内容参考：百度百科-分支限界法
约束函数和限界函数的目的是相同的，都为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，它们统称为剪枝函数（pruning function）。
使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法(backtracking)
使用剪枝函数的广度优先生成状态空间树中结点的求解方法称为分支/枝限界法(branch-and-bound)
回溯法/分支限界法 = 穷举 + 剪枝。
回溯法是一个既带有系统性又带有跳跃性的搜索算法；
这种以深度优先的方式系统地搜索问题的解得算法称为回溯法。其实回溯法就是对 隐式图 的深度优先搜索算法
回溯是穷举方法的一个改进，它在所有可行的选择中，系统地搜索问题的解。它假定解可以由向量形式 (x1,x2,...,xn) 来 表示，其中xi的值表示在第i次选择所作的决策值，并以深度优先的方式遍历向量空间,逐步确定xi 的值，直到解被找到。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束，来确保解的正确性。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。( 找出解空间树中满足约束条件的所有解 )
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。 这种方法适用于解一些组合数较大的问题 。
（1）问题框架
（2） 递归的算法框架
回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中i为搜索的深度，框架如下：
（3）非递归回溯框架（递归转非递归，这里可以参考树的遍历，或者看上篇博客——递归算法介绍）
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为 ，则回溯法所需的计算空间通常为 。而显式地存储整个解空间则需要 或 内存空间。
回溯法解题的时候常遇到两种类型的解空间树：
用回溯法搜索子集树的算法框架可描述为：
用回溯法搜索排列树的算法框架可描述为：
回溯法是一种选优搜索法（试探法）。
基本思想：将问题P的状态空间E表示成一棵高为n的带全有序树T，把求解问题简化为搜索树T。搜索过程采用 深度优先搜索 。搜索到某一结点时判断该结点是否包含原问题的解，如果包含则继续往下搜索，如果不包含则向祖先回溯。
通俗来说，就是利用一个树结构来表示解空间,然后从树的根开始深度优先遍历该树，到不满足要求的叶子结点时向上回溯继续遍历。
几个结点：
扩展结点：一个正在产生子结点的结点称为扩展结点
活结点：一个自身已生成但未全部生成子结点的结点
死结点：一个所有子结点已全部生成的结点
1、分析问题，定义问题解空间。
2、根据解空间，确定解空间结构，得 搜索树 。
3、从根节点开始深度优先搜索解空间（利用 剪枝 避免无效搜索）。
4、递归搜索，直到找到所要求的的解。
1、子集树
当问题是：从n个元素的集合S中找出满足某种性质的子集时，用子集树。
子集树必然是一个二叉树。常见问题：0/1背包问题、装载问题。
遍历子集树时间复杂度：O（2^n）
2、排列树
当问题是：确定n个元素满足某种排列时，用排列数。常见问题：TSP旅行商问题，N皇后问题。
遍历排列树时间复杂度：O（n!）
通俗地讲，结合Java集合的概念，选择哪种树其实就是看最后所得结果是放入一个List（有序）里，还是放入一个Set（无序）里。
剪枝函数能极大提高搜索效率，遍历解空间树时，对于不满足条件的分支进行剪枝，因为这些分支一定不会在最后所求解中。
常见剪枝函数：
约束函数（对解加入约束条件）、限界函数（对解进行上界或下界的限定）
满足约束函数的解才是可行解。
1、0/1背包问题
2、TSP旅行商问题
3、最优装载问题
4、N-皇后问题
具体问题可百度详细内容。
