Eficiencia de Algoritmos

INTRODUCCION
Hemos escuchado que: “Si se sabe resolver un problema, siempre se puede encontrar una solución” esta frase se escucha muy obvia pero no siempre es así.
Por ejemplo, si tenemos el siguiente problema que se nos presenta a continuación comenzaríamos a bacilar acerca de la veracidad de la anterior frase:
Un viajante de Piura desea viajar por las mejores 50 ciudades de todo el paíscon la finalidad de conocer más acerca de nuestra historia, el problema que se le plantea a este viajante seria, cual debería ser el itinerario que le permita recorrer la mínima distancia para tener menos gastos.
Este problema está dentro de la Teoría de Grafos. Consiste en "encontrar un circuito hamiltoniano en un grafo". Y no siempre existe tal circuito. Este es un problema que permaneceabierto: no se conoce ningún criterio que permita distinguir los grafos hamiltonianos de los que no lo son.
Pero si el grafo es completo, siempre existe. Supongamos entonces que el grafo es completo, es decir que desde cualquier ciudad (vértice) se puede llegar a cualquier ciudad, mediante una carretera que no pasa por ningún otro vértice.
Para resolver el problema podríamos seguir los siguientespasos:

1. Se obtienen todos los itinerarios posibles que partiendo de Piura llegan a Piura, recorriendo las 50 ciudades.
Veamos un ejemplo para 3 ciudades. Construimos el grafo del problema, tal y como se observa en la siguiente figura: cada par de ciudades quedan unidas por una arista, y el número sobre cada una, refleja el coste en km. que implica recorrerla, en un sentido o en otro (es un grafono dirigido).
Una posible solución al problema sería A-C1-C3-C2-A. Es decir, salir de Piura, ir a C1, luego a C3, luego a C2, y finalmente volver a Piura. En este caso, el coste en kilómetros, sería: 7 + 10 + 2 + 3 = 22 km. ¿Cuantos posibles caminos de estas características hay? Pues 3! = 6.
Circuito hamiltoniano
Costo
P-C1-C2-C3-P
7 + 5 + 2 + 8 = 22
P-C1-C3-C2-P
7 + 10 + 2 + 3 = 22P-C2-C1-C3-P
3 + 5 + 10 + 8 = 26
P-C2-C3-C1-P
3 + 2 + 10 + 7 = 22
P-C3-C1-C2-P
8 + 10 + 5 + 3 = 26
P-C3-C2-C1-P
8 + 2 + 5 + 7 = 22










2. Seleccionamos el camino que tenga mínimo coste.
Observamos cuatro posibles soluciones: la uno, la dos, la cuatro y la seis. Cualquiera de ellas nos resolvería el problema.
¿Qué ocurre al aplicar este algoritmo a nuestro problema?
Veamos:el número total de circuitos hamiltonianos sería:
50! = 30414093201713378043612608166064768844377641568960512000000000000
Supongamos que un ordenador tarda un segundo en obtener y evaluar cada circuito: esto supondría que estaría trabajando 9.644245688·1056 años. ¡Y todavía le quedaría encontrar el circuito hamiltoniano de coste mínimo entre ese en enorme número de soluciones posibles!
Sabemosresolver el problema, pero no podemos encontrar una solución, al menos, por este método.
El ejemplo anterior nos lleva a estudiar una cuestión: "la dificultad de los problemas". Podemos saber resolver un problema y no poder encontrar una solución. Hay problemas que el ordenador puede resolver con un tiempo computacional aceptable, y otros que no. Por ejemplo, para la obtención de la solución delas soluciones de una ecuación polinómica de tercer grado, tiene un coste computacional bajo. Es un problema fácil. Pero la obtención de un ciclo hamiltoniano en un grafo completo tiene un coste computacional muy alto.


EFICIENCIA DE ALGORITMOS

NOCION DE EFICIENCIA

Dados dos algoritmos distintos que solucionan un mismo problema, sus propiedades son probablemente distintas, tardantiempos distintos en solucionar el problema (eficiencia temporal).Precisan de tamaños de almacenamiento distintos (eficiencia espacial).

Una pregunta obvia que surge a la hora de considerar ambos algoritmos es: ¿cuál de ambos es mejor?

• Lógicamente, el que menos tiempo emplee y menos espacio de almacenamiento necesite
• Habitualmente, nuestro objetivo principal será mejorar la eficiencia...