logo móvil
Contáctanos

La enumeración de retículas con poda discreta: mejoras, estimación de costos y parámetros óptimos

Autores: Luan, Luan; Gu, Chunxiang; Zheng, Yonghui; Shi, Yanan

Idioma: Inglés

Editor: MDPI

Año: 2023

Descargar PDF

Acceso abierto

Artículo científico
2023

La enumeración de retículas con poda discreta: mejoras, estimación de costos y parámetros óptimos


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Enumeración de retícula
Poda extrema
Poda discreta
Enumeración de DP
Estimación de costos
Optimización

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 20

Citaciones: Sin citaciones


Descripción
La enumeración de retículos es un algoritmo de espacio lineal para resolver el problema del vector de retículo más corto (SVP). La poda extrema es una técnica práctica para acelerar la enumeración de retículos, que tiene un análisis teórico maduro y una implementación práctica. Sin embargo, estos trabajos aún no se han aplicado a la poda discreta. En este documento, mejoramos la enumeración podada discreta (enumeración DP) y proporcionamos una solución al problema propuesto por Léo Ducas y Damien Stehlé sobre la estimación del costo de la poda discreta. Primero rectificamos la suposición de aleatoriedad para describir más precisamente la distribución de puntos del retículo de la enumeración DP. Luego, proponemos una serie de mejoras, incluido un nuevo algoritmo de búsqueda binaria de tiempo polinómico para el radio de enumeración de celdas, un algoritmo refinado de decodificación de celdas y una estrategia de realeatorización y reprocesamiento, todos con el objetivo de aumentar la eficiencia y construir un modelo de estimación de costos más preciso para la enumeración DP. Basándonos en estas mejoras teóricas y prácticas, construimos un modelo preciso de estimación de costos para la enumeración DP mediante simulación, que tiene una buena precisión en experimentos. Este simulador DP nos permite proponer un método de optimización para calcular los parámetros óptimos de la enumeración DP para minimizar el tiempo de ejecución. Los resultados experimentales y el análisis asintótico muestran que el método de poda discreta podría superar a la poda extrema, lo que significa que nuestra enumeración DP optimizada podría convertirse en el solucionador de SVP de espacio polinómico más eficiente hasta la fecha. También se proporciona una implementación de código abierto de la enumeración DP con su simulador.

Otros recursos que podrían interesarte

Temas Virtualpro