




全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
6.6 布线问题算法设计思想:采用分支限界法求解。首先将问题转化为一颗解空间树:树根为线头,树高为线头到线尾的格数,每个节点有4个孩子,代表下一格可以朝4个方向。这样,布线问题就是搜索从树根到代表线尾节点的一条最短路径。分支限界法的本质是对解空间树的BFS(广度优先)搜索,即每进一格就将状态入队,而后再依次将出队的每个状态的子状态入队,直到到达所求的状态节点即线尾。该问题的剪枝条件显而易见,即当遇到电路板上的封锁标记时进行剪枝。为了方便剪枝,算法开始进行了预处理,在电路板周围加上了一圈“围墙”(虚拟的封锁标记),使搜索路径时对边界的处理与对封锁标记的处理统一。因为该问题BFS的队列中,并没有明显的优先级,所以该算法采用普通队列式。除了上述三点之外,程序对鲁棒性做了增强,对非法输入和文件错误进行了检测。程序设计代码: /*头文件 布线问题.h*/#ifndef KNAP_H#define KNAP_H#include #include #include using namespace std;class position/位置类public:int row;/行坐标int column;/列坐标bool operator=(const position &b) const/重载运算符=,表示位置相同if(row = b.row & column = b.column)return true;elsereturn false;position& operator=(const position &b)/重载运算符=,位置赋值this-row = b.row;this-column = b.column;return *this;position operator+(const position &b)const/重载运算符+,表示移动一格position temp;temp.row = row + b.row;temp.column = column + b.column;return temp;class Wiring/布线类public:Wiring(char *in, char *out);/构造函数Wiring();/析构函数void Solve();/输出结果到文件protected:bool FindPath();/找出布线方案void PrintPath();/输出结果布线方案void PrintFail();/输出没有路径信息private:int n, m;/电路板行列数int *grid;/电路板格子position start, finish;/起点和终点position *nextstep;/下一步四个方向ofstream fout;/输出结果文件;#endif/*函数实现文件 布线问题.cpp*/#include 布线问题.hWiring:Wiring(char *in, char *out) : fout(out)ifstream fin(in);if( !fin )cerr 文件 in 无法打开! n m;/初始化电路板大小n*mgrid = new int*n+2;for(int i = 0; i = n+1; i+)gridi = new intm+2;if(i = 0 | i = n+1)/加上下围墙for(int j = 0; j = m+1; j+)gridij = 1;elsegridi0 = gridim+1 = 1;/加左右围墙for(int j = 1; j gridij;fin start.row start.column;/初始化起点和终点fin finish.row finish.column;fin.close();nextstep = new position4;nextstep0.row = 0; nextstep0.column = 1;/右nextstep1.row = 1; nextstep1.column = 0;/下nextstep2.row = 0; nextstep2.column = -1;/左nextstep3.row = -1; nextstep3.column = 0;/上if( !fout )cerr 文件 out 无法打开! endl;exit(1);Wiring:Wiring()if(fout)fout.close();for(int i = 0; i = n+1; i+)if(gridi)delete gridi;if(grid)delete grid;void Wiring:Solve()if(FindPath()PrintPath();/输出路径elsePrintFail();/无路径bool Wiring:FindPath()if(start = finish)/如果起点和终点重合return 0;position here, near;/当前位置和相邻的一个位置gridstart.rowstart.column = 2;/开始点步数记为2list Queue;/辅助队列Queue.push_back(start);/初始位置是起点while(1)here = Queue.front();/取队尾位置Queue.pop_front();for(int i = 0; i 0; i-)/找前趋位置gridhere.rowhere.column = -1;/表示在路径上for(int j = 0; j 4; j+)near = here + nextstepj;if(gridnear.rownear.column = i+1)/找到前趋break;here = near;/向前移动for(int i = 1; i = n; i+)int j;for(j = 1; j = m; j+)if(gridij = -1)/表示路径fout *tt;elsefout gridij tt;fout endl;void Wiring:PrintFail()fout No Path! endl;/*主函数文件 test.cpp*/#include
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【正版授权】 ISO/IEC 15415:2024 EN Automatic identification and data capture techniques - Bar code symbol print quality test specification - Two-dimensional symbols
- 2025年度化工生产工厂技术许可合同协议
- 2025年城市管道天然气项目建议书
- 设备管理科设备维护与更新计划
- 提升仓库服务质量的个人策略计划
- 社区个人工作计划改善社区供水设施
- 2025年特种大型铝合金型材合作协议书
- 新闻媒体安全管理的必要性计划
- 社团交流合作的网络平台计划
- 2025年中大型重载轴承项目建议书
- 消防工程管理办法附流程图
- 幼儿园手工教学中教师指导行为研究-以自贡市幼儿园为例
- 初中物理实验教学
- 雨水管道中粗砂回填
- 团意操作流程详解课件
- SH/T 0356-1996燃料油
- 第1课中华优秀传统文化的内涵与特点课件(共28张PPT)
- 耳鼻咽喉头颈外科学-鼻科症状学课件
- 轮胎使用日常说明
- 第8章 动车组空调装置检修动车组维护与检修
- 《幼小衔接存在的问题及对策研究(论文)6400字》
评论
0/150
提交评论