Algoritmo

RESUMEN
Para dar una solución óptima al problema de la creación de una lista de invitados a una reunión, cumpliendo ciertas restricciones, se plantea el concepto de algoritmo dinámico; de igual forma, se hace una comparación con otros métodos algorítmicos estableciendo sus ventajas y desventajas. Por último, se muestran los pasos establecidos por la programación dinámica para la implementacióndel algoritmo y mostrar la solución siempre óptima de la creación de la lista de invitados final.

ABSTRACT
To give an optimal solution to the problem of the creation of a list of guests to a meeting, carrying out certain restrictions, there appears the concept of Dynamic programming; in the same way, a comparison with others algorithmic methods is established, showing its advantages anddisadvantages. Finally, it can be seen the steps established by the dynamic programming for the implementation of the algorithm and to show always the optimal solution of the creation of the final list of guests.

PALABRAS CLAVE: Algoritmo dinámico, solución óptima, sub-problema.

1. INTRODUCCIÓN
Un algoritmo dinámico, es un método que consiste en dividir un problema en varios sub-problemas quecumplen con la propiedad de ser dependientes uno del otro, a diferencia de la técnica de dividir y conquistar, con el objetivo de evitar la realización de cálculos ya efectuados previamente, los cuales son almacenados en una estructura de datos que generalmente representan una tabla para acceder a ellos cuando sea necesario, es decir en el instante en que se calcule el resultado global delproblema en cuestión. El desarrollo de los algoritmos dinámicos puede dividirse en cuatro características principales:
1) Caracterización de una estructura óptima.
2) Definir recursivamente el valor de una solución óptima
3) Calcular el valor de una solución óptima.
4) Construir una solución una solución óptima a partir de la información calculada.
Lo anterior conlleva a que elalgoritmo se comporte de manera eficiente a comparación con otras técnicas (fuerza bruta, dividir y conquistar entre otros); lo que en algunos textos se le denomina como “optimization”. Algunos ejemplos de situaciones abordadas por este método son: La serie Fibonacci, El viaje más barato por río, El problema de la mochila entre otros. (CORMEN et al. 2001, P. 323)
2.1. Problema
A continuación sedescribe el desarrollo de un algoritmo dinámico para dar una solución óptima en particular al siguiente problema: dada una lista de empleados pertenecientes a una empresa x, dónde cada empleado tiene un indicador numérico que constituye que tan apropiado o ameno puede ser dicho empleado en una reunión social. Lo que se desea hacer, es una lista de invitados a una reunión de tal forma que semaximice la suma de los indicadores de los invitados a la fiesta, cumpliendo con la restricción de que un empleado no puede asistir si su jefe inmediato asiste. Los datos de entrada representan una jerarquía jefe – empleado(s) con sus respectivos indicadores. El núcleo de la situación está en determinar en un instante dado quien o quienes asisten a la reunión si el jefe o sus subordinados más inmediatos.La toma de esta decisión puede alterar o no de forma descendiente el estado la jerarquía planteada desde el inicio, el estado representa un valor de verdad para cada empleado en el momento actual, que informa si asiste o no. En caso de que altere la estructura, se debe establecer de nuevo para aquellos empleados que ya han sido analizados si asisten o no, cumpliendo con las condicionesmencionadas al inicio.

1.2 ¿Porque Dinámico?
Si el objetivo es obtener siempre una solución que cumpla con las propiedades de ser óptima y eficiente el concepto de dinámico es la elección adecuada. En la siguiente tabla se muestra las ventajas y las desventajas de algunas técnicas o métodos en diseño de algoritmos con el fin de demostrar que a través de un algoritmo dinámico se obtiene una...