Zusammenfassung der Ressource
Tipos de Algoritmos
- Algoritmo
Voraz
- El denominado “algoritmo voraz” sigue una estrategia
sencilla pero eficaz. Simplemente, se trata de elegir la
opción óptima en cada paso local, con la esperanza de
llegar a una solución general óptima.
- Caracteristicas
- 1- El problema a resolver debe ser
optimizado[MAZ-MIN], debe existir una función que
es la que hay que minimizar o maximizar
- 2-Dominio, son un conjunto de valores posibles
para cada una de las variables de la función
objetivo.
- 3-Pueden existir un conjunto de restricciones
que imponen condiciones a los valores del
dominio que pueden tomar las variables de
función de la función objetivo
- 4-La solución para el problema
debe ser dada en forma de
secuencia de decisiones.
- Función
- Se emplean sobre todo para resolver
problemas de optimización, como
por ejemplo, encontrar la secuencia
óptima para procesar un conjunto
de tareas por un computador, hallar
el camino mínimo de un grafo, etc.
- Ventajas
- El tiempo de ejecución: al tomar siempre la
solución más prometedora, la complejidad
es lineal en el número total de decisiones.
- Fáciles de implementar
- Soluciones
eficientes
- Desventajas
- No todos los problemas se pueden
solucionar con este tipo de
algoritmos
- Dificultad para encontrar un modo
de selección optimo para el
problema
- Ejemplos
- 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. En otras palabras, el algoritmo
encuentra un subconjunto de aristas que forman un
árbol con todos los vértices, donde el peso total de
todas las aristas en el árbol es el mínimo posible. Si el
grafo no es conexo, entonces el algoritmo encontrará el
árbol recubridor mínimo para uno de los componentes
conexos que forman dicho grafo no conexo.
- Integrantes grupo: Didier
Stuard Díaz B72582,
Yamsineth Vargas B88189,
Laura Masis Brenes B74530,
Gerald Ramírez B89056
- Divide y
vencerás
- ¿Como funciona este tipo de algoritmo?
Separa un problema en sub problemas
para resolver el problema original con
mayor eficacia.
- ¿Qué características tiene? Se divide en 3 partes:
Divide el problema en un número de sub
problemas. Vence los sub problemas al resolverlos
de manera recursiva. Combina las soluciones de
los sub problemas para resolver el problema
original.
- ¿Para que sirven y en que se usan? Sirve
para resolver problemas complejos y
extensos, se usan en problemas de
ordenamiento, o búsquedas.
- Ventajas
- • Resolución de problemas
complejos
- • Eficiencia del
algoritmo
- • Paralelismo (Realizar varios cálculos
simultáneamente)
- Desventajas
- • Lentitud en la repetición del proceso
recursivo
- • Dificultad o incluso inconveniencia de
aplicar el método a situaciones en las
que la solución al problema general no
se deriva de la suma directa y simple
de los sub problemas (parte)
- Ejemplos
- • Búsqueda Binaria • Encontrar el
elemento máximo en un array.
• Merge -sort(Ordenar array).
• Quick -sort(Ordenar rápido un
array)
- Algoritmos
Probabilísticos
- ¿Cómo funciona? dan una respuesta utilizando
criterios basados en la utilización de números
aleatorios. La salida depende no sólo de la entrada,
y esta componente aleatoria hace que el programa
pueda comportarse de forma distinta en dos
ejecuciones con los mismos parámetros de
entrada.
- Características:
- Existen varios tipos de algoritmos probabilísticos
dependiendo de su funcionamiento, pudiéndose
distinguir: • Algoritmos numéricos, que
proporcionan una solución aproximada del
problema. • Algoritmos de Montecarlo, que
pueden dar la respuesta correcta o respuesta
erróneas (con probabilidad baja). • Algoritmos
de Las Vegas, que nunca dan una respuesta
incorrecta: o bien no encuentran la respuesta
correcta e informan del fallo
- ¿En que se
usa?
- Se puede optar por la elección aleatoria si se tiene un problema
cuya elección óptima es demasiado costosa frente a la decisión
aleatoria.
- Ventajas
- • Diferentes soluciones
• Aumentar la
posibilidad de encontrar
la solución correcta
• Mayor eficiencia en
tiempo y memoria
- Desventajas
- • Un algoritmo probabilista puede equivocarse
siempre que esto ocurra con una probabilidad
pequeña para cada dato de entrada. • El análisis de
los algoritmos probabilistas es, a menudo, muy
difícil.
- Ejemplo
- La aguja de Buffon Si se tira una aguja de longitud μ a un suelo hecho con tiras de madera de
anchura w (w≥μ), la probabilidad de que la aguja toque más de una tira de madera es p=2μ/wπ.
Aplicación: Una aplicación del teorema de Buffon es utilizarlo para predecir el valor de π. Sea
μ=w/2, entonces p=1/π. Si se tira la aguja un número de veces n suficientemente grande y se
cuenta el número k de veces que la aguja toca más de una tira de madera, se puede estimar el
valor de p: k ~ n/p → p ~ n/k.
- Búsqueda
exhaustiva
- Función Búsqueda exhaustiva , es una técnica trivial pero a menudo
usada, que consiste en enumerar sistemáticamente todos los
posibles candidatos para la solución de un problema, con el fin de
chequear si dicho candidato satisface la solución al mismo.
- Características
- Se utiliza para resolver problemas para los que no existe un algoritmo eficiente
para resolverlos. • Mediante la programación paralela se intentara reducir el
tiempo de ejecución de estos algoritmos
- ¿En que se
usa?
- Es un método utilizado cuando es más importante una
implementación sencilla que una mayor rapidez. Este puede ser el
caso en aplicaciones críticas donde cualquier error en el algoritmo
puede acarrear serias consecuencias; también es útil como método
"base" cuando se desea comparar el desempeño de otros
algoritmos metaheurísticos.
- Ventajas
- Es un algoritmo simple Es la más
simple y busca en todo el espacio de
solución. Enumera todos los posibles
candidatos para la solución.
Encuentra una solución
- Desventajas
- Depende de N el número de N posiciones a
compararse y por ende el tiempo de ejecución
Requiere un determinado espacio
- Ejemplo
- Problema del agente viajero Dada una lista
de n ciudades y las distancias entre cada
par de ellas, encontrar el recorrido (ruta)
más corto posible que visita cada ciudad
exactamente una vez y regresa a la ciudad
origen.
- Programación
dinámica
- 1- ¿Cómo funciona este tipo de Algoritmo? Divide
el problema en subproblemas. Se divide en dos
etapas:
- Etapa de Análisis:
- Analiza el problema desde su
última etapa y calcula todas as
opciones posibles y lo agrega a
una tabla de resultados
obtenidos, luego hace lo mismo
con la etapa anterior a esa y así
secuencialmente hasta llegar a
la primera etapa.
- Etapa de decisión:
- Una vez guardadas las opciones
empieza desde la primera etapa
y decide la mejor opción, y así
secuencialmente hasta llegar a la
última etapa para finalmente dar
una solución.
- 2- Características
- - El tiempo de ejecución puede mejorarse secuencialmente.
- Divide el problema en subetapas - Es un método capaz de
resolver problemas eficientemente.
- ¿Para qué sirve?, ¿en qué se usa?
- - Sirve para resolver problemas complejos
caracterizados por decisiones que se
deben tomar de manera secuencial. Se usa
principalmente para resolver problemas de
alta complejidad.
- - Ventajas:
- Eficaz para resolver problemas de gran complejidad al
dividirlo y secuenciarlo. Resuelve cada subproblema de
una sola vez. Los cálculos de cada etapa se organizan y se
guardan de manera eficiente facilitando su consulta para
posteriores análisis.
- Desventajas
- Si la red es muy grande se vuelve laborioso. No
aplicable a todo tipo de problemas. Si hay un
error en una tabla afecta a todo el problema.
- Ejemplo
- Un autobús necesita desplazarse de un punto A a un punto B, pero hay diferente rutas
para llegar al destino, el algoritmo va a hacer un recorrido desde el punto B hasta el A,
va a guardar las distancias de las rutas para finalmente analizarlas y dar como
solución la ruta más corta.