当前位置:  编程技术>c/c++/嵌入式

算法详解之分支限界法的具体实现

    来源: 互联网  发布时间:2014-10-23

    本文导语:  首先我们来关注一个问题: 问题描述: 布线问题:印刷电路板将布线区域划分成n×m个方格阵列,要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时,电路只能沿直线或直角布线,为了避免线路...

首先我们来关注一个问题:

问题描述:

布线问题:印刷电路板将布线区域划分成n×m个方格阵列,要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时,电路只能沿直线或直角布线,为了避免线路相交,已布了线的方格做了封锁标记,其他线路不允许穿过被封锁的方格。如下图所示:

 

算法思路:

布线问题的解空间是一个图,则从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并可达的方格成为可行结点被加入到活结点队列中,并且将这些方格标记为1,即从起始方格a到这些方格的距离为1。接着,从活结点队列中取出队首结点作为下一个扩展结点,并将与当前扩展结点相邻且未标记过的方格标记为2,并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。

在实现上述算法时,

(1) 定义一个表示电路板上方格位置的类Position。

它的2个成员row和col分别表示方格所在的行和列。在方格处,布线可沿右、下、左、上4个方向进行。沿这4个方向的移动分别记为0,1,2,3。下表中,offset[i].row和offset[i].col(i= 0,1,2,3)分别给出沿这4个方向前进1步相对于当前方格的相对位移。

(2) 用二维数组grid表示所给的方格阵列。

初始时,grid[i][j] = 0, 表示该方格允许布线,而grid[i][j] = 1表示该方格被封锁,不允许布线。

算法图解:

代码贴出来:

代码如下:

#include
typedef struct {
  int row;
  int col;
}Position;
int FindPath (Position start, Position finish, int &PathLen, Position *&path)
{ //计算从起始位置start到目标位置finish的最短布线路径,找到返回1,否则,返回0
  int  i;
  if ((start.row = = finish.row) && (start.col = = finish.col)) {
PathLen = 0;   return 0; } //start = finish
  //设置方格阵列”围墙”
  for (i = 0; i

    
 
 

您可能感兴趣的文章:

 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 一种求正整数幂的高效算法详解
  • 深入串的模式匹配算法(普通算法和KMP算法)的详解
  • 解析C#彩色图像灰度化算法的实现代码详解
  • 使用Deflate算法对文件进行压缩与解压缩的方法详解
  • 深入第K大数问题以及算法概要的详解
  • 字符串的模式匹配详解--BF算法与KMP算法
  • 算法之排列算法与组合算法详解
  • 采用C++实现区间图着色问题(贪心算法)实例详解
  • 算法详解之分治法具体实现
  • C语言位图算法详解
  • 算法详解之回溯法具体实现
  • 基于一致性hash算法(consistent hashing)的使用详解
  • 算法详解之回溯法具体实现 iis7站长之家
  • 基于稀疏图上的Johnson算法的详解
  • 基于一致性hash算法 C++语言的实现详解
  • 深入N皇后问题的两个最高效算法的详解
  • 使用C++实现全排列算法的方法详解
  • <<大话数据结构>>中冒泡排序算法改进
  • 那位高人有任务分配问题的禁忌搜索算法、模拟退火算法的算法实现程序啊
  • 二叉树常用算法(求总节点个数和叶子节点个数)
  • 求对称加密DES算法与非对称加密RSA算法!(可用)
  • boost unordered_map和std::list相结合的实现LRU算法
  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
  • 中文网页快速去重算法研究
  • 谁能给出一个最快最高效的求素数的算法?(高分求算法)
  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • 谁有这样的算法:给定两个区域,用直线或折线来连接,以及移动其中线段的算法。
  • 广告系统中weak-and算法原理及编码验证
  • 算法之排序算法的算法思想和使用场景总结
  • c++实现MD5算法代码示例
  • 【算法】扑克发牌算法实现




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3