Trabajo




Introducción

En el diario vivir, necesitamos resolver problemas de todo tipo, los cuales cada vez se van haciendo más complejos. Es por esta razón que es de mucha utilidad utilizar herramientas que nos ayuden a resolver los problemas con un mayor grado de eficiencia.
Es aquí donde los algoritmos juegan un rol fundamental para que la resolución de estos problemas sea de la mejor forma yes de gran utilidad contar con un abanico bastante amplio de herramientas que nos ayuden a resolver los mismos, los cuales son los Esquemas Algorítmicos que veremos a continuación.





























Esquemas Algorítmicos

1. Fuerza Bruta
No es un esquema algorítmico sino más bien una solución directa poco reflexionada. Puede dar una aproximación a lasolución final y se basa primordialmente en el método de prueba y error.
Por ejemplo, un algoritmo de fuerza bruta para encontrar el divisor de un número natural n consistiría en enumerar todos los enteros desde 1 hasta n, chequeando si cada uno de ellos divide n sin generar resto.

2. Divide y Vencerás (Divide and Conquer)
Consiste en descomponer el problema en subproblemas que se resuelvenindependientemente para después combinar las soluciones o resolver el problema original. Se puede aplicar con éxito a problemas matemáticos como multiplicación de matrices, algebra, etc.
Ejemplo:
Subvector de suma máxima: Algoritmo eficiente para encontrar subcadenas dentro de un vector evitando tener que recorrer todo el vector desde cada posición.

3. Ávidos o Voraces (Greedy)
Trata deproducir un mejor resultado a partir de un conjunto de opciones. Se procede paso a paso realizando la mejor elección entre las posibles. Se emplea en la optimización, por lo que parte de una solución que puede mejorarse.
El algoritmo se orienta a la selección de la mejor solución con base a ciertas candidatas a solución.
Ejemplo:
Entregar Vuelto: Solución: vamos incluyendo secuencialmente la monedade mayor valor posible de forma que todavía no superemos la cantidad a devolver.







4. Programación Dinámica
Permite resolver un problema mediante una secuencia de decisiones, menos directo que el método voraz. Solamente al final se sabe la mejor solución de todas. Inventada por el matemático Richard Bellman en 1953. Se utilizaba una tabla para ir identificando los resultados de cadaalternativa y se basa en ecuaciones.
Ejemplo:
El problema de la mochila:
Somos ladrones y hemos entrado en la casa de un rico ex-presidente.
Tenemos una mochila de capacidad M.
Podemos llevar objetos entre una colección de N objetos A, B, C... Cada objeto tiene un volumen size y un valor val.
¿Cómo optimizar el valor de la mochila?

5. Vuelta Atrás o Retroceso (Back tracking)
Nosiguen reglas para la búsqueda de una solución, simplemente efectúan una búsqueda sistemática, probar todo lo posible hasta encontrar una solución.
Se llaman de vuelta atrás porque en caso de no encontrar una solución en alguna subtarea, se regresa a la tarea original y comienza con otra subtarea o alternativa. Se asemejan al recorrido dentro de un diagrama de árbol.
Ejemplos de problemas comunesresueltos usando Vuelta Atrás
Sudoku
Problema de los movimientos de un caballo
Las ocho reinas

6. Ramificación y Poda (Branch and Bound)
Este método es una variante del Back tracking mejorado sustancialmente. Se aplica mayoritariamente para resolver cuestiones o problemas de optimización.
La técnica de Ramificación y poda se suele interpretar como un árbol de soluciones, donde cada rama noslleva a una posible solución posterior a la actual. La característica de esta técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para “Podar” esa rama del árbol y no continuar malgastando recursos y procesos en casos que se alejan de la solución óptima.



Por...