Conceptos básicos de algoritmos

Conceptos básicos de algoritmos

No existe una regla precisa para escribir un programa que resuelva un dado problema práctico. Al menos

por ahora escribir programas es en gran medida un arte. Sin embargo con el tiempo se han desarrollado un

variedad de conceptos que ayudan a desarrollar estrategias para resolver problemas y comparar a priori la

eficiencia de las mismas.

Por ejemplo supongamos que queremos resolver el “Problema del Agente Viajero” (TSP, por “Traveling

Salesman Problem”) el cual consiste en encontrar el orden en que se debe recorrer un cierto número de

ciudades (esto es, una serie de puntos en el plano) en forma de tener un recorrido mínimo. Este problema

surge en una variedad de aplicaciones prácticas, por ejemplo encontrar caminos mínimos para recorridos

de distribución de productos o resolver el problema de “la vuelta del caballo en el tablero de ajedrez”, es

decir, encontrar un camino para el caballo que recorra toda las casillas del tablero pasando una sola vez

por cada casilla. Existe una estrategia (trivial) que consiste en evaluar todos los caminos posibles. Pero esta

estrategia de “búsqueda exhaustiva” tiene un gran defecto, el costo computacional crece de tal manera con el

número de ciudades que deja de ser aplicable a partir de una cantidad relativamente pequeña. Otra estrategia

“heurística” se basa en buscar un camino que, si bien no es el óptimo (el de menor recorrido sobre todos los

posibles) puede ser relativamente bueno en la mayoría de los casos prácticos. Por ejemplo, empezar en una

ciudad e ir a la más cercana que no haya sido aún visitada hasta recorrerlas todas.

Una forma abstracta de plantear una estrategia es en la forma de un “algoritmo”, es decir una secuencia

de instrucciones cada una de las cuales representa una tarea bien definida y puede ser llevada a cabo en una

cantidad finita de tiempo y con un número finito de recursos computacionales. Un requerimiento fundamental

es que el algoritmo debe terminar en un número finito de pasos, de esta manera él mismo puede ser usado

como una instrucción en otro algoritmo más complejo.

Entonces, comparando diferentes algoritmos para el TSP entre sí, podemos plantear las siguientes preguntas

>Da el algoritmo la solución óptima?

Si el algoritmo es iterativo, >converge?

>Como crece el esfuerzo computacional a medida que el número de ciudades crece?

9

CAPÍTULO 1. DISEÑO Y ANÁLISIS DE ALGORITMOS

Sección 1.1. Conceptos básicos de algoritmos

1.1.1. Ejemplo: Sincronización de acceso a objetos en cálculo distribuido

Consideremos un sistema de procesamiento con varios procesadores que acceden a un área de memoria

compartida. En memoria

...