基于回溯算法的計算機(jī)機(jī)箱線路板排列問題的分析研究

劉引濤

摘 要： 針對計算機(jī)微型化的發(fā)展需求，為了有效節(jié)約計算機(jī)機(jī)箱的空間和大小，利用回溯算法的搜索問題解空間的排列樹，深度優(yōu)化策略，采用優(yōu)先隊(duì)列式分支限界法找出所給電路板的最小密度布局，研究計算機(jī)機(jī)箱線路板中的線路排列問題，找出有效解決計算機(jī)機(jī)箱中線路板及其插線在機(jī)箱中的合理排列方法。經(jīng)過程序驗(yàn)證，提出的回溯算法解決了計算機(jī)機(jī)箱線路板排列問題，對于給定線路板連接條件（連接塊），確定線路板的最佳排列，使其具有最小的密度的方法是可行的。

關(guān)鍵字： 回溯算法； 線路板排列； 計算機(jī)微型化； 計算機(jī)機(jī)箱

中圖分類號： TN710?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2014）18?0084?02

Analysis based on backtracking algorithm of wiring board arrangement

problems in computer cabinet

LIU Yin?tao

（ School of Information Engineering， Shaanxi Polytechnic Institute， Xianyang 712000， China ）

Abstract： in order to meet the development demand of computer miniaturization and effectively save computer cabinet space， the priority queue branch and bound method is used to get the minimum density layout of the circuit board by the depth optimization strategy of the search solution space arrangement trees of the backtracking algorithm. The circuit board arrangement problem existing in the computer case circuit is researched to find out the reasonable arrangement method of the circuit board and plug wire in the computer case. After verification， the backtracking algorithm to solve the issue of the circuit board arrangement in computer case was determined. the minimum density method with the given circuit board connection conditions and the determined optimal arrangement of circuit board is feasible.

Keywords： backtracking algorithm； circuit board arrangement； computer miniaturization； computer cabinet

0 引 言

回溯法可以系統(tǒng)地搜索一個問題的所有解或任一解，其是一種即帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在問題的解空間樹中，按深度優(yōu)先策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時，先判斷該節(jié)點(diǎn)是否包含問題的解。如果不包含，則跳過對以該節(jié)點(diǎn)為根的子樹的搜索，逐層向其他祖先節(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按照深度優(yōu)先策略搜索?；厮莘ㄇ髥栴}的所有解時，要回溯到根，且根節(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束?；厮莘ㄇ髥栴}的一個解時，只要搜索到問題的一個解就可結(jié)束。這種以深度優(yōu)先方式系統(tǒng)搜索問題的算法稱為回溯法，它用于求解組合數(shù)大的問題。

1 問題描述

計算機(jī)機(jī)箱中的線路板排列問題是為了有效的節(jié)約機(jī)箱的空間和大小的實(shí)際問題，為了有效解決線路板及其插線在機(jī)箱中的合理排列，先提出以下解決方案：將N塊線路板以最佳排列方案插入帶有N個插槽的計算機(jī)機(jī)箱中，N塊線路板的不同排列方式對應(yīng)于不同的線路板插入方案。

設(shè)B={1，2，…，N}是N塊線路板的集合。集合L={N1，N2，…，Nm}是N塊線路板的m個連接塊。其中每個連接塊Ni是B的一個子集，且Ni中的線路板用同一根導(dǎo)線連接在一起。

設(shè)N=8，M=5。給定的N塊線路板及其m個連接塊如下：

B={1，2，3，4，5，6，7，8}；L={N1，N2，N3，N4，N5}；

N1={4，5，6}；N2={2，3}；N3={1，3}；N4={3，6}；

N5={7，8}；

這8塊線路板的一個排列（如圖1所示）。

圖1 線路板排列

設(shè)X表示N塊線路板的排列，即在機(jī)箱的第i個插槽中插入線路板x[i]。x所確定的線路板排列密度density（x）定義為跨越相鄰線路板插槽的最大連線數(shù)。

在圖1中線路板排列的密度為2，跨越插槽2和3，插槽4和5以及插槽5和6的連線數(shù)均為2，插槽6和7之間無跨越連線。其余相鄰插槽之間都只有1條跨越連線。在設(shè)計機(jī)箱時，插槽一側(cè)的布線間隙由線路板排列的密度所確定。因此線路板排列問題要求對于給定線路板連接條件（連接塊），確定線路板的最佳排列，使其具有最小密度。

2 算法設(shè)計

線路板排列問題是NP難問題，因此不大可能找到解決此問題的多項(xiàng)式時間算法。通過系統(tǒng)搜索線路板排列問題所相應(yīng)解空間的排列樹，找出線路板最佳排列。

