| 基于分层法的通风网络图绘制算法研究 |
| |
| 引用本文： | 邓立军,刘剑. 基于分层法的通风网络图绘制算法研究[J]. 计算机工程与应用, 2014, 50(15): 1-6 |
| |
| 作者姓名： | 邓立军 刘剑 |
| |
| 作者单位： | 辽宁工程技术大学 安全科学与工程学院，辽宁 阜新 123000 |
| |
| 摘 要： | 最长路径法绘制通风网络图需要频繁地搜索任意两个节点之间的最长路径，采用深度优先搜索导致大量的时间浪费在无用路径的搜索过程中；且采用几何相交方法判断分支交叉，效率低且无法有效地减少分支交叉数。提出了将分层法引入到通风网络图绘制中。采用最长路径法对网络图进行节点分层，求解整数规划问题优化节点分层减少长边；采用模拟退火遗传算法优化节点排序，从拓扑上减少分支交叉数。为了减少无意义地搜索最长路径过程，采用最长路径并联通路法计算节点坐标和分支形状。给出了基于分层法的通风网络图绘制的测试例子。
|
| 关 键 词： | 通风网络图 最长路径法 整数规划 分层法 模拟退火遗传算法 |
Study on drawing algorithm of ventilation network graph based on layer method |
| |
| DENG Lijun,LIU Jian. Study on drawing algorithm of ventilation network graph based on layer method[J]. Computer Engineering and Applications, 2014, 50(15): 1-6 |
| |
| Authors: | DENG Lijun LIU Jian |
| |
| Affiliation: | College of Safety Science and Engineering, Liaoning Technical University, Fuxin, Liaoning 123000, China |
| |
| Abstract: | Drawing ventilation network graph based on longest path method requires frequently searching the longest path between any two nodes. There is a lot of time wasted in useless paths search process because of the depth first search algorithm. Geometric intersection method is adopted to determine the arc crossings, but it has low efficiency and can not effectively reduce the arc crossings number. The layered method is introduced to ventilation network graph drawing. The longest path method is employed to rank nodes of ventilation network, and long edges are removed by solving integer programming problem for optimizing node ranking. Then simulated annealing-genetic algorithm is used to optimize the nodes order based previous node ranking step, reducing the arc crossings number from the network topology. In order to decrease the meaningless longest path search process, a modified version of the longest path method is made to calculate node coordinates and arc shape, which is called longest parallel path method. The test example of drawing ventilation network graph is presented based on layered method. |
| |
| Keywords: | ventilation network graph longest path method integer programming layered method simulated annealing-genetic algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
