Uva 140 Bandwidth（回溯法+剪枝）

93 阅读 0 评论 62 点赞

我是靠谱客的博主眯眯眼期待，最近开发中收集的这篇文章主要介绍Uva 140 Bandwidth（回溯法+剪枝），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

书附的代码只有使用next_permutation()逐个计算带宽的，而网上没看到很符合心意的（回溯法+剪枝）的题解，自己写了个自我感觉逻辑比较清晰的，水准有限。

（书附git链接：https://github.com/aoapc-book/aoapc-bac2nd/blob/master/ch7/UVa140.cpp）

题意：

输入一行数据，其中有n个字符节点和节点间的连通关系，输出一组排列，节点i的带宽为i和相邻节点在排列中的最远距离，所有带宽的最大值就是该排列的带宽。按字典序输出带宽最小的排列。

思路：

一是列出所有排列后逐个计算带宽，并和最优解比较。（书附有了，就不献丑了）

二是使用回溯法。

在回溯的过程中，记录下目前已经找到的最小带宽k。如果发现已经有某两个结点的距离大于或等于k，再怎么扩展也不可能比当前解更优，应当强制把它“剪”掉，就像园丁在花园里为树修剪枝叶一样，也可以为解答树“剪枝（prune）”。

除此之外，还可以剪掉更多的枝叶。如果在搜索到结点u时，u结点还有m个相邻点没有确定位置，那么对于结点u来说，最理想的情况就是这m个结点紧跟在u后面，这样的结点带宽为m，而其他任何“非理想情况”的带宽至少为m+1。这样，如果m≥k，即“在最理想的情况下都不能得到比当前最优解更好的方案”，则应当剪枝。（此段是复制书本的。。本人语言表达能力有限）

测试输入：

A:FB;B:GC;D:GC;F:AGH;E:HD
#

测试输出：

A B C F G D H E -> 3

代码：（输入数据处理部分是修改书附代码的，自认没能力写的更舒服。。）

#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 10;
int id[256], letter[maxn];
int G[maxn][maxn]; 

int A[maxn],ans[maxn],vis[maxn];
int n,sw; //sw为最优带宽 

void dfs(int cur,int bw){ //bw为当前排列的最大带宽 
	if(cur==n){ //走到这里一定是当前最优的了
			memcpy(ans,A,sizeof(int)*n);
			sw=bw;
	}
	else for(int i=0;i<n;i++){
		if(!vis[i]){
			
			//最理想性剪枝
			int m=0; 
			for(int j=0;j<cur;j++){
				if(G[i][j]&&!vis[j]) m++;
			}
			if(m>=sw) break; 
			
			//最优性剪枝 
			int ok=1;
			A[cur]=i;
			for(int j=0;j<cur;j++){
				if(G[A[j]][i]){
					int w=cur-j;
					if(w>=sw){ //当前的最大带宽已经不小于最优解了。放弃
						ok=0;break;
					}
					if(w>bw) bw=w;
				} 
			}
			if(ok) {
				vis[i]=1;
				dfs(cur+1,bw);
				vis[i]=0;
			}
			else{
				break; //如果i在cur带宽已经超了，在cur之后更大，直接跳过cur 
			}
		}
	}
}

int main() {
	char input[1000];
	while(scanf("%s", input) == 1 && input[0] != '#') {
		// 计算结点个数并给字母编号
		n = 0;
		for(char ch = 'A'; ch <= 'Z'; ch++)
		if(strchr(input, ch) != NULL) {
			id[ch] = n++;
			letter[id[ch]] = ch;
		}
		sw=n;
	
		// 处理输入
		int len = strlen(input), p = 0, q = 0;
		memset(G,0,sizeof(G));
		for(;;) {
			while(p < len && input[p] != ':') p++;
			if(p == len) break;
			while(q < len && input[q] != ';') q++;
			for(int i = p+1; i < q; i++) {
				G[id[input[p-1]]][id[input[i]]]=1;
				G[id[input[i]]][id[input[p-1]]]=1;
			}
			p++; q++;
			}
	
			// 回溯 
			memset(vis,0,sizeof(vis));
			dfs(0,0);

			// 输出
			for(int i = 0; i < n; i++) printf("%c ", letter[ans[i]]);
			printf("-> %dn", sw);
	}
	return 0;
}