Tema 5

Programación Científica y HPC

Métodos algorítmicos de
resolución de problemas
 Índice
Esquema 3

Ideas clave 4
5.1. Introducción y objetivos 4
5.2. Algoritmos de ordenación 6
5.3. Algoritmos de búsqueda 15
5.4. Algoritmos voraces 18
© Universidad Internacional de La Rioja (UNIR)

5.5. Programación dinámica 19

5.6. Heurísticas 21
5.7. Referencias bibliográficas 27
5.8. Cuaderno de ejercicios 28

A fondo 40

Test 41
 Esquema
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

3
Tema 5. Esquema
 Ideas clave

5.1. Introducción y objetivos

En este tema se presentarán algoritmos de distinta naturaleza y con distintas

funcionalidades, que puedan ser aplicados sobre las estructuras de datos y los tipos
abstractos de datos o sobre algunas propuestas nuevas. Se verá primero la
conceptualización y el diseño del algoritmo y, posteriormente, su implementación en
Python.

Antes de empezar, es importante conocer la etimología de la palabra algoritmo, que

nos informará a su vez del origen. La palabra algoritmo proviene del nombre del
matemático persa del siglo IX, al-Jwārizmī. Tal y como se concibe, un algoritmo no es
más que un conjunto de reglas que se aplican para realizar algún cálculo y obtener
un resultado. Estas se podrían aplicar a mano o en una máquina.

El algoritmo más famoso es el algoritmo de Euclides (siglo III a. C.) para el cálculo del
máximo común divisor de dos números enteros.

En general, se debe tener en cuenta que la ejecución de un algoritmo no requiere

de decisiones subjetivas, ni de la intuición o la creatividad. Un algoritmo es un
conjunto de reglas que se deben ejecutar de la forma y orden que se haya
establecido. Por tanto, se puede suponer que la aplicación de las reglas
proporcionará una respuesta correcta.
© Universidad Internacional de La Rioja (UNIR)

El objetivo de usar algoritmos es el de dar solución a un problema. Sin embargo, hay

problemas para los que no se conocen algoritmos de resolución aplicables y no queda
otro remedio que tratar de encontrar algunas reglas que proporcionen una
aproximación en un tiempo razonable de la respuesta correcta, aunque tampoco
siempre es posible demostrar la bondad de la aproximación. Estos algoritmos, que se

Programación Científica y HPC

4
Tema 5. Ideas clave
 conocen como algoritmos heurísticos, o simplemente se dice que es una heurística,
tienen una base teórica mínima y se puede decir que están basados en el
«optimismo».

Como ya se ha dicho anteriormente, el objetivo de los algoritmos es la resolución de

un problema, pero no siempre existe un algoritmo único para resolverlo y, por tanto,
se deberá decidir cual usar en cada caso. La selección puede depender de factores de
tiempo de ejecución, de cantidad de espacio requerido o del tipo de los datos a los
que se aplica.

Los algoritmos se pueden clasificar por su funcionalidad, que es la clasificación

elegida para presentarlos en este tema, o por su naturaleza. De acuerdo con esta
última y, que es la que se adopta en Brassard y Bratle (1997), los algoritmos se pueden
clasificar en:

 Algoritmos voraces: con un enfoque sencillo y fáciles de implementar. Se utilizan

fundamentalmente para resolver problemas de optimización.

 Algoritmo «divide y vence»: en realidad, es una técnica que descompone el

problema en subproblemas que se resuelven de forma sucesiva e independiente
a los otros subproblemas. Es un método de refinamiento progresivo en el que se
pasa del problema completo a los subproblemas.

 Algoritmos de programación dinámica: esta es una técnica ascendente que

comienza por los subproblemas más pequeños y, mediante la combinación de sus
soluciones, se obtienen soluciones para problemas de tamaño cada vez mayor.
© Universidad Internacional de La Rioja (UNIR)

 Algoritmos probabilistas: procedimientos que efectúan elecciones aleatorias

acerca de lo que se debe realizar para encontrar una solución. Aunque su
fundamento parece que choca con la idea de algoritmo, que se concibe como un
conjunto de reglas que se aplican de forma determinista, son aceptados como
tales.

Programación Científica y HPC

5
Tema 5. Ideas clave
  Algoritmos paralelos: están pensados para la ejecución simultanea de partes del
algoritmo sobre diferentes conjuntos de datos para mejorar su complejidad
temporal.

 Algoritmos sobre grafos: Para resolver problemas que se pueden formular

mediante grafos.

 Algoritmos heurísticos: procedimientos que pueden encontrar o no una solución

y, en el caso de encontrarla, puede ser óptima, buena o no. Se aplica a problemas
en los que es difícil, o incluso no se pueda resolver, mediante un algoritmo
conocido.

En este tema se verán algunos algoritmos según su funcionalidad, que puede ser
ordenar y buscar, entre otros. Para algunos se presentarán distintas técnicas. Se
revisarán, así mismo, algunas técnicas de programación dinámica y heurísticas.

