论文标题
Deep-Steiner：学习解决欧几里得施泰纳树问题
Deep-Steiner: Learning to Solve the Euclidean Steiner Tree Problem
论文作者
论文摘要
Euclidean Steiner树问题寻求Min-Cost网络来连接目标位置的集合，并且是无线网络的许多应用程序的基础。在本文中，我们介绍了一项研究，以通过图表学习增强的增强学习来解决欧几里得施泰纳树问题。与经常研究的连接问题（例如旅行推销员问题或车辆路由问题）不同的是，搜索空间是有限的，欧几里得施泰纳树问题需要在整个欧几里得空间上进行搜索，从而使现有方法不适用。在本文中，我们通过利用Steiner树的独特特征来设计离散方法，并提出了新的训练方案来处理增量结构期间出现的动态Steiner点。我们的设计通过在数据集集合上进行的实验进行理智检查，令人鼓舞的结果表明，我们的方法是替代经典组合方法的实用性。
The Euclidean Steiner tree problem seeks the min-cost network to connect a collection of target locations, and it underlies many applications of wireless networks. In this paper, we present a study on solving the Euclidean Steiner tree problem using reinforcement learning enhanced by graph representation learning. Different from the commonly studied connectivity problems like travelling salesman problem or vehicle routing problem where the search space is finite, the Euclidean Steiner tree problem requires to search over the entire Euclidean space, thereby making the existing methods not applicable. In this paper, we design discretization methods by leveraging the unique characteristics of the Steiner tree, and propose new training schemes for handling the dynamic Steiner points emerging during the incremental construction. Our design is examined through a sanity check using experiments on a collection of datasets, with encouraging results demonstrating the utility of our method as an alternative to classic combinatorial methods.
