Un asistente extensible para la experimentación interactiva con problemas combinatorios

Abstract

Los algoritmos voraces tienen un problema desde el punto de vista docente: no son muy adecuados para su ejercitación por los alumnos. Para remediar esta situación, hemos diseñado un enfoque didáctico basado en experimentación y soportado por varios asistentes interactivos para problemas concretos (mochila, selección de actividades, árbol de recubrimiento de coste mínimo). A partir de nuestra experiencia, la comunicación analiza los problemas encontrados y presenta mejoras en varios aspectos. Primero, hemos ampliado ligeramente el método experimental. Segundo, hemos modificado los asistentes interactivos para soportar mejor el método experimental e incluso poder usarlo con otras técnicas de diseño (programación dinámica, algoritmos aproximados). Tercero, hemos integrado dos asistentes interactivos en uno solo, llamado GreedEx, que puede ampliarse para dar soporte a otros problemas combinatorios. Por último, hemos ampliado GreedEx con un tercer problema, el de la mochila 0/1. En resumen, estas mejoras han reducido las limitaciones del método experimental, han ampliado el dominio de aplicación de los asistentes, y facilitan su extensión a otros problemas y su mantenimiento.