最小长度电路板排列问题(C++实现)

最新推荐文章于 2021-04-20 17:48:59 发布

ZB1139

最新推荐文章于 2021-04-20 17:48:59 发布

阅读量5k

点赞数 22

原文链接：https://blog.csdn.net/ioio_/article/details/81166158

版权

最小长度电路板排列问题

问题描述：

最小长度电路板排列问题是大规模电子系统设计中提出的实际问题。
该问题的提法是，将 n 块电路板以最佳排列方案插入带有n个插槽的机箱中。n块电路板的不同的排列方式对应于不同的电路板插入方案。
设 B={1，2，…， } 是 n 块电路板的集合。集合 L={ N1，N2 ,N3…， } 是 n 块电路板的 m 个连接块。其中每个连接块是B的一个子集，且中的电路板用同一根导线连接在一起。
例如，设n=8，m=5。给定n块电路板及其m个连接块如下：
B={1，2，3，4，5，6，7，8}；L={ N1，N2 ，…， }；
N1={4，5，6}；N2 ={2，3}；N3 ={1，3}； N4={3，6}；N5 ={7，8}。
在这里插入图片描述
在最小长度电路板排列问题中，连接块的长度是指该连接块中第1块电路板到最后1块电路板之间的距离。例如在图示的电路板排列中，连接块的第1块电路板在插槽3中，它的最后1块电路板在插槽6中，因此的长度为3。同理的长度为2。图中连接块最大长度为3。试设计一个分支限界法找出所给n个电路板的最佳排列，使得m个连接块中最大长度达到最小。
本文参考了 https://blog.csdn.net/ioio_/article/details/81166158

他是用Java写的,我用C++改写,并加入了一些注释,如有理解不到位的地方,还请大佬指教.

#include <iostream>
#include<fstream>
#include <vector>
using namespace std;

int n, m;
int bestx[10];// 这是最终的最优解排列顺序
int B[10][10];//电路板在连接块中的排列，是一个二维数组
int x[10], low[10], high[10];// 分别是当前的排列、最左边电路板、最右边电路板
int bestd=0;// 最优解

int len(int ii) {// 计算当前ii排列最小长度
	for (int i = 1; i <= m; i++) {
		high[i] = 0;
		low[i] = n + 1;// 先初始化最左边和最右边的值，
	}
	for (int i = 1; i <= ii; i++)// 对于第i行
		for (int k = 1; k <= m; k++)// k列
			if (B[x[i]][k] > 0) {// 如果第i个电路板在第k个连接块中，
				if (i < low[k])//low[k]代表第K个连接块的最左边的值，如果i比它小，则更新左值
					low[k] = i;
				if (i > high[k])
					high[k] = i;//如果比初始的右值大，则更新右值
			}
	int tmp = 0;
	for (int k = 1; k <= m; k++)
		if (low[k] <= n && high[k] > 0 && tmp < high[k] - low[k])
			tmp = high[k] - low[k];//计算每个连接块的举例
	return tmp;
}
void swap(int* x, int i, int j) {// 交换i和j位置的值
	int tmp;
	tmp = x[i];
	x[i] = x[j];
	x[j] = tmp;
}
void backtrack(int i) {
	if (i == n) {// 如果到达末尾
		int tmp = len(i);// 计算当前排列最小长度
		if (tmp < bestd) {
			bestd = tmp;
			for (int j = 1; j <= n; j++)
				bestx[j] = x[j];
		} // 如果比最优解还要好，则更新bestx[]排列；
	} else {// 若不是末尾；
		for (int j = i; j <= n; j++) {
			swap(x, i, j);
			int ld = len(i);
			if (ld < bestd)
				backtrack(i + 1);// 则继续进入下一个数，
			swap(x, i, j);
		}
	}
}

int arrangeBoards() {
	bestd = n + 1;// 先假设一个很大的值
	for (int i = 1; i <= n; i++)
		x[i] = i;// 这里是最开始的排序；
	backtrack(1);
	return bestd;
}

int main(void) {
	ifstream ifs("input.txt");//文件输入流
	ifs>>n;
	ifs>>m;

	vector<int> temp(m);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ifs>>B[i][j] ;// 输入的电路板的二维数组排列
		}
	}
	int minLen = arrangeBoards();
	cout<<minLen<<endl;
	for (int i = 1; i <= n; i++)
		cout<<bestx[i]<<" ";
	ifs.close();
	return 0;
}