算法 电路布线问题 (动态规划)

问题描述

在一块电路板的上下两端分别有 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动态申请一个二维数组的三种方法