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

...