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

点赞:22230 浏览:97708 近期更新时间:2024-03-24 作者:网友分享原创网站原创

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

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

中图分类号:TN71034文献标识码:A文章编号:1004373X(2014)18008402

Analysisbasedonbacktrackingalgorithmofwiringboardarrangement

problemsinputercabi

LIUYintao

(SchoolofInformationEngineering,ShaanxiPolytechnicInstitute,Xianyang712000,China)

Abstract:inordertomeetthedevelopmentdemandofputerminiaturizationandeffectivelyseputercabispace,thepriorityqueuebranchandboundmethodisusedtogettheminimumdensitylayoutofthecircuitboardbythedepthoptimizationstrategyofthesearchsolutionspacearrangementtreesofthebacktrackingalgorithm.Thecircuitboardarrangementproblemexistingintheputercasecircuitisresearchedtofindoutthereasonablearrangementmethodofthecircuitboardandplugwireintheputercase.Afterverification,thebacktrackingalgorithmtosolvetheissueofthecircuitboardarrangementinputercasewasdetermined.theminimumdensitymethodwiththegivencircuitboardconnectionconditionsandthedeterminedoptimalarrangementofcircuitboardieasible.

Keywords:backtrackingalgorithm;circuitboardarrangement;puterminiaturization;putercabi

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

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

PublicclassBoard

{Staticintn;//线路板数

Staticintm;//连接块数

Staticint[]x;//当前解

Staticint[]bestx;//当前最优解

Staticint[]total;//total[j]等于连接块j的线路板数

Staticint[]now;//now[j]等于当前解中所含连接块j的线路板数

Staticintbestd;//当前最优密度

Staticint[][]b;//连接块数组

Publicstaticintarrange(int[][]bb,intmm,int[]xx)

//初始化

//置x为单位排列


//计算total[]

For(inti等于1;i<=n;i++)

{x[i]等于I;

For(intj等于1;j<=m;j++)

total[j]+等于b[i][j]}

//回溯搜索

Backtrack(1,0);

Returnbestd;}

PublicstaticvoidBacktrack(intI,intdd)

{if(i等于等于n)

For(intj等于1;j<=n;j++)

{//选择x[j]为下一块线路板

Intd等于等于0;

For(intk等于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解线路板排列问题计算时间