最大覆蓋問題在路徑限制下是NP-hard問題。 廣義成本收益演算法(GCB)能解決這樣的問題，並達到1/2(1-1/e)的近似最佳值。 但是GCB和近似最佳解仍有有一段差距。 此研究提出基於交叉熵的蒙地卡羅搜尋樹演算法 (CE-MCTS) 來解決這個問題。 這個演算法包含三個部分: 演化演算法 (EA) 用於採樣分支、信賴上界策略 (UCB) 用於選擇展開和估計分布演算法 (EDA) 用於模擬。實驗證實了CE-MCTS在不同地圖及成本限制底下的效能比其他兩個演算法(GCB、EAMC)更好。 ;The maximal coverage problems with routing constraints are NP-hard problems. The generalized cost-benefit algorithm (GCB) is able to solve this problem with a $\frac{1}{2}(1-\frac{1}{e})\widetilde{OPT}$ guarantee. There is a space between the approximation optimal solution $(\widetilde{OPT})$ and GCB performance. In this research, the cross-entropy based Monte Carlo Tree Search algorithm (CE-MCTS) is proposed to solve this problem. It consists of three parts: the evolutionary algorithm (EA) for sampling the branches, the upper confidence bound (UCB) policy for selections, and the estimation of distribution algorithm (EDA) for simulations. The experiments demonstrate that the CE-MCTS outperforms benchmark approaches (e.g., GCB, EAMC) in different maps with various budget constraints.
