Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Annals of Computer Science and Information Systems

1 2020

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On Finding the Optimal Tree of a Complete Weighted Graph

Hosseini Seyed Soheil, Wormald Nick, Tian Tianhai

Annals of Computer Science and Information Systems

2020

Vol. 21

271--275

We want to find a tree where the path length between any two vertices on this tree is as close as possible to their corresponding distance in the complete weighted graph of vertices upon which the tree is built. We use the residual sum of squares as the optimality criterion to formulate this problem, and use the Cholesky decomposition to solve the system of linear equations to optimise weights of a given tree. We also use two metaheuristics, namely Simulated Annealing (SA) and Iterated Local Search (ILS) to optimise the tree structure. Our results suggest that SA and ILS both perform well at finding the optimal tree structure when the dispersion of distances in the complete graph is large. However, when the dispersion of distances is small, only ILS has a solid performance.