C++用分支限界法求解最短布线问题(共7页).doc

精选优质文档-倾情为你奉上实验六 用分支限界法求解最短布线问题学院： 计算机科学与技术 专业：计算机科学与技术学号： 班级： 姓名： （本程序在的环境下实现）一、实验内容：布线问题：印刷电路板将布线区域划分成nm个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。实验要求：用分支限界法解此最短布线问题。分支限界法类似回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但分支限界法只找出满足约束条件的一个最优解，并且以广度优先或最小耗费优先的方式搜索解空间树T。树T是一棵子集树或排列树。在搜索时，每个结点只有一次机会成为扩展结点，并且一次性产生其所有儿子结点。从活结点表中选择下一扩展结点有两种方式：（1）队列式（FIFO） （2）优先队列式。分支限界法可广泛应用于单源最短路径问题，最大团问题，布线