侵權投訴

電路布線問題C++實現案例

2020-08-08 11:48 ? 次閱讀

問題描述:

在一塊電路板的上、下兩端分別有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;

}

收藏 人收藏
分享:

評論

相關推薦

NI推新款M系列USB數據采集設備,輕松實現電路板連接

美國國家儀器有限公司(National Instruments,簡稱NI)推出新款M系列USB數據采....
的頭像 電子發燒友網工程師 發表于 08-30 09:07 ? 35次 閱讀
NI推新款M系列USB數據采集設備,輕松實現電路板連接

Linux操作系統知識講解:避免內存使用七大坑

Linux操作系統知識講解:避免內存使用七大坑
的頭像 如意 發表于 08-28 11:12 ? 101次 閱讀
Linux操作系統知識講解:避免內存使用七大坑

Python語言的特點和使用Python對XML文件的數據進行解析說明

在民用航空電子產品的測試過程中,大部分的測試用例需要編寫測試腳本進行自動化測試。Python 作為一....
發表于 08-28 10:33 ? 11次 閱讀
Python語言的特點和使用Python對XML文件的數據進行解析說明

變頻器維修的三大建議

變頻器電路板損壞的原因,絕大多數是板上眾多元器件中,有個別壞了。電路板的維修過程,就是尋找故障板上個....
發表于 08-27 17:04 ? 65次 閱讀
變頻器維修的三大建議

國內SSD價格已下跌到最低水位,NAND閃存價格后續有較大上漲空間

內存、SSD固態盤這兩年的價格可謂跌宕起伏,誰也無法準確預料就接下來到底會怎么走,但總歸有些蛛絲馬跡....
的頭像 牽手一起夢 發表于 08-27 15:43 ? 235次 閱讀
國內SSD價格已下跌到最低水位,NAND閃存價格后續有較大上漲空間

如何防止PCB板子過回焊爐發生板彎及板翹呢?

許多電子的產品為了達到更輕薄的目的,板子的厚度已經剩下1.0mm、0.8mm,甚至做到了0.6mm的....
的頭像 Torex產品資訊 發表于 08-26 10:49 ? 159次 閱讀
如何防止PCB板子過回焊爐發生板彎及板翹呢?

C#入門知識教學經典教程

C#是微軟公司發布的一種面向對象的、運行于 NET Framework之上的高級程序設計語言并定于在....
發表于 08-26 08:00 ? 29次 閱讀
C#入門知識教學經典教程

電路板需要雙面SMT打件怎么決定

 如果電路板需要雙面(side1、side2或A面、B面)SMT打件,是哪一面先打?先打的哪面是如何....
發表于 08-25 15:56 ? 82次 閱讀
電路板需要雙面SMT打件怎么決定

Molex基于 PCIe 的系統背板兼容線纜組件

電信和數據中心企業面對與日俱增的帶寬需求,因此需要高密度的互連。為了滿足這些需求,莫仕繼續開發各種創....
的頭像 lhl545545 發表于 08-25 14:35 ? 180次 閱讀
Molex基于 PCIe 的系統背板兼容線纜組件

僅憑顏色判斷PCB的表面工藝?

金色的最貴,是真正的黃金。雖然只有薄薄的一層,但也占了電路板成本的近10%。廣東和福建沿海有些地方專....
的頭像 凡億PCB 發表于 08-25 14:09 ? 227次 閱讀
僅憑顏色判斷PCB的表面工藝?

Chrome團隊將測試驗證Rust與C++的互操作性

Chrome 團隊也開始嘗試 Rust 了。在 Chromium 官網近期發布的文檔中,“Rust ....
的頭像 如意 發表于 08-25 10:35 ? 84次 閱讀
Chrome團隊將測試驗證Rust與C++的互操作性

如何使用Windows環境實現快速機器視覺系統接口

