TP: Mochila – Algoritmos voraces (página 2)

A menudo, pueden encontrarse instancias concretas del
problema donde la heurística producirá resultados muy
malos o se ejecutará muy lentamente. Aún así,
estas instancias concretas pueden ser ignoradas porque no
deberían ocurrir nunca en la práctica por ser de origen
teórico, y el uso de heurísticas es muy común en
el mundo real.

Heurísticas para encontrar
el camino más corto

Para problemas de búsqueda del
camino más corto el término tiene un significado
más específico. En este caso una
heurística es una función matemática,
h(n) definida en los nodos de un árbol de
búsqueda, que sirve como una estimación del coste del
camino más económico de un nodo dado hasta el nodo
objetivo. Las heurísticas
se usan en los algoritmos de búsqueda
informada como la búsqueda egoísta. La búsqueda
egoísta escogerá el nodo que tiene el valor más bajo en la
función heurística. A* expandirá los nodos que
tienen el valor más bajo para g(n) +
h(n), donde g(n) es el coste
(exacto) del camino desde el estado inicial al nodo
actual. Cuando h(n) es admisible, esto
es si h(n) nunca sobrestima los costes de
encontrar el objetivo; A* es probablemente
óptimo.

Un problema clásico que usa heurísticas es el
puzzle-n. Contar el número de casillas mal colocadas y
encontrar la suma de la distancia Manhattan entre cada bloque y
su posición al objetivo son heurísticas usadas a menudo
para este problema.

Efecto de las
heurísticas en el rendimiento computacional

En cualquier problema de búsqueda donde hay
b opciones en cada nodo y una profundidad d al
nodo objetivo, un algoritmo de búsqueda
ingenuo deberá buscar potencialmente entre
bd nodos antes de encontrar la solución.
Las heurísticas mejoran la eficiencia de los algoritmos de
búsqueda reduciendo el factor de ramificación de
b a (idealmente) una constante b * .Aunque
cualquier heurística admisible devolverá una respuesta
óptima, una heurística que devuelve un factor de
ramificación más bajo es computacionalmente más
eficiente para el problema en particular. Puede demostrarse que
una heurística h2(n) es mejor
que otra h1(n), si
h2(n) domina
h1(n), esto quiere decir que
h1(n) <
h2(n) para todo
n.

Heurísticas en la Inteligencia
Artificial

Muchos algoritmos en la inteligencia artificial son
heurísticos por naturaleza, o usan reglas
heurísticas. Un ejemplo reciente es SpamAssassin que usa una
amplia variedad de reglas heurísticas para determinar cuando
un correo electrónico es
spam. Cualquiera de las reglas
usadas de forma independiente pueden llevar a errores de
clasificación, pero cuando se unen múltiples reglas
heurísticas, la solución es más robusta y
creíble. Esto se llama alta credibilidad en el
reconocimiento de patrones (extraído de las estadísticas en las que
se basa). Cuando se usa la palabra heurística en el
procesamiento del lenguaje basado en reglas, el
reconocimiento de patrones o el procesamiento de imágenes, es usada para
referirse a las reglas.

Algoritmo de
Kruskal

El algoritmo de Kruskal es un algoritmo
de la teoría de grafos para encontrar un
árbol expandido mínimo en un grafo conexo y ponderado.
Es decir, busca un subconjunto de aristas que, formando un
árbol, incluyen todos los vértices y donde el valor
total de todas las aristas del árbol es el mínimo. Si
el grafo no es conexo, entonces busca un bosque expandido
mínimo (un árbol expandido mínimo para
cada componente conexa).

El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

Un ejemplo de árbol expandido mínimo. Cada
punto representa un vértice, el cual puede ser un árbol
por sí mismo. Se usa el Algoritmo para buscar las distancias
más cortas (árbol expandido) que conectan todos los
puntos o vértices. Funciona de la siguiente
manera:

• se crea un bosque B (un conjunto de árboles), donde cada
  vértice del grafo es un árbol separado
• se crea un conjunto C que contenga a todas las
  aristas del grafo
• mientras C es novacío
• • eliminar una arista de peso mínimo de
    C
  • si esa arista conecta dos árboles diferentes
    se añade al bosque, combinando los dos árboles en
    un solo árbol
  • en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene una sola componente,
