基于节点重要度的斯坦纳树构造（专利GAI22CN4390）

      已有斯坦纳树构造方法大多从邻接边（路径）的权重入手，在选择邻接边构造树的过程中，才考虑邻接边的组合，使得树的代价尽量小。这种方式无法更好的发掘组合对于更优的斯坦纳树的决定性作用，使得结果不理想，或迭代过程过长。

      为此，在特定类别的图中，人们把模式（如L和Z等）引入到斯坦纳树的构造中。 但是这样使得算法过于复杂，模式少使得结果不理想，模式过多搜索过程代价又会过大。不通用。

      在选择边构造的过程中，才去考察组合对于树生成的决定性作用，始终是局部的优化，且过程冗长。同时，这种方式无法有效解决多目标斯坦纳树的构造。

      只有在邻接边的选择之前考虑组合，才能克服以上困难，得到更优的斯坦纳树。

      GAI22CN4390 在主要从两个方面解决斯坦纳树的构造：

      一方面，通过统计邻接边连接T节点的能力，以降低邻接边的权重值（专利GAI22CN4676给出一种非常高效的方案）；

      另一方面，通过更新后的邻接边权重，计算非T节点到T节点的距离，进而计算节点的重要度，根据节点的重要度，构造斯坦纳树，这极大的简化了多目标斯坦纳树的构造。

     如上图中，经过邻接边<0，3>，<1，3>，<2，3>的最短路径，通过2条路径，各连接3个T节点。如邻接边<0，3>通过路径0-3-1和0-3-2，连接节点0到1和2。取邻接边<0，3>，<1，3>，<2，3>的连接能力都为3（或2），得到更新后的图中邻接边<0，3>，<1，3>，<2，3>的权重都为2/3（或2/2）。其他邻接边权重更新为3.5/2（或3.5/1）。

      在更新后权重后的图上，很容易得到连接T节点0，1，2的斯坦纳树为{{<0,3>,<1,3>,<2,3>},{0,1,2,3}}，如用基于MST的方法。在多目标斯坦纳树的构造中，可根据各优化目标下的节点3到T节点的最短路径长度，计算节点的重要度（如最短路径长度的倒数和）；进而根据各优化目标的所占的比重，计算所有优化目标的合成重要度；进而根据节点的重要度的大小，选择节点和邻接边构造多目标斯坦纳树。

     该方法把邻接边的组合优化能力优先于树的构造考虑，尽可能的保留了邻接边的组合信息，保证了邻接边的权重，对于斯坦纳树代价的决定性在树构造中具有全局性。