4-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters

In this paper, an analysis of the 4-(<i>N<SUP>2</SUP></i>-1) Puzzle, which is a generalization of the (<i>N<SUP>2</SUP></i>-1) Puzzle, is presented. This problem is of interest due to its algorithmic and computational complexity and its applications to...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Sanz, Victoria María, De Giusti, Armando Eduardo, Naiouf, Marcelo
Formato: Articulo
Lenguaje:Inglés
Publicado: 2010
Materias:
Ciencias Informáticas
Parallel algorithms
Optimization
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/9674
http://journal.info.unlp.edu.ar/wp-content/uploads/JCST-Jun10-7.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-9674
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
spellingShingle Ciencias Informáticas
Parallel algorithms
Optimization
Sanz, Victoria María
De Giusti, Armando Eduardo
Naiouf, Marcelo
4-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters
topic_facet Ciencias Informáticas
Parallel algorithms
Optimization
description In this paper, an analysis of the 4-(<i>N<SUP>2</SUP></i>-1) Puzzle, which is a generalization of the (<i>N<SUP>2</SUP></i>-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 (<i>N<SUP>2</SUP></i>-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-(<i>N<SUP>2</SUP></i>-1) Puzzle is analyzed.
format Articulo
Articulo
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-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters
title_short 4-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters
title_full 4-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters
title_fullStr 4-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters
title_full_unstemmed 4-(<i>N<SUP>2</SUP></i>-1) puzzle: parallelization and performance on clusters
title_sort 4-(<i>n<sup>2</sup></i>-1) puzzle: parallelization and performance on clusters
publishDate 2010
url http://sedici.unlp.edu.ar/handle/10915/9674
http://journal.info.unlp.edu.ar/wp-content/uploads/JCST-Jun10-7.pdf
work_keys_str_mv AT sanzvictoriamaria 4insup2supi1puzzleparallelizationandperformanceonclusters
AT degiustiarmandoeduardo 4insup2supi1puzzleparallelizationandperformanceonclusters
AT naioufmarcelo 4insup2supi1puzzleparallelizationandperformanceonclusters
bdutipo_str Repositorios
_version_ 1764820492414353410

Ejemplares similares