Es fácil para mí responder, aunque no sé si mis coautores estarían de acuerdo. Fue el capítulo sobre programación dinámica.
Cuando estábamos escribiendo la primera edición, a fines de la década de 1980, cuando llegamos al capítulo de programación dinámica, sabíamos que teníamos que planearlo cuidadosamente antes de escribirlo. Entonces eso es exactamente lo que hicimos. Lo planeamos con mucho cuidado. Escribí el primer borrador, exactamente de acuerdo con la especificación que habíamos acordado. Estaba feliz con ello.
Pero Charles Leiserson y Ron Rivest no estaban. Acordaron que había escrito el capítulo para especificar. Pero sentían que simplemente no funcionaba.
Le pedimos a un estudiante graduado en el Grupo de Teoría del MIT que leyera el borrador y nos dijera lo que pensaba. Estuvo de acuerdo con Charles y Ron.
- Cómo construir un sistema de recomendación de libros
- ¿Cuáles son los mejores libros de algoritmos que uno debe usar?
- ¿Debería leer el libro ‘Interpretación de estructuras de programas de computadora’?
- ¿Cuáles son algunos libros para aprender C ++ en los niveles introductorios, intermedios y avanzados?
- ¿Cuál fue la motivación detrás de escribir ‘Sistemas informáticos: la perspectiva de un programador’?
Así que reescribí el capítulo y, como con todos nuestros capítulos, Charles y Ron lo editaron. El resultado es lo que apareció en la primera edición de Introducción a los algoritmos . Estaba bien, pero comenzó con la multiplicación de la cadena de la matriz, un problema bidimensional, y no tenía problemas unidimensionales más simples.
Para la segunda edición, decidimos que comenzaríamos con un problema unidimensional. Utilizamos el problema de programación de la línea de ensamblaje. (Fue nuestra reestructuración del problema de volar contra conducir). De hecho, se puede resolver con programación dinámica, pero esa no es realmente la mejor manera de resolver este problema, porque en realidad solo se trata de encontrar el camino más corto en un acíclico dirigido. grafico.
Para la tercera edición, Ron Rivest trabajó en el capítulo. Cambió el problema de apertura al problema de corte de varilla, que es unidimensional y se presta a la programación dinámica mejor que el problema de programación de la línea de ensamblaje. Ron también aumentó el énfasis en la memorización en el capítulo. Creo que finalmente tenemos un buen capítulo.