目前機器視覺研究的主要問題是 視覺算法的魯棒性問題,因此提供快速有效的視覺試驗方案對提高機器視覺的理....
發表于 08-24 17:15 ? 75次 閱讀
如何使用Windows環境實現快速機器視覺系統接口

印制電路板的元件布局和安裝設計

印制電路板(PrintedCircuitBoard)的設計中除了硬件工程師做的原理圖設計、pcb工程....
發表于 08-22 10:06 ? 171次 閱讀
印制電路板的元件布局和安裝設計

手機通信電路板的故障及檢修方法

 手機通信電路板出現故障必須怎么知道跟檢修呢?
的頭像 電子魔法師 發表于 08-22 09:45 ? 244次 閱讀
手機通信電路板的故障及檢修方法

電路板金相切片制作的常見問題及解決方法

電路板金相切片研磨過程中速度應該怎樣控制?研磨過程速度不宜過快,速度越快單位切削越強,樣品標本的形變....
發表于 08-22 09:26 ? 66次 閱讀
電路板金相切片制作的常見問題及解決方法

PCB樣板調試步驟及PCB故障查找方法

對于一個新設計的電路板樣板,調試起來往往會遇到一些困難,特別是當板比較大、元件比較多時,往往無從下手....
發表于 08-22 09:21 ? 122次 閱讀
PCB樣板調試步驟及PCB故障查找方法

整理思維!史上最全Linux/C/C++思維導圖!

史上最全Linux/C/C++思維導圖
的頭像 玩轉單片機 發表于 08-21 17:10 ? 237次 閱讀
整理思維!史上最全Linux/C/C++思維導圖!

分析印刷電路板PCB工藝選型的目的

隨著電子技術的發展,印制電路板從單面板逐步發展為雙面板、多層板、撓性板和剛-撓結合板,制造加工技術上....
的頭像 如意 發表于 08-21 17:07 ? 309次 閱讀
分析印刷電路板PCB工藝選型的目的

淺談印制電路板(PCB)的由來

