PREDA - UNED
Programación y Estructuras de Datos Avanzadas
Capítulo 7
Ramificación y poda
Planteamiento
• También se explora un grafo dirigido implícito
• Para problemas donde el objetivo es optimizar uno o más
criterios en la solución alcanzada
• Aplicar sólo si no hay algoritmo voraz válido (+ eficientes)
• Similar a VA (se podan ramas no viables), pero aquí se poda:
1. por factibilidad: no pueden llegar a una solución
2. por cota: no pueden mejorar el valor asignado a la solución
• Calculamos cotas optimistas/pesimistas
• El recorrido se dirige por el nodo activo más prometedor,
por lo que se requiere una cola de prioridad
• Usar montículos No se exploran los nodos en el orden
en que se generan como en VA
Estimaciones y cota
• Calculamos para cada nodo:
• Estimación optimista (EstOpt)
• Estimación pesimista (EstPes)
• Podar el nodo i en cualquiera de estos casos:
• EstOpt(i) EstPes(j), para algún nodo j generado
• EstOpt(i) Valor(s), para algún nodo solución s
• Cota (C): la usamos para implementar lo anterior
• C = max( {EstPes(j) | j generado},
{Valor(s) | solución s encontrada})
• Podar i si: EstOpt(i) C
Esquema
Creamos el montículo e inicializamos la
cota con el valor de la solución para un
caso cualquiera (estimación pesimista)
No se emplea
recursividad
Añadir:
si EstimacionPes(hijo) < cota entonces
cota EstimacionPes(hijo)
fsi
Esquema
Condición para terminar la
búsqueda: “no quedan caminos que
explorar o el mejor camino por
recorrer dará, en el mejor de los
casos, una solución igual o peor”
Añadir:
si EstimacionPes(hijo) < cota entonces
cota EstimacionPes(hijo)
fsi
Esquema
Explorar cada posible hijo
analizando si es una
solución o si hay que
insertarlo en el montículo
para seguir profundizando
en ese camino en algún Añadir:
momento. si EstimacionPes(hijo) < cota entonces
cota EstimacionPes(hijo)
fsi
Ejemplo
Objetos indivisibles
(Esquema Voraz no sirve)
• Problema de la mochila
• Objetivo: seleccionar objetos de entre o1,…on cuyos
valores son v1,…vn y sus pesos p1,…pn, maximizando el
valor total y sin superar un peso máximo P
• Representar la solución como un vector de booleanos
(indica si el objeto de la posición i se ha incluido o no)
• Estimaciones
• Optimista: cota superior al valor alcanzable
• Usar algoritmo voraz como si los objetos fueran fraccionables
• Pesimista: valor que como mínimo tendrá una solución
• Tomar la suma de los valores de los objetos que ya están metidos
en la mochila + los valores de los objetos que se puedan
incorporar sin sobrepasar el peso máximo
Ejemplo
• Problema de la mochila
• Objetivo: seleccionar objetos de entre o1,…on cuyos
valores son v1,…vn y sus pesos p1,…pn, maximizando el
valor total y sin superar un peso máximo P
• Representar la solución como un vector de booleanos
(indica si el objeto de la posición i se ha incluido o no)
• Estimaciones
• Optimista: cota superior al valor alcanzable Inicialización
• Usar algoritmo voraz como si los objetos fueran fraccionables
• Pesimista: valor que como mínimo tendrá una solución
• Tomar la suma de los valores de los objetos que ya están metidos
en la mochila + los valores de los objetos que se puedan
incorporar sin sobrepasar el peso máximo
Ejemplo
• Problema de la mochila Opción de incluir el
objeto en la mochila
• Objetivo: seleccionar objetos de entre o1,…on cuyos
valores son v1,…vn y sus pesos p1,…pn, maximizando el
valor total y sin superar un peso máximo P
• Representar la solución como un vector de booleanos
(indica si el objeto de la posición i se ha incluido o no)
• Estimaciones
• Optimista: cota superior al valor alcanzable
• Usar algoritmo voraz como si los objetos fueran fraccionables
• Pesimista: valor que como mínimo tendrá una solución
• Tomar la suma de los valores de los objetos que ya están metidos
en la mochila + los valores de los objetos que se puedan
incorporar sin sobrepasar el peso máximo
Ejemplo Opción de NO incluir el
objeto en la mochila
• Problema de la mochila
• Objetivo: seleccionar objetos
de entre o1,…on cuyos
valores son v1,…vn y sus pesos p1,…pn, maximizando el
valor total y sin superar un peso máximo P
• Representar la solución como un vector de booleanos
(indica si el objeto de la posición i se ha incluido o no)
• Estimaciones
• Optimista: cota superior al valor alcanzable
• Usar algoritmo voraz como si los objetos fueran fraccionables
• Pesimista: valor que como mínimo tendrá una solución
• Tomar la suma de los valores de los objetos que ya están metidos
en la mochila + los valores de los objetos que se puedan
incorporar sin sobrepasar el peso máximo
Ejemplo
• va añadiendo objetos por orden
• Problema de la mochila decreciente de valores específicos
• el último que añade lo considera
• Objetivo: seleccionar objetos de entre o1,…on cuyos
fraccionable
valores son v1,…vn y sus pesos p1,…pn, maximizando el
valor total y sin superar un peso máximo P
• Representar la solución como un vector de booleanos
(indica si el objeto de la posición i se ha incluido o no)
• Estimaciones
• Optimista: cota superior al valor alcanzable
• Usar algoritmo voraz como si los objetos fueran fraccionables
• Pesimista: valor que como mínimo tendrá una solución
• Tomar la suma de los valores de los objetos que ya están metidos
en la mochila + los valores de los objetos que se puedan
incorporar sin sobrepasar el peso máximo
Ejemplo
• Problema de la mochila
• Objetivo: seleccionar objetos de entre o1,…on cuyos
valores son v1,…vn y sus pesos p1,…pn,• maximizando
en este caso solo se meten
el
en la mochila si caben
valor total y sin superar un peso máximoenteros
P
• Representar la solución como un vector de booleanos
(indica si el objeto de la posición i se ha incluido o no)
• Estimaciones
• Optimista: cota superior al valor alcanzable
• Usar algoritmo voraz como si los objetos fueran fraccionables
• Pesimista: valor que como mínimo tendrá una solución
• Tomar la suma de los valores de los objetos que ya están metidos
en la mochila + los valores de los objetos que se puedan
incorporar sin sobrepasar el peso máximo
estPes=23
(alg. voraz no fraccionable)
P = 20
Valor Específico:
ratio valor/peso
• Se analiza antes el hijo con
mejor estOpt:
N0,N1,N3,N5,N7,N8,N6,…
estPes=25 Cota superior de coste:
(nueva cota de poda) forma del árbol = O(2n)
estPes=26
Solo N7
(valor de P) (nueva cota de poda → permite
podar varios nodos)
Solo N8 Será
(1ª solución, Solo Nx
valor=23 (2ª solución, la
→ Misma cota) valor=25) mejor
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
OJO con enunciados y opciones
parecidas pero NO iguales
Ejercicio de examen
OJO con enunciados y opciones
parecidas pero NO iguales
Asignación de tareas: Pastelería
• Objetivo: asignar los próximos n pedidos a cada uno de
los n pasteleros, considerando que cada uno tiene un
coste asociado para cada pastel (C[1..n, l..m]) y
obteniendo el coste total mínimo
• Usamos un montículo de mínimos para almacenar los
nodos e ir tomando los de mejor estimación (menor
coste total estimado)
• Estimaciones:
• Optimista: sumar el coste de la tareas ya asignadas con el
coste mínimo que tienen las tareas pendientes de asignar
• Pesimista: sumar el coste de los pasteles ya asignados con el
coste máximo que pueden tener los pendientes de asignar
Asignación de tareas: Pastelería
• Objetivo: asignar los próximos n pedidos a cada uno de
los n pasteleros, considerando que cada uno tiene un
coste asociado para cada pastel (C[1..n, l..m]) y
obteniendo el coste total mínimo
• Usamos un montículo de mínimos para almacenar los
nodos e ir tomando los de mejor estimación (menor
coste total estimado)
• Estimaciones:• pasteleros: vector de asignaciones
• asignados: indica si un pastelero ha
• Optimista: sumar el coste de la tareas ya asignadas con el
sido ya asignado o no
coste mínimo• k:que tienen
último lasasignado
pedido tareas pendientes de asignar
• Pesimista: sumar
• costeT:el coste
costetotal
de actual
los pasteles ya asignados con el
coste máximo• estOpt:
que pueden tener
estimación los pendientes de asignar
optimista
Asignación de tareas: Pastelería
Se inicializa el montículo con un
nodo inicial sin ningún pastelero
• Objetivo: asignar los próximos n pedidos a cada uno de
asignado a la preparación de un
los n pasteleros, considerando que cada uno tiene un
pastel, con k igual a 0, y con
costeT también 0.
coste asociado para cada pastel (C[1..n, l..m]) y
obteniendo el coste total
1
mínimo
• Usamos un montículo de mínimos para almacenar los
nodos e ir tomando los de mejor estimación (menor
coste total estimado)
• Estimaciones:
• Optimista: sumar el coste de la tareas ya asignadas
con el
coste mínimo que tienen las tareas pendientes de asignar
• Pesimista: sumar el coste de los pasteles ya asignados con el
coste máximo que pueden tener los pendientes de asignar
Asignación de tareas: Pastelería
1
• Objetivo: asignar los próximos n pedidos a cada uno de
los n pasteleros, considerando
que cada uno tiene un
coste asociado para cada pastel (C[1..n, l..m]) y
obteniendo el coste total mínimo
• Usamos un montículo de mínimos para almacenar los
nodos e ir tomando los de mejor estimación (menor
coste total estimado)
• Estimaciones:
• Optimista: sumar el coste de la tareas ya asignadas con el
coste mínimo que tienen las tareas pendientes de asignar
• Pesimista: sumar el coste de los pasteles ya asignados con el
coste máximo que pueden tener los pendientes de asignar
Asignación de tareas: Pastelería
• Objetivo: asignar los próximos nLa pedidos
pesimista esaidéntica
cada pero
uno de
calculando el mayor en lugar del menor
los n pasteleros, considerando que cada uno tiene un
coste asociado para cada pastel (C[1..n, l..m]) y
Cota superior de coste:
obteniendo el coste total mínimo tamaño del árbol = O(n!)
• Usamos un montículo de mínimos para almacenar los
nodos e ir tomando los de mejor estimación (menor
coste total estimado)
• Estimaciones:
• Optimista: sumar el coste de la tareas ya asignadas con el
coste mínimo que tienen las tareas pendientes de asignar
• Pesimista: sumar el coste de los pasteles ya asignados con el
coste máximo que pueden tener los pendientes de asignar
El viajante de comercio
• Objetivo: minimizar el coste del recorrido de un viajante
de comercio que partiendo de la ciudad origen tiene que
visitar todas las ciudades de su zona una y sólo una vez y
volver al origen
• buscar ciclos Hamiltonianos mínimos que empiezan y terminan
en el nodo 1 del grafo
• Estructuras de datos:
• Solución: vector en el que el contenido de la posición i indica la
ciudad por la que se pasa en el orden i
• Grafo: matriz de adyacencia
• Montículo: montículo de mínimos para nodos candidatos
• Estimaciones:
• Optimista: sumar al coste actual el resultado de aplicar a cada
salto pendiente el coste mínimo de todas las aristas del grafo
• Pesimista: Ninguna (puede no haber solución)
El viajante de comercio
• Objetivo: minimizar el coste del recorrido de un viajante
de comercio que partiendo de la ciudad origen tiene que
visitar todas las ciudades de su zona una y sólo una vez y
volver al origen
• buscar ciclos Hamiltonianos mínimos que empiezan y terminan
en el nodo 1 del grafo
• Estructuras de datos:
• Solución: vector en el que el contenido de la posición i indica la
ciudad por la que se pasa en el orden i
• Grafo: matriz de adyacencia
• ruta: vector de asignaciones
• Proceso: montículo de mínimos para nodos candidatos
• asignados: indica si un vértice ha
• Estimaciones: sido ya asignado o no
• Optimista: sumar
• k: última
al coste
paradaactual
asignadael resultado de aplicar a cada
salto pendiente el coste
• costeT: mínimo
coste total actualde todas las aristas del grafo
• Pesimista: Ninguna
• estOpt: (puede
estimaciónnooptimista
haber solución)
El viajante de comercio
• Objetivo: minimizar el coste del recorrido de un viajante
de comercio que partiendo de la ciudad origen tiene que
visitar todas las ciudades de su zona una y sólo una vez y
volver al origen
• buscar ciclos Hamiltonianos mínimos que empiezan y terminan
en el nodo 1 del grafo
• Estructuras de datos:
• Solución: vector en el que el contenido de la posición i indica la
ciudad por la que se pasa en el orden i
• Grafo: matriz de adyacencia
• Proceso: montículo de mínimos para nodos candidatos
• Estimaciones:
• Optimista: sumar al coste actual el resultado de aplicar a cada
salto pendiente el coste mínimo de todas las aristas del grafo
• Pesimista: Ninguna (puede no haber solución)
El viajante de comercio
• Objetivo: minimizar el coste del recorrido de un viajante
de comercio que partiendo de la ciudad origen tiene que
visitar todas las ciudades de su zona una y sólo
Añadir:una vez y
hijo.costeT <- hijo.costeT +
volver al origen grafo[i,1]
• buscar ciclos Hamiltonianos mínimos que empiezan y terminan
en el nodo 1 del grafo
• Estructuras de datos:
• Solución: vector en el que el contenido de la posición i indica la
ciudad por la que se pasa en el orden i
• Grafo: matriz de adyacencia
• Proceso: montículo de mínimos para nodos candidatos
• Estimaciones:
• Optimista: sumar al coste actual el resultado de aplicar a cada
salto pendiente el coste mínimo de todas las aristas del grafo
• Pesimista: Ninguna (puede no haber solución)
El viajante de comercio
• Objetivo: minimizar el coste del recorrido de un viajante
de comercio que partiendo de la ciudad origen tiene que
visitar todas las ciudades de su zona una y sólo una vez y
volver al origen
• buscar ciclos Hamiltonianos mínimos que empiezan y terminan
en el nodo 1 del grafo
• Estructuras de datos:
• Solución: vector en el que el contenido de la posición i indica la
ciudad por la que se pasa en el orden i
• Grafo: matriz de adyacencia
Cota superior de coste:
• Proceso: montículo de mínimos para nodos candidatos
tamaño del árbol = O(n!)
• Estimaciones:
• Optimista: sumar al coste actual el resultado de aplicar a cada
salto pendiente el coste mínimo de todas las aristas del grafo
• Pesimista: Ninguna (puede no haber solución)
Selección de tareas: cursos de
formación
• Objetivo: decidir qué cursos debe impartir un
autónomo para maximizar el beneficio total,
considerando que cada curso i aporta un beneficio bi y
requiere un tiempo ti, y habiendo recibido n solicitudes
de empresas con fecha tope d1…dn
• Una secuencia es admisible si σ𝑘𝑗=1 𝑡𝑗 ≤ 𝑑𝑘 , para todo
k entre 1 y m (ordenar por 𝑑𝑖 y comprobar)
• Estimaciones:
• Optimista: sumar el beneficio de los cursos que si empiezan
justo después de los ya seleccionados son viables
• Pesimista: sumar el beneficio de los cursos en orden por
fecha tope creciente si no superan su fecha tope
Selección de tareas: cursos de
formación
• Objetivo: decidir qué cursos debe impartir un
autónomo para maximizar el beneficio total,
considerando que cada curso i aporta un beneficio bi y
requiere un tiempo ti, y habiendo recibido n solicitudes
de empresas con fecha tope d1…dn
• Una secuencia es admisible si σ𝑘𝑗=1 𝑡𝑗 ≤ 𝑑𝑘 , para todo
k entre 1 y m (ordenar por 𝑑𝑖 y comprobar)
• Estimaciones:
• cursos: vector de selecciones
• Optimista: •sumar el beneficio de los cursos que si empiezan
k: último curso considerado
justo después de los ya seleccionados son viables
• beneficioT: beneficio total actual
• Pesimista: sumar el beneficio
• tiempoT: deactual
tiempo total los cursos en orden por
fecha tope creciente si no superan
• estOpt: estimación su fecha tope
optimista
Selección de tareas: cursos de
formación
• Objetivo: decidir qué cursos debe impartir un
autónomo para maximizar el beneficio total,
considerando que cada curso i aporta un beneficio bi y
requiere un tiempo ti, y habiendo recibido n solicitudes
de empresas con fecha tope d1…dn
• Una secuencia es admisible si σ𝑘𝑗=1 𝑡𝑗 ≤ 𝑑𝑘 , para todo
k entre 1 y m (ordenar por 𝑑𝑖 y comprobar)
• Estimaciones:
• Optimista: sumar el beneficio de los cursos que si empiezan
justo después de los ya seleccionados son viables
• Pesimista: sumar el beneficio de los cursos en orden por
fecha tope creciente si no superan su fecha tope
Selección de tareas: cursos de
formación
• Objetivo: decidir qué cursos debe impartir un
autónomo para maximizar el beneficio total,
beneficioT
considerando que cada curso i aporta un beneficio bi y
requiere un tiempo ti, y habiendo recibido n solicitudes
de empresas con fecha tope d1…dn
• Una secuencia es admisible si σ𝑘𝑗=1 𝑡𝑗 ≤ 𝑑𝑘 , para todo
k entre 1 y m (ordenar por 𝑑𝑖 y comprobar)
• Estimaciones:
• Optimista: sumar el beneficio de los cursos que si empiezan
justo después de los ya seleccionados son viables
• Pesimista: sumar el beneficio de los cursos en orden por
fecha tope creciente si no superan su fecha tope
Selección de tareas: cursos de
formación
• Objetivo: decidir qué cursos debe impartir un
autónomo para maximizar el beneficio
beneficioT total,
considerando que cada curso i aporta un beneficio bi y
requiere un tiempo ti, y habiendo recibido n solicitudes
de empresas con fecha tope d1…dn
• Una secuencia es admisible si σ𝑘𝑗=1 𝑡𝑗 ≤ 𝑑𝑘 , para todo
k entre 1 y m (ordenar por 𝑑𝑖 y comprobar)
• Estimaciones:
• Optimista: sumar el beneficio de los cursos que si empiezan
justo después de los ya seleccionados son viables
• Pesimista: sumar el beneficio de los cursos en orden por
fecha tope creciente si no superan su fecha tope
Selección de tareas: cursos de
formación
• Objetivo: decidir qué cursos debe impartir un
autónomo para maximizar el beneficio total,
considerando que cada curso i aporta un beneficio bi y
requiere un tiempo ti, y habiendo recibido n solicitudes
de empresas con fecha tope d1…dn
• Una secuencia es admisible si σ𝑘𝑗=1 𝑡𝑗 ≤ 𝑑𝑘 , para todo
k entre 1 y m (ordenar por 𝑑𝑖 y comprobar)
• Estimaciones:
• Optimista: sumar el beneficio de los cursos que si empiezan
justo después de los ya seleccionados son viables
• Pesimista: sumar el beneficio de los cursos en orden por
fecha tope creciente si no superan su fecha tope
Selección de tareas: cursos de
formación
• Objetivo: decidir qué cursos debe impartir un
autónomo para maximizar el beneficio total,
considerando que cada curso i aporta un beneficio bi y
requiere un tiempo ti, y habiendo recibido n solicitudes
de empresas con fecha tope d1…dn
• Una secuencia es admisible si σ𝑘𝑗=1 𝑡𝑗 ≤ 𝑑𝑘 , para todo
k entre 1 y m (ordenar por 𝑑𝑖 y comprobar)
• Estimaciones:
• Optimista: sumar el beneficio de los cursos que si empiezan
justo después de los ya seleccionados son viables
• Pesimista: sumar el beneficio de los cursos en orden por
fecha tope creciente si no superan su fecha tope
Cota superior de coste:
tamaño del árbol = O(2n)
Distancia de edición
• Encontrar una secuencia de transformaciones que lleven
de la cadena X=x1,…,xn a la cadena Y=y1,…,ym con un coste
mínimo, considerando nm y posibles cambios de los
siguientes tipos:
• Borrar un carácter de X, con un coste cb
• Insertar uno de los caracteres de Y en X, con un coste ci
• Sustituir un carácter de X por uno de los de Y, con coste cs
• Usamos montículo de mínimos para los nodos
• Estimaciones
• Optimista: suponer que el resto de caracteres de X coinciden con
los de Y e insertar los m-n caracteres de diferencia entre X e Y
• Pesimista: sumar al coste actual el de borrar el resto de los
caracteres de X más el de insertar los caracteres que faltan de Y
Distancia de edición
• Encontrar una secuencia de transformaciones que lleven
de la cadena X=x1,…,xn a la cadena Y=y1,…,ym con un coste
mínimo, considerando nm y posibles cambios de los
siguientes tipos:
• Borrar un carácter de X, con un coste cb
• Insertar uno de los caracteres de Y en X, con un coste ci
• Sustituir un carácter de X por uno de los de Y, con coste cs
• Usamos montículo de mínimos para los nodos
• cadena: cadena con transformaciones
• Estimaciones
• long: longitud actual
• Optimista:• suponer
k: posiciónque el resto
del último de caracteres
carácter que de X coinciden con
los de Y e insertar los m-n caracteres de diferencia entre X e Y
coincide con Y
• Pesimista:• sumar al coste actual realizadas
transf: transformaciones el de borrar el resto de los
caracteres• de X más
costeT: el total
coste de insertar
actual los caracteres que faltan de Y
• estOpt: estimación optimista
Distancia de edición
• Encontrar una secuencia de transformaciones que lleven
de la cadena X=x1,…,xn a la cadena Y=y1,…,ym con un coste
mínimo, considerando nm y posibles cambios de los
siguientes tipos:
• Borrar un carácter de X, con un coste cb
• Insertar uno de los caracteres de Y en X, con un coste ci
• Sustituir un carácter de X por uno de los de Y, con coste cs
• Usamos montículo de mínimos para los nodos
• Estimaciones
• Optimista: suponer que el resto de caracteres de X coinciden con
los de Y e insertar los m-n caracteres de diferencia entre X e Y
• Pesimista: sumar al coste actual el de borrar el resto de los
caracteres de X más el de insertar los caracteres que faltan de Y
Distancia de edición
• Encontrar una secuencia de transformaciones
que lleven
de la cadena X=x1,…,xn a la cadena Y=y1,…,ym con un coste
mínimo, considerando nm y posibles cambios de los
siguientes tipos:
• Borrar un carácter de X, con un coste cb
• Insertar uno de los caracteres de Y en X, con un coste ci
• Sustituir un carácter de X por uno de los de Y, con coste cs
• Usamos montículo de mínimos para los nodos
• Estimaciones
• Optimista: suponer que el resto de caracteres de X coinciden con
los de Y e insertar los m-n caracteres de diferencia entre X e Y
• Pesimista: sumar al coste actual el de borrar el resto de los
caracteres de X más el de insertar los caracteres que faltan de Y
Distancia de edición
• Encontrar una secuencia de transformaciones que lleven
de la cadena X=x1,…,xn a la cadena Y=y1,…,ym con un coste
mínimo, considerando nm y= cadenaY[hijo.k]
nodo.cadena[hijo.k] posiblesentonces
cambios de los
siguientes tipos:
• Borrar un carácter de X, con un coste cb
• Insertar uno de los caracteres de Y en X, con un coste ci
• Sustituir un carácter de X por uno de los de Y, con coste cs
nodo.cadena[hijo.k+1] = cadenaY[hijo.k] entonces
• Usamos montículo de mínimos para los nodos
• Estimaciones
• Optimista: suponer que el resto de caracteres de X coinciden con
los de Y e insertar los m-n caracteres de diferencia entre X e Y
• Pesimista: sumar al coste actual el de borrar el resto de los
caracteres de X más el de insertar los caracteres que faltan de Y
cadenaY[hijo.k]
cadenaY[hijo.k]
Distancia de edición
• Encontrar una secuencia de transformaciones
cadenaY[hijo.k]
que lleven
de la cadena X=x1,…,xn a la cadena Y=y1,…,ym concadenaY[hijo.k]
un coste
mínimo, considerando nm y posibles cambios de los
siguientes tipos: Añadir:
hijo.cadena nodo.cadena
• Borrar un carácter de X, con un coste cb
• Insertar uno de los caracteres de Y en X, con un coste ci
• Sustituir un carácter de X por unocadenaY[hijo.k]
de los de Y, con coste cs
• Usamos montículo de mínimos para los nodos cadenaY[hijo.k]
• Estimaciones
• Optimista: suponer que el resto de caracteres de X coinciden con
los de Y e insertar los m-n caracteres de diferencia entre X e Y
• Pesimista: sumar al coste actual el de borrar el resto de los
caracteres de X más el de insertar los caracteres que faltan de Y
Distancia de edición
• Encontrar una secuencia de transformaciones que lleven
de la cadena X=x1,…,xn a la cadena Y=y1,…,ym con un coste
mínimo, considerando nm y posibles cambios de los
siguientes tipos:
• Borrar un carácter de X, con un coste cb
• Insertar uno de los caracteres de Y en X, con un coste ci
• Sustituir un carácter de X por uno de los de Y, con coste cs
• Usamos montículo de mínimos para los nodos
• Estimaciones
• Optimista: suponer que el resto de caracteres de X coinciden con
los de Y e insertar los m-n caracteres de diferencia entre X e Y
• Pesimista: sumar al coste actual el de borrar el resto de los
caracteres de X másCotaelsuperior de coste:
de insertar los caracteres que faltan de Y
tamaño del árbol = O(3m)
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
Ejercicio de examen
Resumen de ejemplos
• Mochila (objetos con valores y pesos + peso máximo P)
- Optimista: Voraz (fraccionable)
- Pesimista: Restantes sin superar P
• Asignación de tareas: Pastelería (n costes pastelero-pastel)
- Optimista/Pesimista: Restantes con coste mínimo/máximo
• El viajante de comercio (buscar ciclos hamiltonianos)
- Optimista: Sumar arista de coste mínimo a los saltos pendientes
- Pesimista: ninguna
• Selección de tareas: cursos de formación (beneficio, tiempo, fecha tope)
- Optimista: Sumar cursos viables a continuación
- Pesimista: Sumar cursos en orden () por fecha tope sin superarla
• Distancia de edición
- Optimista: Suponer que el resto de X coincide e insertar sobrante de Y
- Pesimista: Borrar el resto de X e insertar todos los que faltan de Y
