劉引濤

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

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

中圖分類號(hào)： TN710?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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)地搜索一個(gè)問(wèn)題的所有解或任一解，其是一種即帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任一結(jié)點(diǎn)時(shí)，先判斷該節(jié)點(diǎn)是否包含問(wèn)題的解。如果不包含，則跳過(guò)對(duì)以該節(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其他祖先節(jié)點(diǎn)回溯。否則，進(jìn)入該子樹(shù)，繼續(xù)按照深度優(yōu)先策略搜索。回溯法求問(wèn)題的所有解時(shí)，要回溯到根，且根節(jié)點(diǎn)的所有子樹(shù)都已被搜索遍才結(jié)束?；厮莘ㄇ髥?wèn)題的一個(gè)解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可結(jié)束。這種以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題的算法稱為回溯法，它用于求解組合數(shù)大的問(wèn)題。

1 問(wèn)題描述

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

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

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

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塊線路板的一個(gè)排列（如圖1所示）。

圖1 線路板排列

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

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

2 算法設(shè)計(jì)

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

算法中用整形數(shù)組b表示輸入。B[i][j]的值為1當(dāng)且僅當(dāng)線路板i在連接塊Nj中。設(shè)total[j]是連接塊Nj中的線路板數(shù)。對(duì)于線路板的部分排列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]?？梢岳眠@個(gè)條件來(lái)計(jì)算插槽i和插槽i+1間的連線密度。

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

當(dāng)i

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

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為單位排列

//計(jì)算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é)果輸出

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

終上所述，解線路板排列問(wèn)題的回溯算法Backtrack所需的計(jì)算時(shí)間為O（mn！），如圖2所示。

4 結(jié) 語(yǔ)

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

圖2 解線路板排列問(wèn)題計(jì)算時(shí)間

參考文獻(xiàn)

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

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

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

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

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

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

2 算法設(shè)計(jì)

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

算法中用整形數(shù)組b表示輸入。B[i][j]的值為1當(dāng)且僅當(dāng)線路板i在連接塊Nj中。設(shè)total[j]是連接塊Nj中的線路板數(shù)。對(duì)于線路板的部分排列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]?？梢岳眠@個(gè)條件來(lái)計(jì)算插槽i和插槽i+1間的連線密度。

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

當(dāng)i

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

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為單位排列

//計(jì)算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é)果輸出

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

終上所述，解線路板排列問(wèn)題的回溯算法Backtrack所需的計(jì)算時(shí)間為O（mn?。?，如圖2所示。

4 結(jié) 語(yǔ)

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

圖2 解線路板排列問(wèn)題計(jì)算時(shí)間

參考文獻(xiàn)

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

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

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

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

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

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

2 算法設(shè)計(jì)

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

算法中用整形數(shù)組b表示輸入。B[i][j]的值為1當(dāng)且僅當(dāng)線路板i在連接塊Nj中。設(shè)total[j]是連接塊Nj中的線路板數(shù)。對(duì)于線路板的部分排列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]?？梢岳眠@個(gè)條件來(lái)計(jì)算插槽i和插槽i+1間的連線密度。

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

當(dāng)i

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

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為單位排列

//計(jì)算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é)果輸出

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

終上所述，解線路板排列問(wèn)題的回溯算法Backtrack所需的計(jì)算時(shí)間為O（mn?。?，如圖2所示。

4 結(jié) 語(yǔ)

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

圖2 解線路板排列問(wèn)題計(jì)算時(shí)間

參考文獻(xiàn)

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

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

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

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

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

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