Embed Size (px)
Citation preview
Técnicas Algorítmicas
Gonzalo Sainz-Trápaga (GomoX)
Charlas PC++ 2008www.pcmasmas.com26 de Julio de 2008
Temas
1. Problemas2. Técnicas exactas3. Técnicas aproximadas
Problemas
De decisión
•¿183287 es primo?
•¿Cuál es el mínimo de la secuencia [7,8,32]?
Elegir o proponer una solución.
De optimización
• Hallar el camino más corto entre Buenos Aires y Beijing
• Ordenar la secuencia: [1,9,34,-2,6,28]
Técnicas Exactas
Fuerza Bruta
Probar todaslas opciones.
Fuerza Bruta
Se recorre todo el universode soluciones posibles.
for cand in generarCandidatos(): if esSolucion(cand): return cand
Fuerza Bruta
for p in permutaciones(secuencia): if estaOrdenado(p): return p
Ordenar por fuerza bruta:
Fuerza Bruta
• Limitaciones
• Usos reales
Backtracking
Probar todaslas opciones,
de forma más inteligente.
Backtracking
Orden!
Backtracking
Ordenar la secuencia [3,1,2]:
Backtracking
• Podas
• Recursión
Backtracking
• Limitaciones
• Usos reales
Divide & Conquer
“Vamos por partes”- Jack el destripador
Divide & Conquer
• “Dividir”• “Conquistar”• “Combinar”
Divide & Conquer
def mergesort(l): m1 = l[0:len(l)/2] m2 = l[len(l)/2:len(l)] return combinar(mergesort(m1), mergesort(m2))
Merge sort:
Divide & Conquer
• Recursión
• Paralelismo
Divide & Conquer
• Usos reales
• Limitaciones
ProgramaciónDinámica
“Usar COBOL arruina el cerebro”
- Edsger Dijkstra
Programación Dinámica
SubestructuraÓptima
Recursión
def fibo(n): if n == 1 or n == 2: return 1 else: return fibo(n-1) + fibo(n-2)
Fibonacci:
Programación Dinámica
Programación Dinámica
fibo(n) = fibo(n-1) + fibo(n-2)
fibo(n-2) + fibo(n-3) fibo(n-3) + fibo(n-4)
fibo(n-4) + fibo(n-5)
Programación Dinámica
Solapamiento
A B
• “Top-down”
• “Bottom-up”
Programación Dinámica
tabla = {}def fibo(n): if n == 1 or n == 2: return 1 else: if n in tabla: return tabla[n] else: res = fibo(n-1) + fibo(n-2) tabla[n] = res return res
Fibonacci (top down):
Programación Dinámica
tabla = {}def fibo(n): if n == 1 or n == 2:
return 1 else: tabla[1] = fibo(1) tabla[2] = fibo(2) for i in 3…n-1: tabla[i] = tabla[i-1] + tabla[i-2] return tabla[n-1] + tabla[n-2]
Fibonacci (bottom up):
Programación Dinámica
def fibo(n): if n == 1 or n == 2:
return 1 else: t1 = fibo(1) t2 = fibo(2) for i in 3…n-1: tmp = t2 t2 = t1 + t2 t1 = tmp return t1 + t2
Fibonacci (bottom up 2.0):
Programación Dinámica
• Usos reales
• Limitaciones
Programación Dinámica
ProgramaciónLineal
• Ecuaciones lineales
• SIMPLEX
• Programación entera
Programación Lineal
Técnicas Aproximadas
"La mayor deficiencia de la raza humana es nuestra incapacidad para comprender la función exponencial."
- Albert Bartlett
Heurísticas
Metaheurísticas
Algoritmos Golosos
• Usos
• Limitaciones
Algoritmos golosos
Taboo Search
Algoritmos Genéticos
- Charles Darwin
generacion = 0poblacion = generarIndividuosAleatorios()while(generacion < 5000): padres = poblacion.tomarAlgunos() poblacion.agregar(padres.procrear()) poblacion.mutarAlgunos() poblacion.matarAlgunos() generacion++
poblacion.sort(aptitud)machoAlfa = poblacion[0]return machoAlfa
Algoritmo genético:
Algoritmos Genéticos
• Usos
• Parametrización
Algoritmos Genéticos
Otras metaheurísticas
GRASPColonias de hormigasRedes neuronales
Problemas de lasMetaheurísticas
• Confiabilidad
• Parametrización
Más opciones!
• Algoritmos aproximados
• Algoritmos híbridos
Esta charla fue traídaa ustedes por cortesía
de Lotux Neon.
¿Preguntas?
Fin.