算法中用整形數(shù)組b表示輸入。B[i][j]的值為1當(dāng)且僅當(dāng)線路板i在連接塊Nj中。設(shè)total[j]是連接塊Nj中的線路板數(shù)。對于線路板的部分排列x[1：i]，設(shè)now[j]是x[1：i]中所包含的Nj中的線路板數(shù)。由此可知，連接塊Nj的連線跨越插槽i和i+1當(dāng)且僅當(dāng)now[j]>0且now[j]≠total[j]?？梢岳眠@個條件來計算插槽i和插槽i+1間的連線密度。

在算法backtrack中，當(dāng)i=n時，所有n塊線路板都已排定，其密度為cd。由于算法僅完成比當(dāng)前最優(yōu)解更好的排列，故cd肯定優(yōu)于bestd。此時應(yīng)更新bestd。

當(dāng)i

按上述的回溯搜索策略設(shè)計的解線路板排列問題的算法可描述如下。

Public class Board

{ Static int n； //線路板數(shù)

Static int m； //連接塊數(shù)

Static int [] x； //當(dāng)前解

Static int [] best x； //當(dāng)前最優(yōu)解

Static int [] total； // total[j]=連接塊j的線路板數(shù)

Static int [] now； //now[j]=當(dāng)前解中所含連接塊j的線 路板數(shù)

Static int bestd； //當(dāng)前最優(yōu)密度

Static int [][]b； //連接塊數(shù)組

Public static int arrange（int [][]bb， int mm， int []xx）

//初始化

…

//置x為單位排列

//計算total[]

For （int i=1；i<=n；i++）

{ x [i]=I；

For （int j=1；j<=m；j++）

total[j]+=b[i][j] }

//回溯搜索

Backtrack（1，0）；

Return bestd；}

…

Public static void Backtrack（int I ，int dd）

