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
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
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.
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.