求解最小Steiner树的可视化试验方法  

A visualization approach for the Steiner minimal tree problem

作　　者：杨宗霄[1] 高艳平[1] 程传业[1] 冯志强[1] 张祖俊[1] 

机构地区：[1]河南科技大学系统科学与工程研究所,洛阳471003

出　　处：《系统工程理论与实践》2008年第7期173-178,共6页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70671035)

摘　　要：求解最小Steiner树是NP难题,在通信网络设计、交通规划等工程实际中有着广泛的应用.利用表面活性剂溶液的物化特性,将溶液的最小表面张力特性采用平行板结构转化成二维平面的最优路径,得到了最小Steiner树的可视化解.通过改变模板装置和溶液的相对运动,研发出了最短路径可视化仪,为将最小Steiner树求解应用于工程实践探索了新的方法手段.The Steiner minimal tree problem shows the availability in many engineering practices such as communication network, arterial traffic programming, notwithstanding one of the NP problems. A visualization approach is proposed in this paper by using the physical chemistry characteristics of the surfactant solution and developed experiment unit. The minimum surface tension of the surfactant solution can be transformed into twodimensional system shortest path planning, and a transparency visualization scheme, i.e. a Steiner minimum tree, for objective can be formed steadily and rapidly. A special visualization instrument for system shortest path programming is developed by changing the relative movement of the template unit and the surfactant solution, and shown a new application approach for the Steiner minimal tree problem to engineering applications.

关 键 词：最小Steiner树 表面活性剂溶液 最短路径规划 可视化仪 

分 类 号：N945.15[自然科学总论—系统科学]