5.2. Algoritmos de ordenación

Método de la burbuja

Se trata del procedimiento de ordenación más conocido. Está considerado como uno
de los algoritmos de ordenación menos eficientes y solo se recomienda para ordenar
listas de datos pequeñas, de tamaño máximo 1 000.

Realiza múltiples pasadas por la lista de datos comparando el dato siguiente y, si no

© Universidad Internacional de La Rioja (UNIR)

están ordenados, los intercambia. Tras cada pasada, el dato de valor más grande
queda en su lugar.

Cada pasada recorrerá un elemento menos. En la Tabla 1 se muestra la ejecución de

la primera pasada, en la que queda al final el dato más grande.

Programación Científica y HPC

6
Tema 5. Ideas clave
 Tabla 1. Primera pasada del algoritmo. Fuente: elaboración propia.

A continuación, se muestra el código en Python:

© Universidad Internacional de La Rioja (UNIR)

Figura 1. Código y resultado del algoritmo de ordenación burbuja. Fuente: elaboración propia.

Vean el uso de la declaración de una variable global usada por la función, pero
que pertenece al ámbito global y, por tanto, se puede obtener su valor fuera
de ella tras la ejecución. Esto es un recurso que no se considera de muy buena

Programación Científica y HPC

7
Tema 5. Ideas clave
 práctica en programación, pero es útil. Miren también el uso del intercambio,
en el que se hacen dos asignaciones a la vez

Su complejidad en tiempo es de orden 𝑂(𝑛2 ), siendo 𝑛 el número de elementos que

se van a ordenar. Las instrucciones del bucle interno se ejecutan 𝑛 − 𝑖 veces.

Ordenación por selección

Se basa en la selección sucesiva de los valores mínimos. En cada iteración del

algoritmo se selecciona el elemento mínimo de los no ordenados y se intercambia
con el primero. Tras cada iteración se conseguirá ordenar un elemento.

En la Tabla 2 se muestra la ejecución del algoritmo, en donde cada fila representa

una iteración.

Tabla 2. Iteraciones de la ordenación por selección. Fuente: elaboración propia.

© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

8
Tema 5. Ideas clave
 A continuación, se muestra el código en Python:

Figura 2. Código y resultado del algoritmo de ordenación por selección. Fuente: elaboración
propia.

Su complejidad en tiempo es de orden 𝑂(𝑛2 ), siendo 𝑛 el número de elementos que

se van a ordenar. Las instrucciones del bucle interno se ejecutan 𝑛 − 𝑖 veces.

Ordenación por inserción

Se basa en ir examinando todos los elementos desde el segundo hasta el último e

insertarlo en el lugar adecuado entre sus predecesores.

En la tabla 3 se muestra la ejecución del algoritmo, donde cada fila representa una
© Universidad Internacional de La Rioja (UNIR)

iteración.

Programación Científica y HPC

9
Tema 5. Ideas clave
 Tabla 3. Una iteración del algoritmo por inserción. Fuente: elaboración propia.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

10
Tema 5. Ideas clave
 A continuación, se muestra el código en Python:

Figura 3. Código y resultado del algoritmo de ordenación por inserción. Fuente: elaboración
propia.

Su complejidad en tiempo es de orden 𝑂(𝑛2 ), siendo 𝑛 el número de elementos que

se van a ordenar. Las instrucciones del bucle interno se ejecutan 𝑖 veces en el peor
de los casos.

Ahora se verán ahora dos algoritmos de ordenación que aplican un esquema de

«divide y vencerás» para realizar la ordenación

Ordenación por mezcla (mergesort)

© Universidad Internacional de La Rioja (UNIR)

Consiste en dividir la lista en dos sub-listas de tamaño similar y ordenar cada una
de ellas usando la recursividad. Posteriormente, se mezclan las dos sub-listas
ordenadas manteniendo el orden.

Programación Científica y HPC

11
Tema 5. Ideas clave
 La mezcla de las dos sub-listas es más eficiente, si se cuenta con un espacio adicional
que se pueda usar como centinela.

Tabla 4. Interacciones de la ordenación por mezclas. Fuente: elaboración propia.

© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

12
Tema 5. Ideas clave
 A continuación, se muestra el código en Python:

Figura 4. Código y resultado del algoritmo de ordenación por mezcla. Fuente: elaboración propia.

Para analizar la complejidad del algoritmo se debe considerar que la división en dos
matrices requiere tiempo lineal. Fusionar también requiere tiempo lineal, de forma
© Universidad Internacional de La Rioja (UNIR)

𝑛 𝑛
que (𝑛) = 𝑡 ( 2 ) + 𝑡 (2 ) + 𝑔(𝑛) donde 𝑔(𝑛) ∈ Θ(𝑛).

𝑛
Por tanto, se produce una recurrencia de la forma 𝑡(𝑛) = 2𝑡 ( 2) + 𝑔(𝑛).

Programación Científica y HPC

