问题描述

在一块电路板的上下两端分别有 n 个接线柱。根据电路设计，用 $(i, \pi (i))$ 表示将上端接线柱 i 与下端接线柱 $\pi (i)$ 相连，称其为该电路板上的第 i 条连线

下图所示的 $\pi (i)$ 排列为 $\{8, 7, 4, 2, 5, 1, 9, 3, 10, 6\}$ 对于任何 $1 \le i < j \le n$ ，第 i 条连线和第 j 条连线相交的充要条件是 $\pi (i)>\pi (j)$

在制作电路板时，要求将这 n 条连线分布到若干绝缘层上，在同一层上的连线不相交，现在要确定将哪些连线安排在一层上，使得该层上有尽可能多的连线，即确定连线集 $Nets=\{(i,\pi (i)),1\le i\le n \}$ 的最大不相交子集

问题分析

记 $N (i,j)=\{ t|(t,\pi (t))\in Nets, t\le i, \pi (t) \le j \}$ 。$N (i,j)$ 的最大不相交子集为 $MNS (i,j)$ ，$size (i,j)=|MNS (i,j)|$

经分析，该问题具有最优子结构性质。对规模为 n 的电路布线问题，可以构造如下递归式

$$\begin {align*} &(1) \ 当 \ i=1\ 时， size (1,j)= \begin {cases} 0, & \text {j<$\pi$(1)} \\ 1, & \text {其他情况} \end {cases} \\ &(2) \ 当 \ i>1\ 时， size (i,j)= \begin {cases} size (i-1,j), & \text {j<$\pi$(i)} \\ max {size (i-1,j),size (i-1,\pi (i)-1)+1}, & \text {其他情况} \end {cases} \end {align*}$$

C 代码

#include <stdio.h>
#include <stdlib.h>
 
#define N 10    // 问题规模
 
// 求最大不相交连接数
void maxNum(int pi[], int **size);
 
// 构造最大不相交连接集合，net[i]表示最大不相交子集中第i条连线的上端接线柱的序号
int constructSet(int pi[], int **size, int *net);
 
int main(void){
    // 下标从1开始
    int pi[N+1] = {0, 8, 7, 4, 2, 5, 1, 9, 3, 10, 6};
    int net[N];
 
    int **size;
    size = (int**)malloc(sizeof(int*)*(N+1));
    for(int i=0;i<N+1;i++)
        size[i]=(int*)malloc(sizeof(int)*(N+1));
    maxNum(pi, size);
    int m = constructSet(pi, size, net);   
    printf("最大不相交连接数为：%d\n",m);
    printf("包含的连线为：\n");
    for(int i=0; i<m; i++){
        printf("(%d,%d)\n", net[i], pi[net[i]]);
    }
 
}
 
void maxNum(int pi[], int **size){
    // size[i][j]: 上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数
    int i,j;
 
    // when j<pi(1)
    for(j=0; j<pi[1]; j++)
        size[1][j];
 
    // when j>=pi(1)
    for(j=pi[1]; j<=N; j++)
        size[1][j];
 
    for(i=2; i<N; i++){
 
        // when j<pi(i)
        for(j=0; j<pi[i]; j++)
            size[i][j] = size[i-1][j];   
 
        // when j>=c[i]
        for(j=pi[i]; j<=N; j++)
            size[i][j]=size[i-1][j]>=size[i-1][pi[i]-1]+1 ? size[i-1][j] : size[i-1][pi[i]-1]+1;
    }
 
    // 最大连接数
    size[N][N] = size[N-1][N]>=size[N-1][pi[N]-1]+1 ? size[N-1][N] : size[N-1][pi[N]-1]+1;
}
 
// 构造最大不相交连接集合，net[i]表示最大不相交子集中第i条连线的上端接线柱的序号
int constructSet(int pi[], int **size, int *net){
    int i;
    int j=N;
    int m=0;    // 记录最大连接集合中的接线柱
 
    for(i=N; i>1; i--){ // 递减
        // (i,pi[i])是最大不相交子集的一条连线
        if(size[i][j] != size[i-1][j]){
            net[m++]=i; // 将i记录到数组net中，连接线数自增1
            j=pi[i]-1;  // 更新扩展连线柱区间
        }
    }
 
    // when i=1
    if(j>=pi[1])
        net[m++] = 1;
 
    return m;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

其他

在搜索过程中发现已有的文章：算法设计与分析 —— 电路布线（动态规划）

参考文章

LaTeX 公式手册

Typora 中使用 LaTeX：多行公式左对齐

用 malloc 动态申请一个二维数组的三种方法