4-(N<sup>2</sup>-1) Puzzle: parallelization and performance on clusters
In this paper, an analysis of the 4-(N<sup>2</sup>-1) Puzzle, which is a generalization of the (N<sup>2</sup>-1) Puzzle, is presented. This problem is of interest due to its algorithmic and computational complexity and its applications to robot movements with several objectiv...
Guardado en:
Autores principales: | , , |
---|---|
Formato: | Objeto de conferencia |
Lenguaje: | Inglés |
Publicado: |
2009
|
Materias: | |
Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/20906 |
Aporte de: |
id |
I19-R120-10915-20906 |
---|---|
record_format |
dspace |
institution |
Universidad Nacional de La Plata |
institution_str |
I-19 |
repository_str |
R-120 |
collection |
SEDICI (UNLP) |
language |
Inglés |
topic |
Ciencias Informáticas Parallel algorithms Optimization multi-objective problems discrete optimization superlinearity |
spellingShingle |
Ciencias Informáticas Parallel algorithms Optimization multi-objective problems discrete optimization superlinearity Sanz, Victoria María De Giusti, Armando Eduardo Naiouf, Marcelo 4-(N<sup>2</sup>-1) Puzzle: parallelization and performance on clusters |
topic_facet |
Ciencias Informáticas Parallel algorithms Optimization multi-objective problems discrete optimization superlinearity |
description |
In this paper, an analysis of the 4-(N<sup>2</sup>-1) Puzzle, which is a generalization of the (N<sup>2</sup>-1) Puzzle, is presented. This problem is of interest due to its algorithmic and computational complexity and its applications to robot movements with several objectives. Taking the formal definition as a starting point, 4 heuristics that can be used to predict the best achievable objective and to estimate the number of steps required to reach a solution state from a given configuration are analyzed. By selecting the objective, a sequential and parallel solution over a cluster is presented for the (N<sup>2</sup>-1) Puzzle, based on the heuristic search algorithm A*. Also, variations of the classic heuristic are analyzed. The experimental work focuses on analyzing the possible superlinearity and the scalability of the parallel solution on clusters, by varying the physical configuration and the dimension of the problem. Finally, the suitability of the heuristic used to assess the best achievable objective in the 4-(N<sup>2</sup>-1) Puzzle is analyzed. |
format |
Objeto de conferencia Objeto de conferencia |
author |
Sanz, Victoria María De Giusti, Armando Eduardo Naiouf, Marcelo |
author_facet |
Sanz, Victoria María De Giusti, Armando Eduardo Naiouf, Marcelo |
author_sort |
Sanz, Victoria María |
title |
4-(N<sup>2</sup>-1) Puzzle: parallelization and performance on clusters |
title_short |
4-(N<sup>2</sup>-1) Puzzle: parallelization and performance on clusters |
title_full |
4-(N<sup>2</sup>-1) Puzzle: parallelization and performance on clusters |
title_fullStr |
4-(N<sup>2</sup>-1) Puzzle: parallelization and performance on clusters |
title_full_unstemmed |
4-(N<sup>2</sup>-1) Puzzle: parallelization and performance on clusters |
title_sort |
4-(n<sup>2</sup>-1) puzzle: parallelization and performance on clusters |
publishDate |
2009 |
url |
http://sedici.unlp.edu.ar/handle/10915/20906 |
work_keys_str_mv |
AT sanzvictoriamaria 4nsup2sup1puzzleparallelizationandperformanceonclusters AT degiustiarmandoeduardo 4nsup2sup1puzzleparallelizationandperformanceonclusters AT naioufmarcelo 4nsup2sup1puzzleparallelizationandperformanceonclusters |
bdutipo_str |
Repositorios |
_version_ |
1764820465087414273 |