分支限界法——最大团问题和旅行售货员问题-创新互联

本章的例题主要还是以回溯法章节的例题为主

创新互联是一家集网站建设,西藏企业网站建设,西藏品牌网站建设,网站定制,西藏网站建设报价,网络营销,网络优化,西藏网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。创新互联公司专注于庆城网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供庆城营销型网站建设，庆城网站制作、庆城网页设计、庆城网站官网定制、小程序设计服务，打造庆城网络公司原创品牌,更为您提供庆城网站排名全网营销落地服务。

据题目要求，一个图的团需要满足它是一个完全子图，并且不被更大的完全子图包含。然后需要我们求出这个图G的大团，如果像如图给出的例子有三种大团，也就是说大团也不唯一。大团也同时满足大独立集（任意两点无连线）。

首先我们确定团包含的点集合肯定与排序无关，因此我们要构建的是一个子集树。

其次我们要根据题目的要求列出剪枝条件：

1.选取的顶点任意两点都存在边，也就是若已有n个顶点，每加入一个顶点要多n-1条边；

2.如果有更大团，就应当将大团更新

3.大团还是大独立集（可以用于确定上界）

我们在回溯法时的总结依然适用，不过我们现在要用分支限界法来写。

由于分支限界法使用的是大堆的结构，不过在这个题目里12345没有大大小之分（虽然我们也可以以度的大小作为大大小，但是为什么不这么做呢？原因是因为不方便我们进行界限的判断，往下看）。然后我们将在每层来判断图中对应节点是否选取，比如第一层（根节点不算）判断1是选取还是不选，选就走左子树，不选就是右子树，以此类推。

另外知道了分支，我们还要确定界限，很显然题目要求我们的大团中每2个顶点之间都要有边，那么就用邻接表表示原图并看看选取的两个节点ij是否有边。这时也体现出按层来判断对应序号节点的好处了，这样我们就可以直接通过循环遍历，遍历n以内的数字节点和其他节点是否有边。

---

问题如下：某售货员要到若干个城市推销商品，已知各城市之间的路程（或旅费），他要选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路线（或总的旅费）最小。也就是说给定一个无向图，求遍历每一个顶点一次且仅一次的一条回路，最后回到起点的最小花费，这是一个无向图的最小回路问题。

用分支限界法来解决，我们依旧是使用堆的结构，不过要求最小值的话我们就用最小堆

分支原理还是一样的，每层代表一个节点，然后左子树代表选择，右子树代表没选。

界限上我们需要满足题目，首先我们要选取最优值，那么得记录当前最优解bestx吧，如果发现一条路径的路长>=bestx，那就不可能更小，就可以直接剪枝。

其次这个问题需要我们形成回路，那么我们在最后一层也就是n-1层（从0开始，叶子节点为结束点）一定就要和我们的第0层（出发点）的选择是一样的了，也就是说我们无需直接遍历到叶子节点，只需判断n-2层的节点是否能到达叶子节点，如果能就代表是有回路的，否则就直接剪枝。

---

从这两题我们可以总结出代码的编写规范了

在确定了分支条件和界限之后，我们要选择用堆的形式来判断分支选择，一般以每层来代表一个节点，然后对其进行上界和下界的剪枝，其中界限也是会动态变化的，因此也要用算法来确定动态变化的界限，最后当到达叶子节点则得到我们的答案。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文标题：分支限界法——最大团问题和旅行售货员问题-创新互联
标题链接：http://cqcxhl.com/article/cehcgj.html