logo móvil
Contáctanos

Un enfoque novedoso para resolver el problema de las N reinas utilizando un algoritmo de resolución de conflictos no secuencial

Autores: Moghimi, Omid; Amini, Amin

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

Acceso abierto

Artículo científico
2024

Un enfoque novedoso para resolver el problema de las N reinas utilizando un algoritmo de resolución de conflictos no secuencial


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería Eléctrica y Electrónica

Palabras clave

Reinas
Algoritmo
Complejidad
Eficiencia
Memoria
Escalabilidad

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 50

Citaciones: Sin citaciones


Descripción
El problema de las N reinas es un desafío fundamental en la optimización combinatoria, comúnmente utilizado como referencia para evaluar la eficiencia de los algoritmos. Los algoritmos tradicionales, como el Backtracking con Forward Checking (BFC), técnicas de problemas de satisfacción de restricciones (CSP), algoritmos de anticipación y métodos basados en heurísticas, a menudo enfrentan desafíos con una complejidad temporal exponencial, lo que los hace menos prácticos para instancias a gran escala. Este documento presenta un algoritmo novedoso, resolución de conflictos no secuencial (NSCR), que mejora el rendimiento sobre los algoritmos tradicionales a través de la resolución dinámica de conflictos. El algoritmo NSCR resuelve iterativamente conflictos entre reinas ajustando sus posiciones, con el objetivo de optimizar tanto la complejidad temporal como el uso de memoria. Aunque el NSCR también opera dentro de límites de tiempo exponenciales, demuestra una escalabilidad y eficiencia mejoradas en comparación con los métodos tradicionales. Una fortaleza significativa del algoritmo NSCR radica en su complejidad espacial, que es O(n), y una complejidad temporal que, aunque generalmente es menor que la de los métodos tradicionales, puede alcanzar O(n) en el peor de los casos. Esta complejidad espacial lineal es altamente ventajosa, especialmente al tratar con tamaños de problemas grandes, ya que garantiza un uso eficiente de los recursos de memoria. El análisis comparativo con los algoritmos mencionados anteriormente muestra que el NSCR ofrece una gestión de recursos superior, utilizando hasta un 60% menos de memoria y reduciendo el tiempo de ejecución en aproximadamente un 50%, convirtiéndolo en una opción eficiente para instancias a gran escala del problema de las N reinas. El rendimiento del algoritmo, evaluado en tamaños de problemas que van desde 8 hasta 1000 reinas, destaca su capacidad para gestionar eficazmente los recursos computacionales, a pesar de los desafíos inherentes de la complejidad temporal exponencial.

Otros recursos que podrían interesarte

Temas Virtualpro