基于回溯算法的计算机机箱线路板排列问题的分析研究

刘引涛

摘 要： 针对计算机微型化的发展需求，为了有效节约计算机机箱的空间和大小，利用回溯算法的搜索问题解空间的排列树，深度优化策略，采用优先队列式分支限界法找出所给电路板的最小密度布局，研究计算机机箱线路板中的线路排列问题，找出有效解决计算机机箱中线路板及其插线在机箱中的合理排列方法。经过程序验证，提出的回溯算法解决了计算机机箱线路板排列问题，对于给定线路板连接条件（连接块），确定线路板的最佳排列，使其具有最小的密度的方法是可行的。

关键字： 回溯算法； 线路板排列； 计算机微型化； 计算机机箱

中图分类号： TN710?34 文献标识码： 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 引 言

回溯法可以系统地搜索一个问题的所有解或任一解，其是一种即带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该节点是否包含问题的解。如果不包含，则跳过对以该节点为根的子树的搜索，逐层向其他祖先节点回溯。否则，进入该子树，继续按照深度优先策略搜索。回溯法求问题的所有解时，要回溯到根，且根节点的所有子树都已被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题的算法称为回溯法，它用于求解组合数大的问题。

1 问题描述

计算机机箱中的线路板排列问题是为了有效的节约机箱的空间和大小的实际问题，为了有效解决线路板及其插线在机箱中的合理排列，先提出以下解决方案：将N块线路板以最佳排列方案插入带有N个插槽的计算机机箱中，N块线路板的不同排列方式对应于不同的线路板插入方案。

设B={1，2，…，N}是N块线路板的集合。集合L={N1，N2，…，Nm}是N块线路板的m个连接块。其中每个连接块Ni是B的一个子集，且Ni中的线路板用同一根导线连接在一起。

设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 线路板排列

设X表示N块线路板的排列，即在机箱的第i个插槽中插入线路板x[i]。x所确定的线路板排列密度density（x）定义为跨越相邻线路板插槽的最大连线数。

在图1中线路板排列的密度为2，跨越插槽2和3，插槽4和5以及插槽5和6的连线数均为2，插槽6和7之间无跨越连线。其余相邻插槽之间都只有1条跨越连线。在设计机箱时，插槽一侧的布线间隙由线路板排列的密度所确定。因此线路板排列问题要求对于给定线路板连接条件（连接块），确定线路板的最佳排列，使其具有最小密度。

2 算法设计

线路板排列问题是NP难问题，因此不大可能找到解决此问题的多项式时间算法。通过系统搜索线路板排列问题所相应解空间的排列树，找出线路板最佳排列。

算法中用整形数组b表示输入。B[i][j]的值为1当且仅当线路板i在连接块Nj中。设total[j]是连接块Nj中的线路板数。对于线路板的部分排列x[1：i]，设now[j]是x[1：i]中所包含的Nj中的线路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当now[j]>0且now[j]≠total[j]。可以利用这个条件来计算插槽i和插槽i+1间的连线密度。

在算法backtrack中，当i=n时，所有n块线路板都已排定，其密度为cd。由于算法仅完成比当前最优解更好的排列，故cd肯定优于bestd。此时应更新bestd。

当i

按上述的回溯搜索策略设计的解线路板排列问题的算法可描述如下。

Public class Board