la cual forma un árbol de expansión mínimo del
grafo.

Este algoritmo fue publicado por primera vez en
Proceedings of the American Mathematical Society, pp.
48–50 en 1956, y fue escrito por Joseph
Kruskal.

Complejidad del algoritmo

Siendo m el número de aristas del grafo y
n el número de vértices, el algoritmo de
Kruskal muestra una complejidad
O(m log m) o, equivalentemente, O(m
log n), cuando se ejecuta sobre estructuras de datos simples. Los tiempos de
ejecución son equivalentes porque:

• m es a lo sumo n2 y log
  n2 = 2logn es O(log
  n).
• ignorando los vértices aislados, los cuales
  forman su propia componente del árbol de expansión
  mínimo, n ≤ 2m, así que
  log n es O(log m).

Se puede conseguir esta complejidad de la siguiente
manera: primero se ordenan las aristas por su peso usando una
ordenación por comparación (comparison sort) con una
complejidad del orden de O(m log m); esto
permite que el paso "eliminar una arista de peso mínimo de
C" se ejecute en tiempo constante. Lo siguiente
es usar una estructura de datos sobre
conjuntos disjuntos
(disjoint-set data structure) para controlar qué
vértices están en qué componentes. Es necesario
hacer varias operaciones del orden de
O(m), dos operaciones de búsqueda y posiblemente
una unión por cada arista. Incluso una estructura de datos sobre
conjuntos disjuntos simple con uniones por rangos puede ejecutar
operaciones del orden de O(m) en O(m log
n). Por tanto, la complejidad total es del orden de
O(m log m) = O(m log
n).

Con la condición de que las aristas estén
ordenadas o puedan ser ordenadas en un tiempo lineal (por ejemplo
mediante counting sort o radix sort), el algoritmo puede
usar estructuras de datos de conjuntos disjuntos más
complejas para ejecutarse en tiempos del orden de O(m
α(n)), donde α es la inversa (tiene un
crecimiento extremadamente lento) de la función de
Ackermann.

Demostración de la corrección

Sea P un grafo conexo y valuado y sea
Y el subgrafo de P producido por el algoritmo.
Y no puede tener ciclos porque cada vez que se
añade una arista, ésta debe conectar vértices de
dos árboles diferentes y no vértices dentro de un
subárbol. Y no puede ser disconexa ya que la
primera arista que une dos componentes de Y debería
haber sido añadida por el algoritmo. Por tanto, Y
es un árbol expandido de P.

Sea Y1 el árbol expandido de
peso mínimo de P, el cual tiene el mayor
número de aristas en común con Y. Si
Y1=Y entonces Y es un
árbol de expansión mínimo. Por otro lado, sea
e la primera arista considerada por el algoritmo que
está en Y y que no está en
Y1. Sean C1 y
C2 las componentes de P que conecta
la arista e. Ya que Y1 es un
árbol, Y1+e tiene un ciclo y existe una
arista diferente f en ese ciclo que también conecta
C1 y C2. Entonces
Y2=Y1+e-f es también
un árbol expandido. Ya que e fue considerada por el
algoritmo antes que f, el peso de e es al menos
igual que que el peso de f y ya que
Y1 es un árbol expandido mínimo,
los pesos de esas dos aristas deben ser de hecho iguales. Por
tanto, Y2 es un árbol expandido
mínimo con más aristas en común con Y que
las que tiene Y1, contradiciendo las hipótesis que se
habían establecido antes para Y1. Esto
prueba que Y debe ser un árbol expandido de peso
mínimo.

P: Cambio de monedas (con
límite de monedas)- Algoritmos voraces
Descripción del problema

El problema del cambio consiste en disponiendo de un
sistema monetario compuesto en
esta caso por monedas de 500, 200, 100, 50, 25, 10, 5, y 1
pesetas, devolver una cantidad n de dinero utilizando el menor
número de monedas posible. Disponemos de una cantidad
ilimitada de monedas de cada tipo.

Limitaciones
que tiene la solución dada

Una limitación típica de este problema es que
no se pueda devolver una cantidad de dinero en concreto. Pero con el sistema
monetario utilizado es posible calcular el cambio para cualquier
cantidad de dinero. Por tanto, no tiene
limitaciones.

