分支限界回课资料.pptx

《分支限界回课资料.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分支限界回课万文恺1600017830目录综述拓展资料样例分析基本概念组合优化问题目标函数约束条件可行解最优解①变量的取值范围搜索空间中满足约束条件的解目标函数到达极大/极小值的解综述极大化或极小化基本概念代价函数界①极大化问题中，是以节点为根的所有可行解的上界。已经得到的可行解中的最大值可行解的目标函数值大于界时，更新界下列概念针对极大化问题讨论综述分支限界思想设立代价函数设立界①综述剪枝更新最大团问题②样例分析代价函数设计思路假设p是搜索树上的节点，f是目标函数，g是代价函数①极小化问题中，g(p)≤f(p)对任

2、意p成立极大化问题中，g(p)≥f(p)对任意p成立②对所有叶子节点p，有g(p)=f(p)③p1是p2的父节点。极小化问题g(p1)≤g(p2)极大化问题g(p1)≥g(p2)常用剪枝方法最优性剪枝可行性剪枝①代价函数不大于界节点不满足约束条件综述可能最优剪枝：预处理/启发式估值，优先搜索最可能拓展最优解的节点优先扩展：优先扩展可能性较少的状态减少重复计算不同扩展策略①综述①③②1.BeFS(优先搜索最佳)2.BFS3.DFS分支限界伪码(极小化)①综述样例回顾0-1背包问题②样例分析最大团问题(MCP)货郎担问题

3、(TSP)圆排列问题连续邮资问题0-1背包问题②样例分析目标函数问题描述有N件物品和一个容量为b的背包。第i件物品的费用是w[i]，价值是v[i]。求解：将哪些物品装入背包可使这些物品：费用总和不超过背包容量，且价值总和最大。解向量为,xi=0，1(不选择/选择)约束条件的代价函数：最大团问题②样例分析目标函数问题描述给定一

4、个无向图G=，

5、G

6、=n，求G的最大团。G的团：G的最大子图最大团：顶点数最多的团节点是可行解，表示节点的选择状况，xi=0不选择，xi=1选择约束条件团中的顶点之间均有边相连最大团问题②样例分析代价函数将未选择的节点全部视为可以加入最大团中的节点。对于节点有代价函数：F=Cn+n-k货郎担问题②样例分析概念定义问题描述(这里根据无向图进行讨论)给定一个无向完全带权图G=，求出一条遍历每个顶点各一次，且路径权值总和最小的路径。（路径权值最小的哈密顿通路）约

7、束条件每个顶点仅遍历一次极小化目标函数解向量，其中xi表示第i步遍历到顶点xidi(1<=i<=n-1)表示第i步选择的路径长度。货郎担问题②样例分析代价函数L=当前路径权值之和可以。更好的方案：首先定义li为与节点i相连，权值最小的边,代价函数L:圆排列问题②样例分析问题描述给定n个圆的排列，将各个圆与矩形的底边相切，求出所得矩形的最小长度l。解向量，其中xi∈{1,2..n}表示第i个圆选择了圆xi。部分解向量表示前k个圆已经选好。圆排列问题②样

8、例分析参数说明k：算法进行到k步rk：第k个圆的半径dk：k-1个圆到第k个圆的圆心水平距离xk：第k个圆的圆心坐标lk：前k个圆的排列长度Lk：前k个圆的代价函数（极小化问题，下界）圆排列问题②样例分析圆排列问题②样例分析连续邮资问题②样例分析问题描述给定n种不同面值的邮票，每个信封至多m张，给出邮票的最佳设计，使得从1开始，增量为1的连续邮资区间达到最大。约束条件必要条件：假设前k种邮票可以凑出[1,rk]的邮资，k+1种邮票的取值范围为[xk+1,rk+1].可行解，x1=1,x1

9、3…xn连续邮资问题②样例分析代价函数(?)动态规划：y(i,j)表示当面值组合为，邮票金额之和为j时所需的最小邮票数。边界条件：y(1,j)=j状态转移函数：y(i,j)=min{t+y(i-1,j-t*xi)}连续邮资r:min(r),r∈{r

10、y(i,r)<=m,y(i,r+1)>m}Sticks③拓展资料问题描述给定一些不同长度的小木棍，它们可以拼成的等长的一些木棍。求出原有木棍可能的最小长度。约束条件小木棍可以拼成圆木棍否定形式更方便：如果有一根木棍，用其他的任何木棍都不能凑成整根，不满

11、足约束条件。Sticks③拓展资料剪枝①可行性剪枝：原木棍长度不会超过最长的小木棍；②可行性剪枝：原木棍长度可以整除木棍总长度③可行性剪枝：只要发现有一根木棍无法用其余木棍匹配，则不用匹配其他木棍，直接剪枝④最优性剪枝：由于是最小化问题，在搜索顺序中含有最优性剪枝。⑤减少重复计算：如果一根木棍暂时不能匹配拼接中的木棍，等长度的其他木棍同样不行。