{ Static int n； //线路板数

Static int m； //连接块数

Static int [] x； //当前解

Static int [] best x； //当前最优解

Static int [] total； // total[j]=连接块j的线路板数

Static int [] now； //now[j]=当前解中所含连接块j的线 路板数

Static int bestd； //当前最优密度

Static int [][]b； //连接块数组

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 结果输出

在解空间排列树的每个结点处，算法Backtrack花费O（m）计算时间为每个儿子结点计算密度。因此计算所耗费的总计算时间为O（mn！）。另外，生成排列树所需O（n！）时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd≥0。因此最优解被更新的次数为O（m）。更新当前最优解需O（mn）时间。

终上所述，解线路板排列问题的回溯算法Backtrack所需的计算时间为O（mn！），如图2所示。

4 结 语

通过利用回溯算法，对计算机机箱线路板中的线路排列问题进行分析研究，有效节约计算机中的机箱空间和大小，合理对计算机线路板及其插线在机箱中的最佳排列，提出可供参考的计算机线路板最佳排列组合方案。

图2 解线路板排列问题计算时间

参考文献

[1] 王鹏，邱枫，张为华，等.一种任意维Line?Sweep计算的数据划分算法[J].计算机学报，2012（12）：2573?2586.

[2] 包乃兰，宁立革.基于双路CAN总线的通信板卡设计与实现[J].计算机测量与控制，2011（11）：2772?2774.

[3] 王龙.关于下一代加固计算机总线选择的分析[J].数字技术与应用，2011（8）：223?224.

[4] 靳晓丽，吴蓉，张爱华.基于Pro/E的插箱自动化设计[J].新技术新工艺，2010（3）：20?24.

[5] 赵得成，柴英杰.标准通信机柜的结构创新与造型设计[J].机械设计与制造，2006（10）：135?137.

[6] BARTOS F J，郦杭川.板卡设计技术[J].软件，2007（1）：122?127.

2 算法设计

线路板排列问题是NP难问题，因此不大可能找到解决此问题的多项式时间算法。通过系统搜索线路板排列问题所相应解空间的排列树，找出线路板最佳排列。

算法中用整形数组b表示输入。B[i][j]的值为1当且仅当线路板i在连接块Nj中。设total[j]是连接块Nj中的线路板数。对于线路板的部分排列x[1：i]，设now[j]是x[1：i]中所包含的Nj中的线路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当now[j]>0且now[j]≠total[j]。可以利用这个条件来计算插槽i和插槽i+1间的连线密度。

在算法backtrack中，当i=n时，所有n块线路板都已排定，其密度为cd。由于算法仅完成比当前最优解更好的排列，故cd肯定优于bestd。此时应更新bestd。

当i

按上述的回溯搜索策略设计的解线路板排列问题的算法可描述如下。

Public class Board

{ Static int n； //线路板数

Static int m； //连接块数

Static int [] x； //当前解

Static int [] best x； //当前最优解

Static int [] total； // total[j]=连接块j的线路板数

Static int [] now； //now[j]=当前解中所含连接块j的线 路板数

Static int bestd； //当前最优密度

Static int [][]b； //连接块数组

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 结果输出

在解空间排列树的每个结点处，算法Backtrack花费O（m）计算时间为每个儿子结点计算密度。因此计算所耗费的总计算时间为O（mn！）。另外，生成排列树所需O（n！）时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd≥0。因此最优解被更新的次数为O（m）。更新当前最优解需O（mn）时间。

终上所述，解线路板排列问题的回溯算法Backtrack所需的计算时间为O（mn！），如图2所示。

4 结 语

通过利用回溯算法，对计算机机箱线路板中的线路排列问题进行分析研究，有效节约计算机中的机箱空间和大小，合理对计算机线路板及其插线在机箱中的最佳排列，提出可供参考的计算机线路板最佳排列组合方案。

图2 解线路板排列问题计算时间

参考文献

[1] 王鹏，邱枫，张为华，等.一种任意维Line?Sweep计算的数据划分算法[J].计算机学报，2012（12）：2573?2586.

[2] 包乃兰，宁立革.基于双路CAN总线的通信板卡设计与实现[J].计算机测量与控制，2011（11）：2772?2774.

[3] 王龙.关于下一代加固计算机总线选择的分析[J].数字技术与应用，2011（8）：223?224.

[4] 靳晓丽，吴蓉，张爱华.基于Pro/E的插箱自动化设计[J].新技术新工艺，2010（3）：20?24.

[5] 赵得成，柴英杰.标准通信机柜的结构创新与造型设计[J].机械设计与制造，2006（10）：135?137.

[6] BARTOS F J，郦杭川.板卡设计技术[J].软件，2007（1）：122?127.

2 算法设计

线路板排列问题是NP难问题，因此不大可能找到解决此问题的多项式时间算法。通过系统搜索线路板排列问题所相应解空间的排列树，找出线路板最佳排列。

算法中用整形数组b表示输入。B[i][j]的值为1当且仅当线路板i在连接块Nj中。设total[j]是连接块Nj中的线路板数。对于线路板的部分排列x[1：i]，设now[j]是x[1：i]中所包含的Nj中的线路板数。由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当now[j]>0且now[j]≠total[j]。可以利用这个条件来计算插槽i和插槽i+1间的连线密度。

在算法backtrack中，当i=n时，所有n块线路板都已排定，其密度为cd。由于算法仅完成比当前最优解更好的排列，故cd肯定优于bestd。此时应更新bestd。

当i

按上述的回溯搜索策略设计的解线路板排列问题的算法可描述如下。

Public class Board

{ Static int n； //线路板数

Static int m； //连接块数

Static int [] x； //当前解

Static int [] best x； //当前最优解

Static int [] total； // total[j]=连接块j的线路板数

Static int [] now； //now[j]=当前解中所含连接块j的线 路板数

Static int bestd； //当前最优密度

Static int [][]b； //连接块数组

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 结果输出

在解空间排列树的每个结点处，算法Backtrack花费O（m）计算时间为每个儿子结点计算密度。因此计算所耗费的总计算时间为O（mn！）。另外，生成排列树所需O（n！）时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd≥0。因此最优解被更新的次数为O（m）。更新当前最优解需O（mn）时间。

终上所述，解线路板排列问题的回溯算法Backtrack所需的计算时间为O（mn！），如图2所示。

4 结 语

通过利用回溯算法，对计算机机箱线路板中的线路排列问题进行分析研究，有效节约计算机中的机箱空间和大小，合理对计算机线路板及其插线在机箱中的最佳排列，提出可供参考的计算机线路板最佳排列组合方案。

图2 解线路板排列问题计算时间

参考文献

[1] 王鹏，邱枫，张为华，等.一种任意维Line?Sweep计算的数据划分算法[J].计算机学报，2012（12）：2573?2586.

[2] 包乃兰，宁立革.基于双路CAN总线的通信板卡设计与实现[J].计算机测量与控制，2011（11）：2772?2774.

[3] 王龙.关于下一代加固计算机总线选择的分析[J].数字技术与应用，2011（8）：223?224.

[4] 靳晓丽，吴蓉，张爱华.基于Pro/E的插箱自动化设计[J].新技术新工艺，2010（3）：20?24.

[5] 赵得成，柴英杰.标准通信机柜的结构创新与造型设计[J].机械设计与制造，2006（10）：135?137.

[6] BARTOS F J，郦杭川.板卡设计技术[J].软件，2007（1）：122?127.