logo móvil
Contáctanos

Un enfoque de aprendizaje automático para la selección de algoritmos para el cálculo exacto del ancho del árbol

Autores: Slavchev, Borislav; Masliankova, Evelina; Kelk, Steven

Idioma: Inglés

Editor: MDPI

Año: 2019

Descargar PDF

Acceso abierto

Artículo científico
2019

Un enfoque de aprendizaje automático para la selección de algoritmos para el cálculo exacto del ancho del árbol


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Marco de selección de algoritmos
Aprendizaje automático
Cálculo exacto
Anchura del árbol
Metaalgoritmo
Importancia de las características del grafo

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 38

Citaciones: Sin citaciones


Descripción
Presentamos un marco de selección de algoritmos basado en aprendizaje automático para el cálculo exacto de , un parámetro de gráficos estudiado intensamente que es difícil de calcular. Específicamente, analizamos el rendimiento comparativo de tres algoritmos exactos de treewidth de última generación en una amplia variedad de gráficos y utilizamos esta información para predecir cuál de los algoritmos, en base a gráfico por gráfico, calculará la treewidth más rápidamente. Los resultados experimentales muestran que el meta-algoritmo propuesto supera a los métodos existentes en instancias de referencia en las tres métricas de rendimiento que utilizamos: en resumen, calcula la treewidth más rápido que cualquier algoritmo individual de forma aislada. Analizamos nuestros resultados para obtener información sobre la importancia de las características del gráfico y las fortalezas y debilidades de los algoritmos que utilizamos. Nuestros resultados son una evidencia adicional de las ventajas que se pueden obtener al combinar estratégicamente enfoques de aprendizaje automático y optimización combinatoria dentro de un marco algorítmico híbrido. El modelo de aprendizaje automático que utilizamos es intencionalmente simple para enfatizar que la aceleración ya se puede obtener sin tener que involucrarse en las complejidades completas de la ingeniería de aprendizaje automático. Reflexionamos sobre cómo el trabajo futuro podría ampliar este concepto simple pero efectivo mediante la implementación de modelos de aprendizaje automático más sofisticados.

Otros recursos que podrían interesarte

Temas Virtualpro