¿Qué algoritmo debemos emplear para la resolución de un problema?
Atendiendo a la naturaleza del problema las posibilidades son muchas y muy variadas, de echo casi todos los problemas se pueden resolver con cualquier esquema algorítmico pero no todos son igual de eficientes a la hora de resolverlo, por eso vamos a hacer una pequeña guía de los esquemas algorítmicos básicos y los problemas que se pueden resolver con ellos.
Los esquemas algorítmicos más comunes son los siguientes:
Y con cada uno de ellos podemos resolver infinidad de problemas pero los más comunes a resolver con cada tipo son los siguientes:
Algoritmos Voraces:
-Encontrar árboles de recubrimiento mínimo (algoritmo de Prim y algoritmo de Kruskal)
-Encontrar camino de coste mínimo (algoritmo de Dijkstra)
-Problemas de minimización de tiempo en un sistema
-Planificar con plazos
-Almacenamiento óptimo en soportes secuenciales
-El típico problema de la mochila con objetos fraccionables
-Mantener la conectividad en una red, en un sistema, etc
-Problema de mensajería
-Robot desplazándose por un circuito
-Sistema de asistencia
Divide y Vencerás:
-Ordenación por fusión (Mergesort)
-Problema del puzzle Tromino
-Ordenación rápida (Quicksort)
-Cálculo del elemento mayoritario de un vector
-Organizar liga de equipos
-Calcular Skyline de una ciudad
Programación Dinámica:
-Cálculo de coeficientes binomiales
-Problemas de devolución de cambio
-Viaje por el río
-La mochila
-Multiplicación Asociativa de Matrices
-Calcular el camino de coste mínimo entre nodos en un grafo dirigido
-Problemas de distancia de edición
Vuelta Atrás:
-Coloreado de grafos
-Ciclos Hamiltonianos
-Subconjuntos de una suma dada
-Reparto equitativo
-Robot en busca de un tornillo
-Asignación de cursos en una escuela
Ramificación y Poda:
-Asignación de tareas
-Viaje de comercio
-Selección de tareas
-Distancia de edición
No hay comentarios:
Publicar un comentario