计算机科学
强化学习
斯坦纳树问题
人工智能
蒙特卡罗树搜索
树(集合论)
图形
启发式
理论计算机科学
组合数学
机器学习
作者
Zong Yan,Haizhou Du,Jiahao Zhang,Guoqing Li
出处
期刊:Conference on Industrial Electronics and Applications
日期:2021-08-01
标识
DOI:10.1109/iciea51954.2021.9516291
摘要
Steiner tree problem (STP) in graphs aims to find a tree of minimum weight in the graph that connects a given set of vertices. It is a classic NP-hard combinatorial optimization problem and has many applications in real world. Many approximate algorithms have been developed for STP, but they suffer from high computational complexity and weak worst-case solution guarantees, respectively. Heuristic algorithms are also developed. But each of them requires application domain knowledge to design and is only suitable for specific scenarios. In this paper, we design a novel framework Cherrypick based on novel graph embedding and deep reinforcement learning to tackle the STP. Given an STP instance, Cherrypick uses this embedding to encode its path-related information and sends the encoded graph to a deep reinforcement learning component based on deep Q network (DQN) to find solutions. We implement the Cherrypick and demonstrate its efficacy and efficiency with extensive experiments using real-world and synthetic datasets.
科研通智能强力驱动
Strongly Powered by AbleSci AI