Divide Y Venceras

Universidad de Granada E.T.S. Ingeniería Informática

Departamento de Ciencias de la Computación e Inteligencia Artificial

Teoría de Algoritmos

Divide y Vencerás

Curso 2005 – 2006

Ingeniería Informática

1. Objetivo

El objetivo de esta práctica es que el alumno analice, diseñe e implemente un algoritmo basado en la técnica divide y vencerás para resolver el problema de obtener la subsecuencia de suma máxima en un vector.

2. Introducción

Dado un vector de números enteros V , con elementos V [i], i ∈ 1...n deseamos encontrar el valor de la expresión

max1≤i≤j≤n

( j X

k=i

V [k] )

es decir, el subvector contiguo cuya suma sea máxima.

Por ejemplo, siendo

V = {31,−41,59,26,−53,58,97,−93,−23,84}

el resultado sería 187, correspondiendo con la suma de los valores

V [3] + V [4] + V [5] + V [6] + V [7]

2.1. Algoritmos Básicos

Algoritmo 1: en una primera aproximación, intuitivamente podríamos aplicar la siguiente idea para resolver el problema: para todo i,j con

1 ≤ i ≤ j ≤ n calculamos la suma

j X

k=i

V [k] y nos quedamos con el valor

máximo encontrado. Claramente, este algoritmo es de orden cúbico.

Algoritmo 2: el algoritmo previo puede transformarse a otro de orden

cuadrático teniendo en cuenta que la suma

j X

k=i

V [k] puede obtenerse

aprovechando el cálculo previo de

j−1 X

k=i

V [k].

Algoritmo 3: otro algoritmo de orden cuadrático se puede obtener utilizando un vector auxiliar A, que sirva para almacenar las sumas parciales de manera que A[i] = V [1]+V [2]+...+V [i]. La construcción de A es de orden lineal. Luego para calcular la sumatoria entre los valores i,j de V , basta con hacer A[j] − A[i − 1]. (si quiero saber cuanto gasté entre abril y septiembre, entonces al gasto acumulado hasta septiembre debo restarle el gasto acumulado hasta marzo).

1

2.2. Algoritmo Divide y Vencerás

Veamos ahora como se puede utilizar la técnica de Divide y Vencerás para obtener un algoritmo (al que llamaremos Algoritmo 4) con una mejor eciencia. El primer paso, será dividir el problema original en tres subproblemas de menor tamaño. Los resolveremos y luego calcularemos la solucion completa a partir de las soluciones parciales. La subsecuencia de suma máxima puede encontrarse en uno de tres lugares:

1. o está en la primera mitad del vector,

2. o está en la segunda mitad del vector,

3. o contiene al punto medio del vector y se encuentra en ambas mitades.

Las tres soluciones se combinan mediante el cálculo de su máximo para obtener la suma pedida. Los dos primeros casos pueden resolverse recursivamente. Para el valor asociado

...