动态规划——电路布线问题
问题:
在一块电路板的上、下两端分别有n个接线柱。根据电路设计,要求用导线(i,π(i))将上端接线柱与下端接线柱相连,其中π(i)是{1,2,…,n}的一个排列。导线(i,π(i))称为该电路板上的第i条连线。对于任何1≤i<j≤n,第i条连线和第j条连线相交的充分且必要的条件是π(i)>π(j)。
电路布线问题要确定将哪些连线安排在第一层上,使得该层上有尽可能多的连线。换句话说,该问题要求确定导线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。
分析:
该问题和最长公共子序列问题属于同一类问题,同样需要关注序列的末端,不同的是由于本题的序列元素间已经存在了某种映射关系,所以在递推时跨的步长更大。
——最优子结构:设s[i][j]为序列[1,i],[1,j]的最大不相交子集,那么若i对应的接线柱π(i)>j,说明接线柱i已经不可能再被选中了,那么s[i][j]=s[i-1][j];若i对应的接线柱π(i)<=j,说明接线柱i可能被选中,那么就有两种情况,选与不选,假如选了,那i就去掉,同时π(i)以及序号大于它的接线柱也不可能被选中了,因为假如被选了,那就有相交了,所以s[i][j]=s[i-1][π(i)-1]+1,假如不选,那就是s[i][j]=s[i-1][j],子结构满足最优子结构性质。
——确定递推关系:s[i][j]=s[i-1][j],π(i)>j;s[i][j]=max(s[i-1][π(i)-1]+1,s[i-1][j]),π(i)<=j。
——计算最优值:初始化最小子问题,第1行的所有值可计算。按照行逐行求解,每一个元素取决于其上一行的某一个元素。
——确定最优解:开辟一个二维数组b,记录s的每个状态对应的最优选择,然后重走革命路。
代码:
#include <bits/stdc++.h>using namespace std;#define MAXN 105// 求最优值,即各个子问题最大不相交子集的大小// 输入:序列pi,子问题最优值记录矩阵s,最优解记录矩阵b,pi长度nvoid MNS(int pi[],int s[][MAXN],int b[][MAXN],int n){// 初始化最小子问题for(int i = 1;i <= n;i++){if(pi[0]<=i){s[1][i] = 1;b[1][i] = 2;}else{s[1][i] = 0;b[1][i] = 1;}}// 根据递推公式计算解空间for(int i = 2;i <= n;i++){for(int j = 1;j <= n;j++){if(pi[i-1] > j){s[i][j] = s[i-1][j];b[i][j] = 1;}else{// 没选if(s[i-1][j] > s[i-1][pi[i-1]-1]+1){s[i][j] = s[i-1][j];b[i][j] = 1;}else{// 选了s[i][j] = s[i-1][pi[i-1]-1]+1;b[i][j] = 2;}}}}}// 根据记录矩阵b还原最优解void traceback(int b[][MAXN],int pi[],int i,int j){if(i==0 || j==0){// 这里一定要到最小子问题也处理完才返回return;}if(b[i][j] == 1){// 行为1,没选这个下层接线柱traceback(b, pi, i-1, j);}if(b[i][j] == 2){// 行为2,选这个下层接线柱traceback(b, pi, i-1, pi[i-1]-1);cout<<i<<" "<<pi[i-1]<<endl;}}int main(){int pi[8] = {1,4,2,3,6,8,5,7};int s[MAXN][MAXN];int b[MAXN][MAXN];MNS(pi, s, b, 8);cout<<s[8][8]<<endl;traceback(b, pi, 8, 8);}
时间复杂度和空间复杂度都是O(n2)