3 Algoritmos voraces 4 Backtracking

ALG
3
QP 07-08
Algoritmos voraces
1. Dado un grafo G, definimos el grado de un v´ertice u ∈ V (G), como el n´
umero de sus vecinos
dG (u) = |v ∈ V | (u, v) ∈ A(G)}|.
Dado un subconjunto de v´ertices, U ⊆ V (G), el subgrafo inducido per U es el grafo
G[U ] = (U, A ∩ U × U ).
Definimos el grado de un subconjunto de v´ertices como
d(U ) = min dG[U] (u).
u∈U
Consideramos el problema siguiente: Dados un grafo G = (V, A), y un natural m, decidir si
existex U ⊆ V tal que d(U ) > m, y en caso de que lo haya obtener un subconjunto U que
cumpla la propiedad.
Proponed un algoritmo voraz para este problema. Calcula una soluci´on? Por qu´e? Que
complejidad tiene?
2. Considerad el problema Max Cut Dado un grafo G = (V, A) queremos obtenir un subconjunt
A de v´ertices de V tal que el n´
umero de aristas (u, v) con u ∈ A y v 6∈ A es m´aximo.
Proponed un algoritmo voraz para el problema MaxCut. Calcula una soluci´on ´optima? Por
qu´e? Que complejidad tiene?
4
Backtracking
1. Consideramos el problema:
BinPacking (bp)
Dado un conjunto de n objetos, y para cada objeto u un tama˜
no s(u) ∈ [0, 1]. Buscar
una manera de repartir todos los objetos en contenedores, tal que la suma del tama˜
no
de los objetos en cada contenedor no exceda 1, y tal que el n´
umero de contenedores
utilizados sea m´ınimo. Los objetos no se pueden fraccionar.
Consideramos las siguientes estrategias voraces:
First Fit
Colocar el siguiente objeto en el primer contenedor en el que se pueda colocar.
Best Fit
Colocar el siguiente objeto en el contenedor mas lleno en el que cabe el objeto. En caso de
que haya m´
as de uno, seleccionar el contenedor con ´ındice menor.
First Fit Decreasing
Reordenar U , de manera que s(u1 ) > s(u2 ) > · · · > s(un ), aplicar First Fit.
¿Alguno de los algoritmos propuestos resuelve el problema bp?. ¿Qu´e coste tienen? Justifica tu respuesta. Si ninguno de ellos calcula la soluci´on ´optima propon un algoritmo de
backtracking para el problema.
2. Dise˜
nad y analizar el coste de un algoritmo de backtracking para resolver los problemas
•
•
•
•
min-clique
min-color
set-packing
min-bis
5
Programaci´
on din´
amica
1. Consider the problem of storing n books on shelves in a library. The order of the books is
fixed by the cataloging system and so cannot be rearranged. Therefore, we can speak of a
book bi , where 1 6 i 6 n, that has a thickness ti and height hi . The length of each bookshelf
at this library is L.
Suppose all the books have the same height h and the shelves are all separated by a distance
of greater than h, so any book fits on any shelf. The greedy algorithm would fill the first
shelf with as many books as we can until we get the smallest i such that bi does not fit,
and then repeat with subsequent shelves. Show that the greedy algorithm always finds the
optimal shelf placement, and analyze its time complexity.
2. This is a generalization of the previous problem. Now consider the case where the height
of the books is not constant, but we have the freedom to adjust the height of each shelf to
that of the tallest book on the shelf. Thus the cost of a particular layout is the sum of the
largest book on each shelf.
• Give an example to show that the greedy algorithm of stuffing each shelf as full as
possible does not always give the minimum overall height.
• Give a dynamic programming algorithm for this problem, and analyze its time complexity.
3. Let P be a pattern string and T a text string over the same alphabet. The edit distance
between P and T is the smallest number of changes sufficient to transform a substring of T
into P , where the changes may be:
• Substitution – two corresponding characters may differ: KAT and CAT.
• Insertion – we may add a character to T that is in P : change CT with CAT.
• Deletion – we may delete from T a character that is not in P .
(a) Compute the edit distance between P = ABCDEFGHIJKL and T = BCDEFFGHIXKL.
(b) Design a dynamic programming algorithm to compute the edit distance between a given
pattern and text.
4. Let’s assume that we are working with base 2 integers. We start by writing an integer x
with n nbits as x1 2n/2 + x0 . In other words x1 are the high order n/2 bits and x0 are the
lower order n/2 bits. Similarly we write y as y1 2n/2 + y0 . Thus we have
xy = (x1 2n/2 + x0 )(y1 2n/2 + y0 )
= x1 y1 2n + (x1 y0 + x0 y1 )2n/2 + x0 y0 .
This equation reduces the problem of computing the product of two n-bit numbers to the
problem of computing 4 products of n/2-bit numbers. Design a divide and conquer algorithm
for computing the product of two n-bit numbers using the above recurrence and analyze its
cost.
A second recurrence can be defined as follows. Set p = (x1 + x0 )(y1 + y0 ), then
xy = x1 y1 2n + (p − x1 y1 − x0 y0 )2n/2 + x0 y0 .
Design a divide and conquer algorithm for computing the product of two n-bit numbers
using the above recurrence and analyze its cost.
Compare the efficiency of both algorithms.

Download Report