Comentario a la
solución implementada

Empleamos un array que llamamos valores
de tamaño 8 inicializado con los valores del sistema
monetario ordenado de la moneda de mayor valor a la de menor
valor. El array quedaría con estos valores: {500, 200, 100, 50,
25, 10, 5, 1}. Empleamos también otro array que llamamos
cantidades del mismo tamaño que el valores
y en el que iremos almacenando la cantidad de cada moneda que
devolvamos. Cada posición de este array se corresponde con
la misma posición del array valores. Inicializamos todas las
posiciones del array a 0.

Heurístico
empleado

Consiste en devolver siempre la moneda de mayor valor
posible sin que exceda a la cantidad que nos queda por devolver.
¿Da la solución óptima? Si. Entendiendo como
solución óptima devolver el menor número de
monedas posibles, con este sistema monetario siempre se devuelve
la solución óptima para cualquier cantidad que se
introduzca. En ocasiones dependiendo del sistema monetario que se
emplee puede encontrarse una solución no
óptima.

Código del programa
package cambio; import java.io.*

public class Cambio {

static int devolver;

static int[] valores = {500, 200, 100, 50, 25, 10, 5, 1};

static int[] caja = {3, 2, 2, 5, 6, 3, 10, 6};// Añadido 30 – 11 – 2006 por –~~~~

static int[] cantidades = {0, 0, 0, 0, 0, 0, 0, 0};

static = new BufferedReader(newInputStreamReader(

System.in));

/**

* Método que halla la
solución final.

* Rellena el array de cantidades en
función de la cantidad a
devolver @param devolver El importe que hay que devolver
*/

public static void calcular(int devolver) {

int i = 0;

while (devolver > 0) {

if ((valores[i] <= devolver) && (caja[i] > 0) /*Añadido al if 30 – 11 – 2006 por –~~~~*/) {

devolver -= valores[i];

caja[i]–; // Añadido 30 – 11 – 2006 por –~~~~

cantidades[i]++;

}

else {

i++;

}

}

}

/**
* Método auxiliar empleado para
pedir al usuario el importe que hay que devolver * y validar si es
una cantidad de dinero correcta * @return Devuelve el importe
introducido por el usuario */

private static int pedirDatos() {

int importe = 0;

System.out.println(" Introduce importe: ");

try {

importe = Integer.parseInt(teclado.readLine());

} catch (IOException e) {

}

return importe;

}

/** * Método main * @param args */

public static void main(String[] args) {

Cambio cambio1 = new Cambio();

devolver = pedirDatos();

calcular(devolver);

for (int i = 0; i < cantidades.length; i++) {

System.out.println(valores[i] + " – " + cantidades[i]);

}

}

}
Complejidad:La complejidad de este problema se
medirá en relación al tiempo empleado en rellenar el
array cantidades que variará en función del importe n a
devolver. Por tanto, su complejidad es O(n).
Problema del viajante Base
del problema

El problema del Agente
viajero es un ejemplo que muestra y analiza la
problemática que subyace tras algunos tipos de problemas
matemáticos que a priori
parecen tener una solución relativamente fácil, y en la
práctica presentan un gran problema.

La respuesta al problema es conocida, es decir se conoce
la forma de resolverlo, pero sólo en teoría, en la
práctica la solución no es aplicable debido al tiempo
que computacionalmente se precisa para obtener su resultado. Para
una mayor profundidad en el tema ver el artículo
NP-completos, del que este es un ejemplo
'maestro' asequible de entender incluso por
niños.

El problema del viajante (también
conocido como problema del viajante de comercio
o por sus siglas en inglés:
TSP) es uno de los problemas más famosos (y
quizás el mejor estudiado) en el campo de la
optimización combinatoria computacional. A pesar de la
aparente sencillez de su planteamiento, el TSP es uno de los
más complejos de resolver y existen demostraciones que
equiparan la complejidad de su solución a la de otros
problemas aparentemente mucho más complejos que han retado a
los matemáticos desde hace
siglos.

Enunciado

