Preguntas sobre problemas que se pueden resolver combinando soluciones de subproblemas obtenidas recursivamente.
Los problemas de la mochila se resuelven fácilmente mediante programación dinámica. La programación dinámica se ejecuta en tiempo polinomial; Por eso lo hacemos, ¿verdad? Sin embargo, he leído que en realidad es un problema NP-completo, lo que significaría que resolver el problema en un problema...
He usado la técnica de la programación dinámica varias veces, sin embargo, hoy un amigo me preguntó cómo definiría mis subproblemas, me di cuenta de que no tenía forma de proporcionar una respuesta formal objetiva. ¿Cómo define formalmente un subproblema para un problema que resolvería utilizando...
¿Existe una diferencia fundamental entre la programación dinámica de arriba hacia abajo y de abajo hacia arriba? En particular, ¿hay algún problema que pueda resolverse de abajo hacia arriba pero no de arriba hacia abajo? ¿O es el enfoque ascendente solo un desenrollamiento de la recurrencia en...
Lo siento de antemano si esta pregunta suena tonta ... Hasta donde sé, construir un algoritmo usando programación dinámica funciona de esta manera: expresa el problema como una relación de recurrencia; implementar la relación de recurrencia ya sea mediante la memorización o mediante un enfoque...
He estado trabajando en programación dinámica por algún tiempo. La forma canónica de evaluar una recursión de programación dinámica es creando una tabla de todos los valores necesarios y llenándola fila por fila. Ver por ejemplo Cormen, Leiserson et al: "Introducción a los algoritmos" para una...
Estaba leyendo sobre programación dinámica cuando me encontré con la siguiente cita Un algoritmo de programación dinámica examinará todas las formas posibles de resolver el problema y elegirá la mejor solución. Por lo tanto, podemos pensar aproximadamente en la programación dinámica como un...
He estado trabajando en el siguiente problema de este libro . Un cierto lenguaje de procesamiento de cadenas ofrece una operación primitiva que divide una cadena en dos partes. Como esta operación implica copiar la cadena original, se necesitan n unidades de tiempo para una cadena de longitud n,...
Hice esta pregunta en StackOverflow , pero creo que este es un lugar más apropiado. Este es un problema del curso de Introducción al algoritmo : Tiene una matriz con enteros positivos (la matriz no necesita ser ordenada o los elementos únicos). Sugiera un algoritmo para encontrar la mayor suma...
En la Introducción a los algoritmos de Cormen et al. , La sección 15.3 Elementos de la programación dinámica explica la memorización de la siguiente manera: Un algoritmo recursivo memorizado mantiene una entrada en una tabla para la solución de cada subproblema. Cada entrada de la tabla...
Si tengo dos matrices y B , de dimensiones 1000 × 2 y 2 × 1000 , respectivamente, y quiero calcular ( A B ) 5000 , es más eficiente reescribir primero la expresión como A ( B A ) 4999 B y solo entonces evalúe numéricamente, porque A B es de dimensión 1000 × 1000 pero B A es de dimensión 2 × 2...
La programación dinámica puede reducir el tiempo necesario para realizar un algoritmo recursivo. Sé que la programación dinámica puede ayudar a reducir la complejidad temporal de los algoritmos. ¿Las condiciones generales son tales que si un algoritmo recursivo lo satisface implicaría que el uso de...
Dadas dos cadenas S1,S2S1,S2S_1, S_2 , escribimos S1S2S1S2S_1S_2 para su concatenación. Dada una cadena SSS y número entero k≥1k≥1k\geq 1 , escribimos (S)k=SS⋯S(S)k=SS⋯S(S)^k = SS\cdots S para la concatenación de kkk copias de SSS . Ahora dada una cadena, podemos usar esta notación para...
¿Cómo abordaría el problema de la mochila en una situación de programación dinámica si ahora tiene que limitar el número de elementos en la mochila por una constante ? Este es el mismo problema (peso máximo de , cada artículo tiene un valor peso ) pero solo puede agregar artículo (s) a la mochila y...
Programación dinámica con gran cantidad de subproblemas. Así que estoy tratando de resolver este problema desde Interview Street: Caminata de cuadrícula (Puntuación 50 puntos) Está situado en una cuadrícula dimensional en la posición . Las dimensiones de la cuadrícula son ). En un paso, puede...
Estaba investigando programación dinámica y leí lo siguiente: A menudo, cuando se utiliza un método más ingenuo, muchos de los subproblemas se generan y resuelven muchas veces. ¿Qué es un método
En Wikipedia , se proporciona una implementación para el esquema de programación dinámica ascendente para la distancia de edición. No sigue la definición completamente; Las células internas se calculan así: if s[i] = t[j] then d[i, j] := d[i-1, j-1] // no operation required else d[i, j] :=...
Considere la siguiente declaración del problema: Dado un número inicial, usted y su amigo se turnan para restarle un cuadrado perfecto. El primero en llegar a cero gana. Por ejemplo: Estado inicial: 37 El jugador1 resta 16. Estado: 21 El jugador2 resta 8. Estado: 13 El jugador1 resta...
Uno de mis mayores tuvo una entrevista de trabajo y le preguntaron por qué se llama dinámico. No pudo responder y, después de darse por vencido, el entrevistador dijo que no había nada dinámico al respecto, simplemente se llama así. Eso me cuesta creerlo. ¿Se refiere al hecho de que los...
Usar el vector Earley como un reconocedor es bastante sencillo: cuando se alcanza el final de la cadena, solo tiene que verificar si la producción axiomática completa comenzó en la posición 0. Si tiene al menos una, entonces se acepta la cadena. Usar el vector Earley para reconstruir los árboles...
Dada una cadena sss , me gustaría encontrar la subsecuencia de repetición más larga (al menos dos veces). Es decir, me gustaría encontrar una cadena que sea una subsecuencia (no tiene que ser contigua) de tal que . Es decir, es una cadena cuyas mitades aparecen dos veces seguidas. Tenga en cuenta...