动态规划——电路布线问题

问题：

在一块电路板的上、下两端分别有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)