案例分析：电路布线问题

问题描述：

在一块线路板的上、下两边各自有n个接线头。依据电源电路设计方案，规定用输电线（i，π（i）） 将上方接线头i与下方接线头π（i）相接，如下图。在其中，π（i），1≤ i 《≤n，是｛1，2，…，n｝的一个排列。导线（I， π（i））称为该电路板上的第i条连线。对于任何1 ≤ i ≤ j ≤n，第i条连线和第j条连线相交的充要条件是π（i）》 π（j）。

在制做线路板时，规定将这n根线遍布到多个电缆护套上，在同一层上的连线不可以交点。电源电路走线问题要明确将什么连线分配在第一层上，促使该层上面有尽量多的连线。也就是说，该问题规定明确输电线集Nets = ｛i，π（i），1 ≤ i ≤ n｝的较大不愿交非空子集。

问题分析：

1. 最佳子结构特性

记N（i，j） = {t|（t， π（i）） ∈ Nets，t ≤ i， π（t） ≤ j }。 N（i，j）的最高不交点非空子集为MNS（i，j）。Size（i，j）=|MNS（i，j）|。

1） 当i = 1时

2） 当i 》1时，

① j 《π（i）。这时，（i，π（i）） 不属于N（i，j）。故在这样的情况下，N（i，j） = N（i-1，j），进而Size（i，j）=Size（i-1，j）。

② j ≥π（i）。这时，若（i， π（i））∈MNS（i，j），则对随意（t， π（i））∈MNS（i，j）有t 《 i且π（t）《 π（i）；不然，（t，π（t））与（i， π（i））交点。在这样的情况下MNS（i，j）-{（i， π（i））}是N（i-1， π（i）-1）的最高不交点非空子集。不然，非空子集MNS（i-1，π（i）-1）∪{（i， π（i））}包含于N（i，j）是比MNS（i，j）更高的N（i，j）的不交点非空子集。这与MNS（i，j）的界定相分歧。

若（i， π（i））不属于MNS（i，j），则对随意（t， π（t））∈MNS（i，j），有t《i。进而MNS（i，j）包含于N（i-1，j），因而，Size（i，j）≤Size（i-1，j）。

另一方面，MNS（i-1，j）包含于N（i，j），故又有Size（i，j） ≥Size（i-1，j），进而Size（i，j）= Size（i-1，j）。

2. 递归计算最佳值

经以上后分，可电源电路布线问题的最佳数值Size（n，n）。由该问题的最佳子结构特性得知：

C 程序流程：

//CircuitLayout.h

#ifndef CIRCUITLAYOUT_H

#define CIRCUITLAYOUT_H

class CircuitLayout{

private：

int count;//较大连线柱

int *c;//int **Size;//较大连线数额

int *net;//储存连线

bool Input（）;

int max（int，int）;

void mnset（int *c，int **Size）;//测算最佳值

int traceback（int *c，int **Size，int *net）;//结构最优解

public：

CircuitLayout（）;

~CircuitLayout（）;

bool Run（）;//运作插口函数公式

};

#endif

//CircuitLayout.cpp

#include “CircuitLayout.h”

#include 《iostream》

#include 《math.h》

using namespace std;

#define MAX（a，b） （（（a）》（b）？（a）：（b）））

#define M 50

CircuitLayout：：CircuitLayout（）{

int N = 0;

c = new int［M］;

net = new int［M］;

Size = new int*［M］;

for（int i=0;i《M; i）

Size［i］ = new int［M］;

}

CircuitLayout：：~CircuitLayout（）{

for（int i=0;i《M; i）

delete ［］Size［i］;

delete ［］Size;

delete ［］c;

delete ［］net;

}

bool CircuitLayout：：Input（）{

int n;

cout 《《 “请输入接线柱的个数： ”;

cin 》》 n;

count = n;

cout 《《 “请先后键入被线程数： ” 《《 endl;

for（int i=0;i《n; i）

cin 》》 c［i］;

if（c） return true;

else return false;

}

int CircuitLayout：：max（int a，int b）{

if（a 》= b） return a;else return b;

}

void CircuitLayout：：mnset（int *c，int **Size）{

int i=0;

int j=0;

int n = count-1;

for（j=0;j《c［1］;j ）

Size［1］［j］ = 0;

for（j=c［1］;j《=n;j ）

Size［1］［j］ = 1;

for （i=2;i《n;i ）{

for （j=0; j《c［i］ ; j ）

Size［i］［j］ = Size［i-1］［j］;

for （j=c［i］;j《=n;j ）

Size［i］［j］ = max（Size［i-1］［j］，Size［i-1］［c［i］-1］ 1）;

}

Size［n］［n］ = max（Size［n-1］［n］，Size［n-1］［c［n］-1］ 1）;

cout 《《 “s［n］［n］： ” 《《 Size［n］［n］ 《《 endl;

}

int CircuitLayout：：traceback（int *c，int **Size，int *net）{

int n = count-1;

int j = n;

int m = 0;

for （int i=n;i》0;i–）{

if （Size［i］［j］ ！= Size［i-1］［j］）{

net［m ］ = i; j = c［i］ – 1;

}

}

if（j》=c［0］）

net［m ］ = 0;

for（int k=0;k《m; k）

cout 《《 “net： ” 《《 net［k］ 《《 “ ”;

cout 《《 endl;

return m;

}

bool CircuitLayout：：Run（）{

int msize = 0;

if（Input（））{

mnset（c，Size）;

msize = traceback（c，Size，net）;

cout 《《 “msize： ”《《 msize;

cout 《《 endl;return true;

}

else return false;}

int main（）{

CircuitLayout xiaoli;

xiaoli.Run（）;

return 0;

}

该文章内容提高散播新技术应用新闻资讯，很有可能有转截/引入之状况，若有侵权行为请联络删掉。