CAJ | 학술논문

最长路径法绘制通风网络图需要频繁地搜索任意两个节点之间的最长路径，采用深度优先搜索导致大量的时间浪费在无用路径的搜索过程中；且采用几何相交方法判断分支交叉，效率低且无法有效地减少分支交叉数。提出了将分层法引入到通风网络图绘制中。采用最长路径法对网络图进行节点分层，求解整数规划问题优化节点分层减少长边；采用模拟退火遗传算法优化节点排序，从拓扑上减少分支交叉数。为了减少无意义地搜索最长路径过程，采用最长路径并联通路法计算节点坐标和分支形状。给出了基于分层法的通风网络图绘制的测试例子。
최장로경법회제통풍망락도수요빈번지수색임의량개절점지간적최장로경，채용심도우선수색도치대량적시간낭비재무용로경적수색과정중；차채용궤하상교방법판단분지교차，효솔저차무법유효지감소분지교차수。제출료장분층법인입도통풍망락도회제중。채용최장로경법대망락도진행절점분층，구해정수규화문제우화절점분층감소장변；채용모의퇴화유전산법우화절점배서，종탁복상감소분지교차수。위료감소무의의지수색최장로경과정，채용최장로경병련통로법계산절점좌표화분지형상。급출료기우분층법적통풍망락도회제적측시례자。
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 algo-rithm. Geometric intersection method is adopted to determine the arc crossings, but it has low efficiency and can not effec-tively 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 coordi-nates and arc shape, which is called longest parallel path method. The test example of drawing ventilation network graph is presented based on layered method.