13
Tema 5. Ideas clave
 Para resolver la recurrencia se aplica la ecuación (1) de resolución de recurrencias
para 𝑙 = 2, 𝑏 = 2, 𝑘 = 1.

𝛩(𝑛𝑘 ) 𝑠𝑖 𝑙 < 𝑏 𝑘
𝑛
(𝑛) ∈ {𝛩(𝑛𝑘 𝑙𝑜𝑔 𝑛) 𝑠𝑖 𝑙 = 𝑏 𝑘 , 𝑠𝑖𝑒𝑛𝑑𝑜 𝑡(𝑛) = 𝑙𝑡 ( ) + 𝑔(𝑛), (1)
𝑏
𝛩(𝑛𝑙𝑜𝑔𝑏 𝑙 ) 𝑠𝑖 𝑙 > 𝑏 𝑘

𝑠𝑖 𝑒𝑥𝑖𝑠𝑡𝑒 𝑢𝑛 𝑒𝑛𝑡𝑒𝑟𝑜 𝑘 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑔(𝑛) ∈ Θ(𝑛𝑘 )

Entonces, su complejidad en tiempo es de orden Θ(𝑛𝑙𝑜𝑔(𝑛)), siendo 𝑛 el número de

elementos que se van a ordenar.

Ordenación rápida (quicksort)

Consiste en dividir la lista en dos sub-listas de tamaño similar. La mayor parte del
trabajo no recursivo se invierte en crear las sub-listas y no en la combinación de ellas.

En la primera etapa, el algoritmo selecciona un elemento que se conoce como pivote,

la lista se parte en dos y se desplazan los elementos menores que el pivote hacia la
izquierda de este y los mayores hacia la derecha. Cada una de las partes se ordenan
mediante llamadas recursivas al algoritmo y se obtiene una lista ordenada.

La mezcla de las dos sub-listas es más eficiente si se cuenta con un espacio adicional
que se pueda usar como centinela.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

14
Tema 5. Ideas clave
 5.3. Algoritmos de búsqueda

Búsqueda secuencial

Busca un elemento dentro de una lista comenzando por el primero de ellos. Luego,
recorre la lista hasta que lo encuentra o hasta que no quedan más elementos por
consultar.

En la Figura 5 se muestra la versión iterativa del algoritmo.

Figura 5. Código y resultado del algoritmo de búsqueda secuencial. Fuente: elaboración propia.

Este algoritmo requiere, en el peor de los casos, un tiempo que está en 𝛩(𝑖), donde
𝑖 es el índice en el que está el elemento. Por tanto, está en 𝛰(𝑛) en el peor de los
casos, siendo 𝑛 el número de elementos de la lista y en 𝛰(1) en el mejor caso.
© Universidad Internacional de La Rioja (UNIR)

Como el número medio de iteraciones es 𝑛 + 1/2, esta búsqueda requiere un tiempo

promedio que está en 𝛩(𝑛).

Programación Científica y HPC

15
Tema 5. Ideas clave
 La búsqueda mejorará, si la lista está ordenada y si se puede determinar si el
elemento está en la primera mitad o en la segunda mitad de la lista. En esto se basa
el algoritmo de búsqueda binaria.

Búsqueda binaria

Es uno de los más sencillos en el que se aplica una técnica de «divide y vencerás».
Parte de la base que la lista debe estar ordenada y va reduciendo el espacio o sección
de búsqueda descartando segmentos de ese espacio en los que es seguro que el valor
no va a estar. Inicialmente, el espacio de búsqueda es la lista total.

Se tendrán en cuenta las siguientes consideraciones en cada ejecución del algoritmo:

 Se selecciona el valor central de la sección de búsqueda y si es el valor buscado se

retorna su índice.

 Si el valor central es mayor que el buscado, se descarta la parte de derecha de la

sección y la búsqueda se limita a la parte izquierda.

 Si el valor central es menor que el buscado, se descarta la parte de izquierda de la

sección y la búsqueda se limita a la parte derecha.

 Si la sección de búsqueda tiene longitud 0, significa que el valor no se encuentra

en la lista y devuelve un índice que no pueda existir, en el caso de Python-1.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

16
Tema 5. Ideas clave
 Figura 6. Código y ejecución del algoritmo recursivo de búsqueda binaria. Fuente: elaboración
propia.

El tiempo que requiere una llamada recursiva de este algoritmo es 𝑡(𝑚) donde 𝑚 =
𝑢𝑙𝑡𝑖𝑚𝑜 − 𝑝𝑟𝑖𝑚𝑒𝑟𝑜 + 1, que es el número de elementos que quedan para la
búsqueda, y el tiempo requerido para la primera llamada es 𝑡(𝑛), que es el tamaño
de la lista.

Por tanto, cuando el número de elementos que quedan por buscar en una llamada
recursiva es mayor que uno requiere una cantidad constante de tiempo, además de
𝑚
la llamada recursiva con 𝑚/2. Esto quiere decir que 𝑡(𝑚) = 𝑡 ( 2 ) + 𝑔(𝑚) con

𝑔(𝑚) ∈ Ο(1). Aplicando la ecuación (1) vista anteriormente con 𝑙 = 1, 𝑏 = 2 , 𝑘 =

© Universidad Internacional de La Rioja (UNIR)

0 se concluye que 𝑡(𝑚) ∈ Θ(log 𝑚). Luego, este algoritmo requiere un tiempo
logarítmico, incluso en el caso mejor.

Programación Científica y HPC

17
Tema 5. Ideas clave
 5.4. Algoritmos voraces

Se utilizan, fundamentalmente, para resolver problemas de optimización. Las

características relevantes de estos problemas son:

 Se cuenta con un conjunto de candidatos a ser solución del problema.

• En cada paso un candidato se incorpora al conjunto de seleccionados o
conjuntos de los rechazados, que se empiezan a construir en la primera etapa
del algoritmo.

 Existe una función que comprueba si algo es solución.

 Existe una función que comprueba si se ha encontrado una solución factible, que
será un subconjunto de los candidatos que satisfacen ciertas restricciones.

 Existe una función de selección que permite escoger un nuevo candidato de los
que quedan por comprobar.

 Se debe obtener la solución factible, que se denomina solución óptima, la cual

maximiza o minimiza una función objetivo.

En Brassard y Bratley (1997) se muestra el pseudocódigo de un algoritmo voraz.

© Universidad Internacional de La Rioja (UNIR)

Figura 7. Pseudocódigo algoritmo voraz. Fuente: basado en Brassard y Bratley, 1997.

Programación Científica y HPC

18
Tema 5. Ideas clave
 El objetivo de este problema es llenar una mochila, de forma que se maximice el valor
de los objetos transportados de acuerdo con la capacidad de esta. Los objetos
cuentan con un peso y un valor.

5.5. Programación dinámica

Es una técnica ascendente, estos algoritmos comienzan resolviendo los casos más
sencillos y combinan las soluciones para resolver casos cada vez mayores hasta
obtener la solución del problema original.

El modelado de problemas de este tipo no es el mismo para todos, para cada

problema será necesario especificar sus componentes y fases.

Se basa en el principio de optimalidad de Bellman. Este principio se enuncia de esta

forma en el diccionario de la Real Academia de Ingeniería (s. f.):

«Principio aplicado en programación dinámica que consiste en que una

secuencia óptima de decisiones que resuelve un problema debe cumplir la
propiedad de que cualquier subsecuencia de decisiones, que tenga el mismo
estado final, debe ser también óptima respecto al subproblema
correspondiente».

Este principio no es aplicable a cualquier problema y, por tanto, se debe considerar

la posibilidad de que no sea posible resolver el problema mediante programación
dinámica.
© Universidad Internacional de La Rioja (UNIR)

Las características relevantes de la programación dinámica son:

 Las decisiones se toman en secuencia.

Programación Científica y HPC

19
Tema 5. Ideas clave
  El problema se divide en etapas que dependen de una política de decisión.

 Los datos que se necesitan conocer para describir cada etapa son pocos.

 Los resultados dependen de una serie de variables.

 En cada capa se cumplen una serie de condiciones que determina el estado del
sistema asociado.

 En cada etapa, la decisión modifica los valores de las variables relacionadas y

transforman el estado de la etapa actual, en el estado de la siguiente etapa. Sin
embargo, no aumentan ni disminuye, los factores de los que depende la solución.

 El diseño del procedimiento basado en la política de decisión está pensado para

encontrar una solución óptima.

 Se resuelven todos los subcasos, para determinar los que son relevantes. Una vez
que se determinan, se combinan para encontrar la solución óptima del problema
original.

Un problema ejemplo sencillo de este tipo es el cálculo de los coeficientes de la

potencia de un binomio.

Se sabe que los coeficientes son números combinatorios que se calculan para una fila
del triángulo, a partir de números de la fila superior, entre los que se encuentra
comprendido el número que se calcula.
© Universidad Internacional de La Rioja (UNIR)

La fórmula de cálculo es:

1 𝑠𝑖 𝑘 = 0 ó 𝑘 = 𝑛
𝑛 𝑛−1 𝑛−1
( )={ ( )+( ) 𝑠𝑖 0 < 𝑘 < 𝑛
𝑘 𝑘−1 𝑘
0 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜

Programación Científica y HPC

20
Tema 5. Ideas clave
 La función que lo calcularía es:

Figura 8. Función para calcular un número combinatorio. Fuente: elaboración propia.

Nótese que para un número combinatorio cualquiera será necesario, calcular todos
los anteriores, calculándose algunos resultados varias veces. Por ejemplo, para
calcular numCombinatorio(6,4) se necesita calcular numCombinatorio(5,3) y
numCombinatorio(5,4), pero cada uno de ellos necesita calcular
numCombinatorio(4,3), que se calculará más de una vez. Su complejidad está en el
𝑛
orden de 𝛺 (𝑘 ). Se podría realizar un algoritmo más eficiente mediante el cálculo del

triángulo de Pascal con una tabla que se iría llenando línea por línea.

Características de las técnicas divide y vencerás y programación dinámica. Análisis

de las técnicas mediante el ejemplo de aplicación de la sucesión de Fibonacci.

5.6. Heurísticas

Son procedimientos que pueden producir o no una buena solución para un problema,
© Universidad Internacional de La Rioja (UNIR)

es decir, son procedimientos que puede producir una solución óptima, pero que no
es la mejor o, incluso, no encuentra una solución.

Programación Científica y HPC

21
Tema 5. Ideas clave
 Estos procedimientos se utilizan en casos de problemas en los que puede no existir
un algoritmo que lo resuelva y priman el tiempo de respuesta sobre la optimización
de la solución.

Existen heurísticas deterministas o probabilistas. En cualquier caso, se suelen aplicar

a problemas difíciles de resolver, que se suelen conocer como problemas NP-hard.

Según Rego et al. (2011) «un método heurístico es un procedimiento para resolver
un problema de optimización bien definido mediante una aproximación intuitiva, en
la que la estructura del problema se utiliza de forma inteligente para obtener una
buena solución».

Se muestra a continuación un ejemplo de un problema clásico para el que no se ha

encontrado un algoritmo que pueda resolverlo en tiempo al menos polinómico.

Problema del viajante

En el problema del viajante se cuenta con una serie de ciudades para las que se
conocen las distancias entre ellas. El viajante deberá salir de una de esas ciudades
y visitar todas las demás una vez, retornando al punto de partida y habiendo
recorrido la menor distancia posible. Se debe tener en cuenta, que encontrar los
métodos exactos para este problema necesitan un tiempo exponencial, por lo que no
son viables para un número grande de nodos.

En este caso, se trata del recorrido de un grafo del que se conoce el origen.

Se puede usar un grafo completo 𝐺 = (𝑉, 𝐸) no dirigido con tantos nodos en 𝑉 como
© Universidad Internacional de La Rioja (UNIR)

ciudades. Se deberá obtener un ciclo hamiltoniano de mínimo coste. Un ciclo

hamiltoniano es un ciclo que contiene todos los nodos de un grafo una sola vez.

Existen varias formas de tratarlo mediante métodos heurísticos. Una de las más
habituales será la forma iterativa, usando un algoritmo voraz. En cada iteración del

Programación Científica y HPC

22
Tema 5. Ideas clave
 algoritmo se seleccionaría la arista con menor distancia que no se haya considerado
todavía y que cumpla:

 No formar un ciclo con las aristas seleccionadas, excepto si es la última iteración.

 No es la tercera arista que llega a un mismo vértice de entre los seleccionados.

La Figura 9 muestra el grafo de distancias entre seis ciudades. Se han numerado las
ciudades o vértices a partir de 0 para que se entienda mejor la implementación.

Figura 9. Grafo distancias entre ciudades. Fuente: elaboración propia.

Su representación en forma de matriz sería:

© Universidad Internacional de La Rioja (UNIR)

Tabla 5. Representación matricial del grafo del problema del viajante. Fuente: elaboración propia.

Programación Científica y HPC

23
Tema 5. Ideas clave
 Según el algoritmo, se necesitan ordenar las aristas de menor a mayor distancia y se
seleccionarían {0,1},{2,4},{3,4},{1,2}.

 Por valor tocaría la {0,4}, pero no se selecciona porque no cumple ninguna de las
dos condiciones indicadas, ya que formaría un ciclo completo con las anteriores y
sería la tercera arista que llega al vértice 4.
 El siguiente que sería el {1,4} que no cierra el ciclo, pero si fuera la tercera arista
que llega al 4, tampoco se coge.
 El siguiente en valor {2,3} tampoco se selecciona por el mismo motivo que el
anterior, en este caso para el vértice 2.
 El {0,2} no se selecciona porque no cumple ninguna de las dos condiciones y el
{0,3} cierra ciclo, así que tampoco se selecciona.
 El {1,3} visitaría por tercera vez el vértice 1.

Se elegiría entonces el {3,5} y ya no se podría seleccionar ninguno más, excepto el

{0,5} que cerraría el ciclo (este caso se permite por ser el último).

En este algoritmo se reorganizarían las aristas, que son simétricas, para mostrar el
camino enlazado, es decir, se muestra el ciclo correcto y se obtiene el siguiente orden
de aristas:

{0,1}, {1,2}, {2,4}, {4,3}, {3,5}, {5,0}

el ciclo [0,1,2,4,3,5,0] y la distancia total 58.

Esta solución es bastante buena, pero no es óptima, de hecho, existe un recorrido

donde la distancia es 56 y sería:
© Universidad Internacional de La Rioja (UNIR)

{0,1}, {1,2}, {2,5}, {5,3}, {3,4}, {4,0}

Programación Científica y HPC

24
Tema 5. Ideas clave
 Figura 10. Código y ejecución de una heurística voraz para el problema del viajante. Fuente:
elaboración propia.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

25
Tema 5. Ideas clave
 Figura 10. Código y ejecución de una heurística voraz para el problema del viajante. Fuente:
elaboración propia.
© Universidad Internacional de La Rioja (UNIR)

Figura 10. Código y ejecución de una heurística voraz para el problema del viajante. Fuente:
elaboración propia.

Programación Científica y HPC

26
Tema 5. Ideas clave
 Figura 10. Código y ejecución de una heurística voraz para el problema del viajante. Fuente:
elaboración propia.

5.7. Referencias bibliográficas

Brassard, G. y Bratley, P. (1997). Fundamentos de algoritmia (1ra ed.). Prentice Hall.

Real Academia de Ingeniería. (s. f.). Principio de optimalidad de Bellman En

Diccionario de la Real Academia de Ingeniería. Recuperado en 3 de abril de 2021, de
[Link]

Rego, C., Gamboa, D., Glover, F. y Osterman, C. (2011). Traveling salesman problem
heuristics: Leading methods, implementations and latest advances. European Journal
of Operational Research, 211(3), pp. 427-441.
[Link]
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

27
Tema 5. Ideas clave
 5.8. Cuaderno de ejercicios

Ejercicio 1. Ordenación rápida (quicksort)

En la Tabla 6 se muestra el estado de la lista [35,36,17,73,8,0] en la primera etapa. En

esta, se toma como pivote 35 y se van desplazando hacia la izquierda los elementos
menores que 35, y hacia la derecha los elementos mayores que 35. Al final se coloca
el pivote en su sitio.

El proceso continúa, aplicando el algoritmo nuevamente a las sublistas de menores y

mayores

Tabla 6. Estado de la lista en las distintas etapas del algoritmo. Fuente: elaboración propia.

A continuación, se muestra el código en Python.

© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

28
Tema 5. Ideas clave
 Figura 11. Implementación y prueba del ejercicio 1. Algoritmo quicksort. Fuente: elaboración
propia.

Este algoritmo es ineficiente, si en las llamadas recursivas se produce, de forma

sistemática, que los subcasos están desequilibrados. En el peor caso requiere un
tiempo cuadrático, sin embargo, en el caso medio, su complejidad en tiempo es de
orden 𝛩(𝑛𝑙𝑜𝑔(𝑛)), siendo 𝑛 el número de elementos que se van a ordenar. Esto se
podría demostrar.
© Universidad Internacional de La Rioja (UNIR)

Brassard y Bratley (1997) proporcionan esta demostración a partir de la resolución

de recurrencias.

Programación Científica y HPC

29
Tema 5. Ideas clave
 Ejercicio 2. Implementación de la búsqueda secuencial de forma
recursiva

Solución:

En este ejercicio se muestra una implementación recursiva de la búsqueda

secuencial. Para ello, se invoca a la función que busca el elemento pasando en cada
llamada como primer elemento, el siguiente elemento al último consultado en la
llamada anterior.

Figura 12. Implementación ejercicio 2. Búsqueda secuencial recursiva. Fuente: elaboración propia.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

30
Tema 5. Ideas clave
 Ejercicio 3. Implementación de la búsqueda binaria de forma iterativa

Solución:

Figura 13. Implementación ejercicio 3. Algoritmo iterativo de búsqueda binaria. Fuente:

elaboración propia.

Ejercicio 4. Implementación del problema de la mochila mediante un

algoritmo voraz con fraccionamiento

Solución:

Esta es una de las soluciones más sencillas de este problema. Se supone que los
objetos pueden ser fraccionados. Básicamente se tiene 𝑛 objetos, que cuentan con
un peso y un valor. Se puede tomar una fracción de un objeto 𝑖. Se representa como
𝑓𝑜𝑏𝑗 𝑖
© Universidad Internacional de La Rioja (UNIR)

Se trata de maximizar
𝑛

∑ 𝑓_𝑜𝑏𝑗𝑖 𝑣𝑎𝑙𝑜𝑟𝑖
𝑖=1

Programación Científica y HPC

31
Tema 5. Ideas clave
 Sujeto a la restricción
𝑛

∑ 𝑓_𝑜𝑏𝑗𝑖 𝑝𝑒𝑠𝑜𝑖 ≤ 𝑝𝑒𝑠𝑜_𝑚𝑎𝑥𝑖𝑚𝑜

𝑖=1

Para mejorar la implementación se usará un enfoque orientado a objetos.

Las opciones para llenar la mochila sería ir escogiendo los de más valor primero, los
de menor peso, para que la mochila se llene más despacio o los objetos cuyo valor
por unidad de peso sea mayor. Es precisamente este enfoque el que se va a
implementar, ya que asegura que la solución que se encuentra es óptima.

Puede consultar la demostración en Brassard y Bratley (1997), teorema 6.5.1.

© Universidad Internacional de La Rioja (UNIR)

Figura 14. Implementación ejercicio 4. Problema de la mochila, algoritmo voraz. Fuente:

elaboración propia.

Programación Científica y HPC

32
Tema 5. Ideas clave
 Figura 14. Implementación ejercicio 4. Problema de la mochila, algoritmo voraz. Fuente:
elaboración propia.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

33
Tema 5. Ideas clave
 Figura 14. Implementación ejercicio 4. Problema de la mochila, algoritmo voraz. Fuente:
elaboración propia.

Se ve que, si el criterio de comparación es el valor, se obtiene un valor menor que si

se usa la ratio valor/peso. La solución óptima es esta última.

Se añade a continuación el algoritmo de quicksort genérico en el que se puede usar

cualquier criterio de ordenación.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

34
Tema 5. Ideas clave
 Figura 15. Algoritmo quicksort genérico que se aplica en el código 13 para ordenación Fuente:
elaboración propia.

Ejercicio 5. Problema de la mochila con programación dinámica

En este caso no se pueden fraccionar los objetos, por lo que la solución se complica
bastante. El objetivo y las restricciones son las mismas que en el ejercicio anterior.

Solución:

Para poderlo resolver, se usa una tabla con las filas representando los objetos y las
columnas, los pesos. La lista de objetos posibles se proporciona ordenada por pesos.

En este caso se ha incorporado la lista de objetos como atributo para poder rescatar
la información de estos, que se introducen en la mochila en cualquier momento.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

35
Tema 5. Ideas clave
 El algoritmo va calculando el valor por filas, suponiendo que solo se cuenta con los
objetos de la fila correspondiente y las anteriores. El valor de cada elemento de la
tabla se calcula de acuerdo con la siguiente fórmula:

𝑡𝑎𝑏𝑙𝑎[𝑖, 𝑗] = max (𝑡𝑎𝑏𝑙𝑎[𝑖 − 1, 𝑗], 𝑡𝑎𝑏𝑙𝑎[𝑖 − 1, 𝑗 − 𝑝𝑒𝑠𝑜𝑖 ] + 𝑣𝑎𝑙𝑜𝑟𝑖 )

Excepto 𝑡𝑎𝑏𝑙𝑎[0, 𝑗] = 0 𝑠𝑖 𝑗 ≥ 0.

En los casos en los que 𝑗 − 𝑝𝑒𝑠𝑜𝑖 < 0, se toma 𝑡𝑎𝑏𝑙𝑎[𝑖][𝑗] = 𝑉[𝑖 − 1, 𝑗].

En todo caso, en cada celda no puede haber valores de objetos pesen más a el
representado por la columna.

A continuación, se muestra un ejemplo de construcción de la tabla, se cuenta con 4

objetos que se muestran en cada fila y un peso máximo de 7.
© Universidad Internacional de La Rioja (UNIR)

Tabla 7. Tabla de memoria para el problema de la mochila resuelto mediante programación

dinámica. Fuente: elaboración propia.

La tabla demuestra que existe una carga óptima con valor 27. A partir de la tabla se
pueden recuperar cuáles son los objetos introducidos.

Programación Científica y HPC

36
Tema 5. Ideas clave
 El proceso sería el siguiente:

 Se toma la celda de la última fila y columna, 𝑡𝑎𝑏𝑙𝑎[3,7], se debe comprobar si el

objeto de la fila está en la mochila o no.

 𝑡𝑎𝑏𝑙𝑎[3,7] = 𝑡𝑎𝑏𝑙𝑎[2,7], pero 𝑡𝑎𝑏𝑙𝑎[3,7] ≠ 𝑡𝑎𝑏𝑙𝑎[2,7 − 〖𝑝𝑒𝑠𝑜〗_3 ] +

〖𝑣𝑎𝑙𝑜𝑟〗_3, luego el objeto 3 no está en la mochila

 Se toma ahora 𝑡𝑎𝑏𝑙𝑎[2,7] = 𝑡𝑎𝑏𝑙𝑎[1,7 − 〖𝑝𝑒𝑠𝑜〗_2 ] + 〖𝑣𝑎𝑙𝑜𝑟〗_2,

entonces el objeto 2 está en la mochila.

 Como ya se ha determinado un objeto en la mochila de valor 18, se buscará en la

fila la celda de valor 27 − 18 = 9 y peso restante 7 − 5, es decir, 𝑡𝑎𝑏𝑙𝑎[1,2].
Descontando el peso del objeto introducido, se cumple que 𝑡𝑎𝑏𝑙𝑎[1,2] =
𝑡𝑎𝑏𝑙𝑎[0,2 − 〖𝑝𝑒𝑠𝑜〗_1 ] + 〖𝑣𝑎𝑙𝑜𝑟〗_1. El objeto 1 estará en la mochila.

 El peso restante es 0, luego no encontrará ningún objeto más.

Por tanto, se introducirán en la mochila dos objetos, el objeto 1 y el objeto 2.

A continuación, se muestra la implementación del algoritmo y se prueba para los

mismos valores que en el ejercicio 3.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

37
Tema 5. Ideas clave
 Figura 16. Código ejercicio 5. Problema de la mochila con programación dinámica. Fuente:
elaboración propia.

Figura 16. Código ejercicio 5. Problema de la mochila con programación dinámica. Fuente:
elaboración propia.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

38
Tema 5. Ideas clave
 Figura 16. Código ejercicio 5. Problema de la mochila con programación dinámica. Fuente:
elaboración propia.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

39
Tema 5. Ideas clave
 A fondo
Algorithms

Geeks for Geeks ([Link]

Recurso en línea muy completo para indagar sobre algoritmos, su análisis y diseño,
además de su aplicación para la resolución de problemas

Uso de heurísticas

Fox, P. (s. f.) Usar heurísticas. Khan Academy. Usar heurísticas (artículo) | Algoritmos |
Khan Academy

Recurso para la profundización sobre el uso de heurísticas y los problemas difíciles

de resolver.

Ejercicios resueltos de programación dinámica

Wextensibles ([Link]

Recurso para profundizar sobre la programación dinámica y ejercicios resueltos

siguiendo esta técnica
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

40
Tema 5. A fondo
 Test
1. El método de ordenación de la burbuja:
A. Solo realiza una pasada por la lista de datos que va a ordenar.
B. Realiza múltiples pasadas por la lista de datos que va a ordenar.
C. Divide la lista en sub-listas y las ordena por separado.
D. Ninguna de las anteriores es verdadera.

2. El método de ordenación de selección:

A. Solo realiza una pasada por la mitad de la lista que va a ordenar.
B. Realiza múltiples pasadas por la lista de datos completa que va a ordenar.
C. Realiza múltiples pasadas por partes de la lista de datos sin ordenar.
D. Ninguna de las anteriores es verdadera.

3. El método de ordenación por inserción:

A. Busca el mínimo de los que quedan por ordenar.
B. En cada iteración coloca el primer elemento de la parte que queda por ordenar
en su lugar.
C. Divide la lista en dos sub-listas y las ordena por separado.
D. Ninguna de las anteriores es verdadera.

4. En un esquema de «divide y vencerás»:

A. Se divide el problema en subproblemas, pero no se usa recursividad para
solucionarlos.
B. Se divide el problema en subproblemas y se usa siempre una tabla de memoria
en la que se guardan los valores de los subproblemas resueltos.
© Universidad Internacional de La Rioja (UNIR)

C. Se divide siempre el problema en tres subproblemas.

D. Ninguna de las anteriores es verdadera.

Programación Científica y HPC

41
Tema 5. Test
 5. En el método de ordenación por mezcla:
A. Se divide la lista que se va a ordenar en dos listas, una con los elementos
menores que el primero y otra con los mayores, se ordenan y se concatenan.
B. Se divide la lista que se va a ordenar en dos listas de tamaño similar, y se
ordenan por separado y luego se mezclan.
C. Se divide la lista que se va a ordenar en dos listas, una con los elementos pares
y otra con los impares, se ordenan y se concatenan.
D. Ninguna de las anteriores es verdadera.

6. En el método de ordenación rápida:

A. Se cuenta con dos listas, una con los elementos menores que el pivote y otra
con los mayores, y se ordenan recursivamente.
B. Se divide la lista que se va a ordenar en dos de tamaño similar, y se ordenan por
separado y luego se mezclan
C. Se divide la lista que se va a ordenar en dos, una con los elementos pares y otra
con los impares, se ordenan y se concatenan.
D. Ninguna de las anteriores es verdadera.

7. Los algoritmos voraces:

A. Son siempre algoritmos de ordenación.
B. Son siempre algoritmos de búsqueda.
C. Se usan fundamentalmente para problemas de optimización.
D. Ninguna de las anteriores es verdadera.

8. En la programación dinámica:
A. Se divide el problema en subproblemas y se usa la recursividad para
solucionarlos.
© Universidad Internacional de La Rioja (UNIR)

B. Se divide el problema en subproblemas y se usa una estructura en la que se

guardan los valores de los subproblemas resueltos.
C. Se divide siempre el problema en tres subproblemas.
D. Ninguna de las anteriores es verdadera

Programación Científica y HPC

42
Tema 5. Test
 9. Una heurística:
A. Siempre produce soluciones óptimas.
B. Siempre encuentra una solución.
C. Puede no encontrar una solución o, si la encuentra, que no sea óptima.
D. Ninguna de las anteriores es verdadera

10. Un ciclo hamiltoniano es:

A. Es un ciclo en el que aparecen todos los nodos de un grafo una sola vez.
B. Es un ciclo en el que aparecen todos los nodos de un grafo dos veces.
C Es un ciclo en el que aparecen todos los nodos de un grafo con todos sus
sucesores, aunque estos ya estuviesen en el ciclo.
D. Ninguna de las anteriores es verdadera.
© Universidad Internacional de La Rioja (UNIR)

Programación Científica y HPC

43
Tema 5. Test