提供最优网络配置的准最小树的构造、搜索或生成方法

摘要

一种用以创建、搜索或生成提供最优网络配置的准最小树的方法,提供对Steiner问题的近似解。这是一种用以通过在作为,即一个由顶点和加权边组成的几何结构的无向图上选择顶点和边,来构造、搜索或生成提供连通作为多个已定义顶点的Steiner点v1至v5的最优网络配置的准最小树的方法,其中通过从那些在创建或搜索提供不包括闭合路径且容许分枝的路径的树时距离最短的顶点开始,将顶点互相连通,来创建或搜索互相不共享所述顶点和边的多棵树,所述距离提供连通任意两个临时点的单一路径所包含边的权值总和；然后,将所述多棵树互相连通,以提供已互相连通所有所述多个已定义顶点v1至v5,且包含的所述边的权值总和为准最小的树(准最小树)。

主权项

1、一种用以通过在作为由顶点和加权边组成的几何结构的无向图上选择顶点和边，来构造、搜索或生成提供连通作为多个已定义顶点的Steiner点的最优网络配置的准最小树的构造、搜索或生成方法，其特征在于，在通过选择所述顶点和边来为构造、搜索或生成最优网络配置而创建或搜索一条路径时，通过从那些在创建或搜索提供不包括闭合路径且容许分枝的路径的树时距离最短的顶点开始，将顶点互相连通，来创建或搜索互相不共享所述顶点和边的多棵树，所述距离提供连通任意两个临时点的单一路径所包含边的权值总和；然后，将所述多棵树互相连通，以提供已互相连通所有所述多个已定义顶点，即Steiner点，且所包含的所述边的权值总和为准最小的树。