Algoritmo tipo Greedy

Vista previa del material en texto

Universidad de Guadalajara 
Centro Universitario de Ciencias Exactas e Ingenierías 
División de Tecnologías para la Integración Ciber Humana 
Departamento de Ciencias Computacionales 
Informática 
Algoritmia 
Act#3 Algoritmo tipo Greedy. 
 
 
 
 
 
 
 
 
 
 
Alumno: Valenciano Tadeo Jeremy Esau 
Código: 218431076 
Introducción 
Un algoritmo codicioso es un algoritmo que encuentra una solución 
óptima global a un problema al tomar decisiones óptimas localmente. 
Entonces: el algoritmo siempre hace lo que "parece" mejor, sin tener que 
revisar sus decisiones, y va directo a la mejor solución posible. 
El término voraz se deriva de la forma en que los datos de entrada se van 
tratando, realizando la elección de desechar o seleccionar un determinado 
elemento una sola vez. Dicho enfoque codicioso consiste en evaluar cada 
elemento bajo consideración solo una vez, descartándolo o 
seleccionándolo de modo que si se selecciona es parte de la solución y si 
se descarta no es parte de la solución, tampoco se volverá a considerar 
nunca más. Algunos de los algoritmos que funcionan bajo esta filosofía 
son los algoritmos de Prim, Kruskal y Dijkstra. 
 
Algoritmo de kruskal 
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para 
encontrar un árbol recubridor 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 de la suma de todas las aristas del 
árbol es el mínimo. 
 
Algoritmo de Dijkstra 
La idea subyacente en este algoritmo consiste en ir explorando 
todos los caminos más cortos que parten del vértice origen y que 
llevan a todos los demás vértices; cuando se obtiene el camino 
más corto desde el vértice origen hasta el resto de los vértices 
que componen el grafo, el algoritmo se detiene. 
 
Algoritmo de Prim 
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los 
grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no 
dirigido y cuyas aristas están etiquetadas. 
 
 
 
Objetivos 
• Reconocer las principales características que definen a un algoritmo 
Voraz 
• Resolver el planteamiento del problema en base a la filosofía de los 
algoritmos voraces 
• Implementar la solución en algún lenguaje de programación 
• Fomentar el pensamiento matemático para la resolución de 
problemas con un enfoque algorítmico. 
 
Desarrollo 
Paso 1: Razonamiento del problema 
El primer paso fue analizar el problema presentado y buscar alguna 
solución lo más viable posible, llegué a la conclusión de que es necesario 
un algoritmo de ordenamiento, por lo cual decidí implementar el bubbleSort 
mejorado debido a que por la cantidad de elementos de los arreglos no es 
necesario implementar algoritmos mas complejos y eficientes. Finalmente 
pude observar que al organizar dichos arreglos de manera contraria (uno 
de forma ascendente y otro descendente) se llegaría a la solución del 
problema que es encontrar la suma de productos mínima. 
 
 
Paso 2: Implementación de BubbleSort mejorado 
 
 
 
Este es el algoritmo de ordenamiento bubbleSort mejorado con una 
bandera, el cual va comparando el elemento en el cual está iterando i con 
el próximo i + 1 en caso de ser menor se intercambia, de lo contrario 
prosigue con el siguiente elemento, la bandera nos ayudara a saber si se 
siguen realizando comparaciones. Se eligió este algoritmo debido a que es 
fácil implementar y por la cantidad de los elementos de los arreglos. 
 
Paso 3: Implementación de función para calcular la suma de 
productos mínima. 
 
 
Dentro de esta función se recibe como parámetros dos arreglos y la 
longitud de estos (se asume que ambos son de la misma longitud) 
posteriormente se itera en cada una de las posiciones de los arreglos y se 
van multiplicando y sumando a la variable sum. Es importante recalcar que 
para este punto se tiene en consideración que los arreglos ya se 
encuentran ordenados de manera ascendente y descendente. 
Finalmente se imprime la suma mínima de productos. 
 
Paso 4: Resolución del Problema planteado 
 
 
 
Una vez implementados los algoritmos de ordenamiento y del calculo de la 
suma de productos mínima procederemos a definir los arreglos, así como 
a obtener la longitud de los mismos, se ordenan uno de manera 
ascendente y otro de manera descendente, para posteriormente invocar a 
la función para calcular la suma mínima de productos, la cual va recibir 
como parámetros los arreglos y la longitud de los mismos. 
 
Conclusión 
Después de haber analizado las características de los algoritmos voraces 
podemos llegar a la conclusión de que son algoritmos interesantes en los 
cuales se busca la eficiencia, por otra parte, La solución a un problema 
dado no siempre se logra mediante un algoritmo codicioso. En estos 
casos, se determina que el problema a resolver es inalcanzable, por lo que 
se necesitan otros métodos para solucionarlo. Finalmente es importante 
mencionar que este tipo de algoritmos jamás pueden reconsiderar alguna 
opción una vez tomada por lo cual pienso que puede ser alguna limitante, 
pero en términos generales llegan a ser lo suficientemente eficientes. 
Referencias 
 
• BRASSARD, G. (1997). FUNDAMENTOS DE ALGORITMIA (1a. ed.). MADRID: PRENTICE - 
HALL. 
• Palazzesi, A. (2018, October 13). El algoritmo voraz. Retrieved October 6, 2022, from 
https://www.neoteo.com/el-algoritmo-voraz/