印制電路板又稱印刷電路板、印刷線路板,簡稱印制板,英文簡稱PCB(Printed Circuit B....
的頭像 如意 發表于 08-21 17:01 ? 419次 閱讀
淺談印制電路板(PCB)的由來

一起來了解一下電路板(線路板)PCBA清洗的作用

清洗在電路板(線路板)PCBA制造過程中往往被忽略,認為清洗并不是關鍵步驟。然而,隨著產品在客戶端的....
發表于 08-21 15:54 ? 111次 閱讀
一起來了解一下電路板(線路板)PCBA清洗的作用

如何使用PHP-X快速開發一個PHP擴展

PHP-X是我在2018年年初創建的一個新項目。這個項目的目標就是讓有一定工作經驗的PHP程序都能夠....
發表于 08-20 16:47 ? 21次 閱讀
如何使用PHP-X快速開發一個PHP擴展

印制電路板設計的技術指導教程

本文件規定了印制線路板設計所需的一些基本原則數據和要求,對電子設備中印制線路板設計起指導作用。電路名....
發表于 08-20 15:00 ? 48次 閱讀
印制電路板設計的技術指導教程

一文解析什么是ESO10.3x38

隨著ESO10.3x38的推出,SCHURTER進一步擴大了應用于電路板的產品范圍。ESO10.3x....
的頭像 電子發燒友網工程師 發表于 08-20 10:31 ? 53次 閱讀
一文解析什么是ESO10.3x38

利用電磁場測量工具觀測電源/地阻抗設計問題

電源與地之間的輸入阻抗是衡量電源供電系統特性的一個重要的指標,影響電源供電系統特性的因素有:PCB的....
的頭像 電子設計 發表于 08-19 09:36 ? 393次 閱讀
利用電磁場測量工具觀測電源/地阻抗設計問題

SUSAN特征檢測的基本原理和算法的性能和應用研究

無論對直線,還是曲線邊緣,SUSAN算法基本上可以檢測出所有的邊緣,檢測結果較好。雖然實驗中沒有達到....
的頭像 電子設計 發表于 08-18 09:07 ? 631次 閱讀
SUSAN特征檢測的基本原理和算法的性能和應用研究

英國SST 氧氣變送器傳感器 -OXY-LC-485系列主要應用在哪些方面?

由于采用直接抽取法測量煙氣中的污染物濃度,系統可以用標準氣對分析儀進行在線標定,保證監測數據的準確性....
發表于 08-17 09:54 ? 87次 閱讀
英國SST 氧氣變送器傳感器 -OXY-LC-485系列主要應用在哪些方面?

如何判斷PCB電路板的好壞

隨著手機、電子、通訊行業等高速發展,PCB線路板產業不斷壯大和迅速增長,同時也促使人們對于PCB的層....
發表于 08-16 11:58 ? 418次 閱讀
如何判斷PCB電路板的好壞

如何降低電路板的噪聲

 我們在設計電路板的時候,電路原理設計的很好,甚至說很優秀,但是,在調試過程中會出現各種各樣的噪聲,....
發表于 08-16 09:23 ? 163次 閱讀
如何降低電路板的噪聲

自制電路板的方法有哪些

1.將敷銅板裁成電路圖所需尺寸。 2.把蠟紙放在鋼板上,用筆將電路圖按1:1刻在蠟紙上,并把刻在蠟紙....
的頭像 Wildesbeast 發表于 08-15 11:59 ? 694次 閱讀
自制電路板的方法有哪些

有什么方法可以有效預防PCBA加工焊接產生氣孔

PCBA板焊接產生的氣孔,也就是我們經常說的氣泡,一般在PCBA加工過程中的回流焊接和波峰焊接是會產....
發表于 08-13 10:06 ? 123次 閱讀
有什么方法可以有效預防PCBA加工焊接產生氣孔

C++語言的設計和演化PDF電子書免費下載

這是一本獨特的書,是由C+語言的設計師本人寫的,描述C*+語言的發展歷史、設計理念及技術細節的著作。....
發表于 08-13 08:00 ? 38次 閱讀
C++語言的設計和演化PDF電子書免費下載

PCB電路板維修入門教程之二極管與電感

下面小編給大家分享一下PCB電路板維修入門教程之二極管與電感: 晶體二極管在電路中常用D加數字表示,....
的頭像 PCB線路板打樣 發表于 08-11 13:01 ? 480次 閱讀
PCB電路板維修入門教程之二極管與電感

電路板維修入門教程之電容篇

下面小編主要給大家簡單分享一下電路板維修入門的教程之電容篇。 1、電容在電路中一般用C加數字表示(如....
的頭像 PCB線路板打樣 發表于 08-11 11:45 ? 666次 閱讀
電路板維修入門教程之電容篇

基于新故障模型的測試方案的研究分析

在此主要研究BS器件管腳之間的互連測試?;ミB測試采用網絡互連模型,用網絡描述電路板上的互連,把網絡之....
發表于 08-10 15:50 ? 86次 閱讀
基于新故障模型的測試方案的研究分析

高精度壓電旋轉臺可用于電子器件的無損檢測

現如今,半導體器件、印刷電路板等電子器件在很多領域都得到廣泛應用,這些電子器件的性能直接影響整個系統....
發表于 08-10 11:39 ? 165次 閱讀
高精度壓電旋轉臺可用于電子器件的無損檢測

單片機晶振電路的原理和作用圖解

還有一點,一般帶有微控制器的電路板,電路功能是否正常,是需要編寫一定的驗證程序來測試電路板的性能的,....
發表于 08-08 17:34 ? 131次 閱讀
單片機晶振電路的原理和作用圖解

淺談電路布線電路設計

在一塊電路板的上、下2端分別有n個接線柱。根據電路設計,要求用導線(i,a(i))將上端接線柱與下端....
的頭像 西西 發表于 08-08 15:33 ? 209次 閱讀
淺談電路布線電路設計

電路板電路布線設計相關問題

首先 上下各有 n 個接線柱,用 a[i] 數組表示 與 上接線柱 相連線的 下接線柱。
的頭像 西西 發表于 08-08 11:01 ? 387次 閱讀
電路板電路布線設計相關問題

潮濕引發的電路板常見故障問題

1、導致電路板中電路參數發生改變引發電路板故障; 2、引發電路板中電路處于短路狀態,致使電路板故障....
發表于 08-08 10:00 ? 433次 閱讀
潮濕引發的電路板常見故障問題

淺談直線電機在3C電子領域中的實際應用

所謂3C電子行業即與計算機、通信以及消費類電子產品相關的行業,隨著直線電機地飛速發展,其加持得各類先....
發表于 08-07 08:09 ? 117次 閱讀
淺談直線電機在3C電子領域中的實際應用

幾個常見的Python庫資料合集免費下載

對于數值型數據, NumPy數組在存儲和處理數據時要比內置的Python數據結構高效得多。此外,由低....
發表于 08-06 17:27 ? 57次 閱讀
幾個常見的Python庫資料合集免費下載

印刷電路板行業的壓板機油冷卻操作及保養說明

印刷電路板行業(壓板機油冷卻)節能機組采用優質進口雙螺桿壓縮機:蒸汽壓縮冷水機組包括四個主要組成部分....
的頭像 PCB線路板打樣 發表于 08-06 10:37 ? 407次 閱讀
印刷電路板行業的壓板機油冷卻操作及保養說明

PCB板常見缺陷分析之電路板常見焊接缺陷

下面就常見的焊接缺陷、外觀特點、危害、原因分析進行詳細說明。 一、虛焊 1、外觀特點 焊錫與元器件引....
的頭像 PCB線路板打樣 發表于 08-06 07:14 ? 717次 閱讀
PCB板常見缺陷分析之電路板常見焊接缺陷

九江仁創藝電路板項目投資10億正式開工建設

該項目總投資10億元,總建筑面積7.2萬平方米,分兩期建設,其中一期興建年產100萬平方米高精密多層....
的頭像 PCB線路板打樣 發表于 08-05 17:04 ? 526次 閱讀
九江仁創藝電路板項目投資10億正式開工建設

ILS 3D打印技術可以在同一打印運行中燒結多種粉末

近年來,許多增材制造公司都采用了自己的方法來優化SLS印刷。這些3D打印機通常與傳統的SLS機器相似....
發表于 08-05 10:03 ? 205次 閱讀
ILS 3D打印技術可以在同一打印運行中燒結多種粉末

印刷電路板焊接工藝規范細則說明

下面小編給大家分享一下印刷電路板焊接工藝守則: PCB板(電路板)元器件、電線焊接時,焊錫絲的選型;....
的頭像 PCB線路板打樣 發表于 08-04 16:20 ? 561次 閱讀
印刷電路板焊接工藝規范細則說明

如何設計一個帶有3個Kintex 160設備的電路板?

我正在設計一個帶有3個Kintex 160設備的電路板。 我想添加備用電池。 我可以將所有球棒輸入連接在一起并放置一塊電池嗎? 謝...
發表于 08-04 10:48 ? 0次 閱讀
如何設計一個帶有3個Kintex 160設備的電路板?

家電市場增長乏力 殃及池魚PCB產業相關廠商

伴隨5G、AI等技術加速落地,智能家電市場爆發指日可待,此時家電用PCB廠商可早作準備;
的頭像 PCB線路板打樣 發表于 08-03 18:20 ? 1706次 閱讀
家電市場增長乏力 殃及池魚PCB產業相關廠商

領先的智能感知技術和方案應對工業人工智能應用挑戰 第二篇

通過對多種模式和AI處理的投資,也使得安森美半導體具備獨特的優勢,從僅提供三種紅綠藍(RGB)組成的....
的頭像 安森美半導體 發表于 08-03 15:01 ? 340次 閱讀
領先的智能感知技術和方案應對工業人工智能應用挑戰 第二篇

PCB布局心得,助你進階成為畫板達人!

單片機的模擬參考輸入端AREF要接電解電容濾波,而且要接模擬地,模擬地(AGND)與一般地(GND)....
的頭像 張飛實戰電子 發表于 08-03 09:12 ? 433次 閱讀
PCB布局心得,助你進階成為畫板達人!

機器人被視為是人類員工完成手動機械操作之外的補充

“對我們來說,彎曲加工是一項關鍵性技術,因為其中我們結合了對零部件的結構設計取代兩個或三個零部件,我....
發表于 08-01 08:59 ? 205次 閱讀
機器人被視為是人類員工完成手動機械操作之外的補充

請問如何使用您的電路板文件在Cadence的Orcad Capture中重繪原理圖?

我買了你的kc705并下載了你的電路板文件。 我想使用Cadence的Orcad捕獲來重繪原理圖。 我怎樣才能做到這一點? 你有Orcad捕...
發表于 07-30 14:24 ? 0次 閱讀
請問如何使用您的電路板文件在Cadence的Orcad Capture中重繪原理圖?

在電路板上輸出音頻流的方法?

我正在考慮將Virtex 7用于我正在考慮的項目,但我需要輸出一些音頻而我無法在電路板上找到音頻輸出端口。 有誰知道在電路板上輸...
發表于 07-27 11:02 ? 0次 閱讀
在電路板上輸出音頻流的方法?

戴爾筆記本主板LA-9104P的電路原理圖

戴爾筆記本主板LA-9104P的電路原理圖
發表于 07-26 08:30 ? 1515次 閱讀
戴爾筆記本主板LA-9104P的電路原理圖

AOZ1094DI-EVB,評估板是完全組裝和測試的電路板

AOZ1094DI-EVB,評估板是完全組裝和測試的電路板,采用AOZ1094DI降壓穩壓器IC構建。它輸出高達5A的連續電流...
發表于 07-17 15:45 ? 1212次 閱讀
AOZ1094DI-EVB,評估板是完全組裝和測試的電路板

Kintex-7未使用的高性能引腳怎么辦

你好, 我在我的電路板設計中使用了Kintex-7 FPGA,只使用了HIGH RANGE bank。 高性能I / O引腳應該怎么辦? ...
發表于 07-17 13:53 ? 0次 閱讀
Kintex-7未使用的高性能引腳怎么辦

K7 FPGA來設計電路板,連接引腳時應注意什么?

嗨XILINX工程師 我正在使用您的K7 FPGA來設計電路板。 在我的項目中,我將使用DDR3來消耗內存。 我將使用SO-...
發表于 07-16 09:06 ? 101次 閱讀
K7 FPGA來設計電路板,連接引腳時應注意什么?

LTC3400將單節輸入轉換為3.3V的同步升壓轉換器

電路顯示LTC3400將單節輸入轉換為3.3V,同時占用最小量的電路板空間...
發表于 07-15 09:27 ? 126次 閱讀
LTC3400將單節輸入轉換為3.3V的同步升壓轉換器

如何使用virtex4 fx60設計一塊電路板

你好 我目前正在使用virtex4 fx60設計一塊電路板。 我不會在我的設計中使用Rocket IO收發器。 我對未使用的火箭IOs pin有...
發表于 07-13 16:02 ? 17次 閱讀
如何使用virtex4 fx60設計一塊電路板

這個電路分為幾個部分

求解答這個電路分為幾個部分,每個部分的作用,以及整個電路原理...
發表于 06-28 19:27 ? 304次 閱讀
這個電路分為幾個部分
山东十一选五彩乐乐