动态规划电路布线

目录

电路布线简介举例及其详细说明代码块测试结果

---

电路布线简介

在一块电路板的上下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i)),将上端接线柱i与下端接线柱π(i)相连，如图，其中，π(i),1<=i<=n,是(1,2……,n)的一个排列.导线(i,π(i))称为该电路板上的第i条连线.对于任何1<=i小于j<=n,第i条连线和第j条连线相交的充分且必要条件是π(i)>π(j)。

---

举例及其详细说明

首先用a[i]数组表示与上面对应点相连线的下面的点，再用set[i][j]表示上面节点i与下面节点j连线的左边（包括i j连线）的最大不相交连线的个数。

　　于是就有公式：

　　　　　　　　max(set[i-1][j], set[i][j-1]); j != a[i]　　

　　set(i,j) =

　　　　　　　　set[i-1][j-1] + 1; j == a[i]

然后就可以对每一个i，都对所以的j求一遍。这样就可以得出结果吗，set[n][n]即我们想要的结果。

最后通过回溯把结果输出出来。

---

代码块

#include <stdio.h> #include<stdlib.h> #define MAX(a,b) ((a) > (b) ? (a) : (b)) void circut(int a[], int set[][11], int n); void back_track(int i, int j, int set[][11]); int main() { int a[] = { 0, 8, 7, 4, 2, 5, 1, 9, 3, 10, 6 }; int set[11][11]; circut(a, set, 10); printf("max set: %d \n", set[10][10]); back_track(10, 10, set); printf("\n"); system("pause"); return 0; } void circut(int a[], int set[][11], int n) { int i, j; for (i = 0; i < n; i++) { set[i][0] = 0; set[0][i] = 0; } for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (a[i] != j) set[i][j] = MAX(set[i - 1][j], set[i][j - 1]); else set[i][j] = set[i - 1][j - 1] + 1; } } } void back_track(int i, int j, int set[][11]) { if (i == 0) return; if (set[i][j] == set[i - 1][j]) back_track(i - 1, j, set); else if (set[i][j] == set[i][j - 1]) back_track(i, j - 1, set); else { back_track(i - 1, j - 1, set); printf("(%d,%d) ", i, j); } }

---

测试结果