Wyszukiwanie zaawansowane ?

Obiekt

Pobierz

Tytuł: Monte Carlo Tree Search Algorithm for the Euclidean Steiner Tree Problem, Journal of Telecommunications and Information Technology, 2017, nr 4

Autor:

Bereta, Michał

Data wydania:

2017, nr 4

Typ zasobu:

artykuł

Opis:

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 find 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 efficiency decreases when the number of terminals grows. A novel algorithm based on Upper Confidence Bound for Trees is proposed. It is adapted to the specific 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.

Wydawca:

National Institute of Telecommunications

Format:

application/pdf

Identyfikator zasobu:

ISSN 1509-4553, on-line: ISSN 1899-8852 ; oai:bc.itl.waw.pl:2006

Źródło:

Journal of Telecommunications and Information Technology

Język:

ang

Prawa:

Biblioteka Naukowa Instytutu Łączności

Temat i słowa kluczowe:

UCT algorithm Monte Carlo Tree Search Euclidean Steiner tree problem MCTS

Kolekcje, do których przypisany jest obiekt:

Data ostatniej modyfikacji:

27 gru 2017

Data dodania obiektu:

27 gru 2017

Liczba wyświetleń treści obiektu:

136

Wszystkie dostępne wersje tego obiektu:

https://bc.itl.waw.pl/publication/2286

Wyświetl opis w formacie RDF:

RDF

Wyświetl opis w formacie OAI-PMH:

OAI-PMH

Nazwa wydania Data
Bereta, Michał, 2017, nr 4, Monte Carlo Tree Search Algorithm for the Euclidean Steiner Tree Problem, Journal of Telecommunications and Information Technology, 2017, nr 4 27 gru 2017
×

Cytowanie

Styl cytowania:

Dane kontaktowe

Adres

Instytut Łączności – Państwowy Instytut Badawczy ul. Szachowa 1 04-894 Warszawa

Telefon

(+48) 5128 696

E-Mail

biblioteka@il-pib.pl

Odwiedź nas!

Ta strona wykorzystuje pliki 'cookies'. Więcej informacji