Sean N ciudades de un territorio. El objetivo es
encontrar una ruta que, comenzando y terminando en una ciudad
concreta, pase una sola vez por cada una de las ciudades y
minimice la distancia recorrida por el viajante. Es decir,
encontrar una permutación P =
{c0,c2,…,cn
− 1} tal que sea mínimo. La
distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x, y]
representa la distancia que hay entre la ciudad X y la ciudad
Y

La solución más directa es la que aplica la
fuerza bruta: evaluar todas
las posibles combinaciones de recorridos y quedarse con aquella
cuyo trazado utiliza la menor distancia. El problema reside en el
número de posibles combinaciones que viene dado por el
factorial del número de ciudades (N!) y esto hace que la
solución por fuerza bruta sea impracticable para valores de
N incluso moderados con los medios computacionales
actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese
capaz de calcular la longitud de cada combinación en un
microsegundo, tardaría algo más 3 segundos en resolver
el problema para 10 ciudades, algo más de medio minuto en
resolver el problema para 11 ciudades y… 77.146 años en
resolver el problema para sólo 20 ciudades.

Por ejemplo las rutas posibles entre 12 ciudades son
(479 millones) 479.001.600 combinaciones y los caminos
individuales entre ciudades son el sumatorio de las 12-1 ciudades
es decir 66.

Se puede demostrar que el requerimiento de volver a la
ciudad de partida no cambia la complejidad computacional del
problema.

Situación actual respecto de su
resolución

Desde el punto de vista práctico, el problema no
está resuelto y desde el punto de vista teórico, las
técnicas empleadas son
sólo aproximaciones. No suponen una resolución real del
TSP y sólo ofrecen soluciones aproximadas
suficientemente aceptables. Los algoritmos clásicos no son
capaces de resolver el problema general, debido a la
explosión combinatoria de las posibles soluciones. Por ello,
a su solución se han aplicado distintas técnicas
computacionales: heurísticas evolutivas, redes de Hopefield, etc.

Casuística

Hay algoritmos que se basan en una configuración
concreta del problema. Por ejemplo, algunos algoritmos de
ramificación y consolidación se pueden utilizar para
resolver problemas de entre 40 a 60 ciudades.

Otros han mejorado a éstos con técnicas
reminiscentes de la programación lineal que
permiten resolver el TSP para valores de N entre 120 y 200
ciudades. En el año 2001 se utilizó una red de 110 ordenadores para resolver el
TSP para las 15.112 poblaciones de Alemania y utilizando el
equivalente computacional a 22,5 años de un PC.

En mayo del 2004 se aplicaron algunas de estas
técnicas para la resolución del problema aplicado a las
24.978 poblaciones suecas en un ciclo de unos 72.500 km
(probándose además que no se podía encontrar un
ciclo más corto).Los algoritmos genéricos basados en
heurísticas no encuentran soluciones exactas, pero permiten
encontrar aproximaciones suficientemente buenas (un 97% de
optimización) y se pueden aplicar a conjuntos de ciudades
muy grandes (redes con millones de nodos) con tiempos de
ejecución razonables en un superordenador (semanas o
meses).

Convergencia del
problema

Una formulación equivalente en términos de la
teoría de grafos es la de encontrar en un grafo
completamente conexo y con arcos ponderados el ciclo hamiltoniano
de menor coste. En esta formulación cada vértice del
grafo representa una ciudad, cada arco representa una carretera y
el peso asociado a cada arco representa la longitud de la
carretera. El TSP está entre los problemas denominados
NP-completos, esto es, los problemas que no se pueden resolver en
tiempo polinomial en función del tamaño de la entrada
(en este caso el número N de ciudades que el viajante debe
recorrer). Sin embargo, algunos casos concretos del problema
sí han sido resueltos hasta su optimización, lo que le
convierte en un excelente banco de pruebas para algoritmos de
optimización que pertenezcan a la misma familia (lo que en jerga
matemática se denominan problemas
isomorfos).

Aplicaciones

El problema tiene considerables aplicaciones
prácticas, aparte de las más evidentes en áreas de
logística de transporte, que cualquier
negocio pequeño o grande de reparto conoce. Por ejemplo, en
robótica, permite
resolver problemas de fabricación para minimizar el
número de desplazamientos para conseguir realizar un
número determinado de perforaciones en una plancha o en un
circuito impreso. Control y operativa optimizada de
semáforos, etc.

Autora:

Diana H.