{if （i==n）

…

For （int j=1；j<=n；j++）

{//選擇x[j]為下一塊線路板

Int d==0；

For （int k=1k<=m；k++）

{now[k]+=b[x[j]][k]；

If （now[k]>0&&total[k]！=now[k]）d++；}

//更新d值

…

3 結(jié)果輸出

在解空間排列樹的每個結(jié)點(diǎn)處，算法Backtrack花費(fèi)O（m）計算時間為每個兒子結(jié)點(diǎn)計算密度。因此計算所耗費(fèi)的總計算時間為O（mn?。?。另外，生成排列樹所需O（n?。r間。每次更新當(dāng)前最優(yōu)解至少使bestd減少1，而算法運(yùn)行結(jié)束時bestd≥0。因此最優(yōu)解被更新的次數(shù)為O（m）。更新當(dāng)前最優(yōu)解需O（mn）時間。

終上所述，解線路板排列問題的回溯算法Backtrack所需的計算時間為O（mn！），如圖2所示。

4 結(jié) 語

通過利用回溯算法，對計算機(jī)機(jī)箱線路板中的線路排列問題進(jìn)行分析研究，有效節(jié)約計算機(jī)中的機(jī)箱空間和大小，合理對計算機(jī)線路板及其插線在機(jī)箱中的最佳排列，提出可供參考的計算機(jī)線路板最佳排列組合方案。

圖2 解線路板排列問題計算時間

參考文獻(xiàn)

[1] 王鵬，邱楓，張為華，等.一種任意維Line?Sweep計算的數(shù)據(jù)劃分算法[J].計算機(jī)學(xué)報，2012（12）：2573?2586.

[2] 包乃蘭，寧立革.基于雙路CAN總線的通信板卡設(shè)計與實(shí)現(xiàn)[J].計算機(jī)測量與控制，2011（11）：2772?2774.

[3] 王龍.關(guān)于下一代加固計算機(jī)總線選擇的分析[J].數(shù)字技術(shù)與應(yīng)用，2011（8）：223?224.

[4] 靳曉麗，吳蓉，張愛華.基于Pro/E的插箱自動化設(shè)計[J].新技術(shù)新工藝，2010（3）：20?24.

[5] 趙得成，柴英杰.標(biāo)準(zhǔn)通信機(jī)柜的結(jié)構(gòu)創(chuàng)新與造型設(shè)計[J].機(jī)械設(shè)計與制造，2006（10）：135?137.

[6] BARTOS F J，酈杭川.板卡設(shè)計技術(shù)[J].軟件，2007（1）：122?127.

2 算法設(shè)計

線路板排列問題是NP難問題，因此不大可能找到解決此問題的多項(xiàng)式時間算法。通過系統(tǒng)搜索線路板排列問題所相應(yīng)解空間的排列樹，找出線路板最佳排列。

算法中用整形數(shù)組b表示輸入。B[i][j]的值為1當(dāng)且僅當(dāng)線路板i在連接塊Nj中。設(shè)total[j]是連接塊Nj中的線路板數(shù)。對于線路板的部分排列x[1：i]，設(shè)now[j]是x[1：i]中所包含的Nj中的線路板數(shù)。由此可知，連接塊Nj的連線跨越插槽i和i+1當(dāng)且僅當(dāng)now[j]>0且now[j]≠total[j]?？梢岳眠@個條件來計算插槽i和插槽i+1間的連線密度。

在算法backtrack中，當(dāng)i=n時，所有n塊線路板都已排定，其密度為cd。由于算法僅完成比當(dāng)前最優(yōu)解更好的排列，故cd肯定優(yōu)于bestd。此時應(yīng)更新bestd。

當(dāng)i

按上述的回溯搜索策略設(shè)計的解線路板排列問題的算法可描述如下。

Public class Board

{ Static int n； //線路板數(shù)

Static int m； //連接塊數(shù)

Static int [] x； //當(dāng)前解

Static int [] best x； //當(dāng)前最優(yōu)解

Static int [] total； // total[j]=連接塊j的線路板數(shù)

Static int [] now； //now[j]=當(dāng)前解中所含連接塊j的線 路板數(shù)

Static int bestd； //當(dāng)前最優(yōu)密度

Static int [][]b； //連接塊數(shù)組

Public static int arrange（int [][]bb， int mm， int []xx）

//初始化

…

//置x為單位排列

//計算total[]

For （int i=1；i<=n；i++）

{ x [i]=I；

For （int j=1；j<=m；j++）

total[j]+=b[i][j] }

//回溯搜索

Backtrack（1，0）；

Return bestd；}

…

Public static void Backtrack（int I ，int dd）

{if （i==n）

…

For （int j=1；j<=n；j++）

{//選擇x[j]為下一塊線路板

Int d==0；

For （int k=1k<=m；k++）

{now[k]+=b[x[j]][k]；

If （now[k]>0&&total[k]！=now[k]）d++；}

//更新d值

…

3 結(jié)果輸出

在解空間排列樹的每個結(jié)點(diǎn)處，算法Backtrack花費(fèi)O（m）計算時間為每個兒子結(jié)點(diǎn)計算密度。因此計算所耗費(fèi)的總計算時間為O（mn?。?。另外，生成排列樹所需O（n?。r間。每次更新當(dāng)前最優(yōu)解至少使bestd減少1，而算法運(yùn)行結(jié)束時bestd≥0。因此最優(yōu)解被更新的次數(shù)為O（m）。更新當(dāng)前最優(yōu)解需O（mn）時間。

終上所述，解線路板排列問題的回溯算法Backtrack所需的計算時間為O（mn?。?，如圖2所示。

4 結(jié) 語

通過利用回溯算法，對計算機(jī)機(jī)箱線路板中的線路排列問題進(jìn)行分析研究，有效節(jié)約計算機(jī)中的機(jī)箱空間和大小，合理對計算機(jī)線路板及其插線在機(jī)箱中的最佳排列，提出可供參考的計算機(jī)線路板最佳排列組合方案。

圖2 解線路板排列問題計算時間

參考文獻(xiàn)

[1] 王鵬，邱楓，張為華，等.一種任意維Line?Sweep計算的數(shù)據(jù)劃分算法[J].計算機(jī)學(xué)報，2012（12）：2573?2586.

[2] 包乃蘭，寧立革.基于雙路CAN總線的通信板卡設(shè)計與實(shí)現(xiàn)[J].計算機(jī)測量與控制，2011（11）：2772?2774.

[3] 王龍.關(guān)于下一代加固計算機(jī)總線選擇的分析[J].數(shù)字技術(shù)與應(yīng)用，2011（8）：223?224.

[4] 靳曉麗，吳蓉，張愛華.基于Pro/E的插箱自動化設(shè)計[J].新技術(shù)新工藝，2010（3）：20?24.

[5] 趙得成，柴英杰.標(biāo)準(zhǔn)通信機(jī)柜的結(jié)構(gòu)創(chuàng)新與造型設(shè)計[J].機(jī)械設(shè)計與制造，2006（10）：135?137.

[6] BARTOS F J，酈杭川.板卡設(shè)計技術(shù)[J].軟件，2007（1）：122?127.

2 算法設(shè)計

線路板排列問題是NP難問題，因此不大可能找到解決此問題的多項(xiàng)式時間算法。通過系統(tǒng)搜索線路板排列問題所相應(yīng)解空間的排列樹，找出線路板最佳排列。

算法中用整形數(shù)組b表示輸入。B[i][j]的值為1當(dāng)且僅當(dāng)線路板i在連接塊Nj中。設(shè)total[j]是連接塊Nj中的線路板數(shù)。對于線路板的部分排列x[1：i]，設(shè)now[j]是x[1：i]中所包含的Nj中的線路板數(shù)。由此可知，連接塊Nj的連線跨越插槽i和i+1當(dāng)且僅當(dāng)now[j]>0且now[j]≠total[j]?？梢岳眠@個條件來計算插槽i和插槽i+1間的連線密度。

在算法backtrack中，當(dāng)i=n時，所有n塊線路板都已排定，其密度為cd。由于算法僅完成比當(dāng)前最優(yōu)解更好的排列，故cd肯定優(yōu)于bestd。此時應(yīng)更新bestd。

當(dāng)i

按上述的回溯搜索策略設(shè)計的解線路板排列問題的算法可描述如下。

Public class Board

{ Static int n； //線路板數(shù)

Static int m； //連接塊數(shù)

Static int [] x； //當(dāng)前解

Static int [] best x； //當(dāng)前最優(yōu)解

Static int [] total； // total[j]=連接塊j的線路板數(shù)

Static int [] now； //now[j]=當(dāng)前解中所含連接塊j的線 路板數(shù)

Static int bestd； //當(dāng)前最優(yōu)密度

Static int [][]b； //連接塊數(shù)組

Public static int arrange（int [][]bb， int mm， int []xx）

//初始化

…

//置x為單位排列

//計算total[]

For （int i=1；i<=n；i++）

{ x [i]=I；

For （int j=1；j<=m；j++）

total[j]+=b[i][j] }

//回溯搜索

Backtrack（1，0）；

Return bestd；}

…

Public static void Backtrack（int I ，int dd）

{if （i==n）

…

For （int j=1；j<=n；j++）

{//選擇x[j]為下一塊線路板

Int d==0；

For （int k=1k<=m；k++）

{now[k]+=b[x[j]][k]；

If （now[k]>0&&total[k]！=now[k]）d++；}

//更新d值

…

3 結(jié)果輸出

在解空間排列樹的每個結(jié)點(diǎn)處，算法Backtrack花費(fèi)O（m）計算時間為每個兒子結(jié)點(diǎn)計算密度。因此計算所耗費(fèi)的總計算時間為O（mn?。?。另外，生成排列樹所需O（n?。r間。每次更新當(dāng)前最優(yōu)解至少使bestd減少1，而算法運(yùn)行結(jié)束時bestd≥0。因此最優(yōu)解被更新的次數(shù)為O（m）。更新當(dāng)前最優(yōu)解需O（mn）時間。

終上所述，解線路板排列問題的回溯算法Backtrack所需的計算時間為O（mn！），如圖2所示。

4 結(jié) 語

通過利用回溯算法，對計算機(jī)機(jī)箱線路板中的線路排列問題進(jìn)行分析研究，有效節(jié)約計算機(jī)中的機(jī)箱空間和大小，合理對計算機(jī)線路板及其插線在機(jī)箱中的最佳排列，提出可供參考的計算機(jī)線路板最佳排列組合方案。

圖2 解線路板排列問題計算時間

參考文獻(xiàn)

[1] 王鵬，邱楓，張為華，等.一種任意維Line?Sweep計算的數(shù)據(jù)劃分算法[J].計算機(jī)學(xué)報，2012（12）：2573?2586.

[2] 包乃蘭，寧立革.基于雙路CAN總線的通信板卡設(shè)計與實(shí)現(xiàn)[J].計算機(jī)測量與控制，2011（11）：2772?2774.

[3] 王龍.關(guān)于下一代加固計算機(jī)總線選擇的分析[J].數(shù)字技術(shù)與應(yīng)用，2011（8）：223?224.

[4] 靳曉麗，吳蓉，張愛華.基于Pro/E的插箱自動化設(shè)計[J].新技術(shù)新工藝，2010（3）：20?24.

[5] 趙得成，柴英杰.標(biāo)準(zhǔn)通信機(jī)柜的結(jié)構(gòu)創(chuàng)新與造型設(shè)計[J].機(jī)械設(shè)計與制造，2006（10）：135?137.

[6] BARTOS F J，酈杭川.板卡設(shè)計技術(shù)[J].軟件，2007（1）：122?127.