Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Euclidean Steiner tree problem

Sortuj według:

Ogranicz wyniki do:

Monte Carlo Tree Search Algorithm for the Euclidean Steiner Tree Problem

Bereta M.

Journal of Telecommunications and Information Technology

2017

nr 4

71--81

This study is concerned with a novel Monte Carlo Tree Search algorithm for the problem of minimal Euclidean Steiner tree on a plane. Given p p p points (terminals) on a plane, the goal is to ﬁnd a connection between all the points, so that the total sum of the lengths of edges is as low as possible, while an addition of extra points (Steiner points) is allowed. Finding the minimum Steiner tree is known to be np-hard. While exact algorithms exist for this problem in 2D, their eﬃciency decreases when the number of terminals grows. A novel algorithm based on Upper Conﬁdence Bound for Trees is proposed. It is adapted to the speciﬁc characteristics of Steiner trees. A simple heuristic for fast generation of feasible solutions based on Fermat points is proposed together with a correction procedure. By combing Monte Carlo Tree Search and the proposed heuristics, the proposed algorithm is shown to work better than both the greedy heuristic and pure Monte Carlo simulations. Results of numerical experiments for randomly generated and benchmark library problems (from OR-Lib) are presented and discussed.