fuerza bruta - voraces

DISEÑO DE ALGORITMOS

René Fabián Zúñiga Muñ[email protected]

2016

ALGORITMO DE FUERZA BRUTA

• La ruta mas corta.• La solución más obvia: Evaluar todas las

posibles rutas para luego compararlas y encontrar la más corta.

• Enumerar los candidatos • La implementación se complica al tener que

evaluar muchos nodos (crece exponencialmente).


• Un algoritmo de fuerza bruta para encontrar el divisor de un número natural n consistiría en enumerar todos los enteros desde 1 hasta n, chequeando si cada uno de ellos divide n sin generar resto.

• Otro ejemplo de búsqueda por fuerza bruta, en este caso para solucionar el problema de las ocho reinas (posicionar ocho reinas en el tablero de ajedrez de forma que ninguna de ellas ataque al resto), consistiría en examinar todas las combinaciones de posición para las 8 reinas (en total 64! /56! = 178.462.987.637.760 posiciones diferentes), comprobando en cada una de ellas si las reinas se atacan mutuamente.

https://es.wikipedia.org/wiki/Factorial


• La búsqueda por fuerza bruta se usa habitualmente cuando el número de soluciones candidatas no es elevado, o bien cuando éste puede reducirse previamente usando algún otro método heurístico.

• Es un método utilizado también 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. La búsqueda de fuerza bruta puede ser vista como el método metaheurístico más simple.


• Grafos– Creación de nodos– Asignación de rutas entre dos puntos– Distancia entre cada punto

• Arreglos– Comparación de patrones– Repeticiones sucesivas– Consume recursos y tiempo


Algoritmos En C++. Robert Sedgewick

https://www.google.com.co/search?tbo=p&tbm=bks&q=inauthor:%22Robert+Sedgewick%22&source=gbs_metadata_r&cad=6


DISEÑO DE ALGORITMOS - Algoritmos de Fuerza Bruta.

Algoritmos En C++. Robert Sedgewick




//Algoritmo para resolver el problema de búsqueda de cadenas//Entrada:// X: Cadena de texto// Y: Cadena a buscar dentro de la cadena X// n: Longitud de la cadena X// m: Longitud de la cadena Y.//Valor de retorno:// posición en la cual se encuentra Y dentro de X// -1 si Y no se encuentra dentro de X.algoritmo subcadenaFB(X,Y,n,m) para i=1 hasta n – m j=0 mientras j <= m and X[i+j] = Y[j] j=j+1 fin_mientras si j = m retornar i fin_para retornar -1fin_algoritmo


Deitel – Como programar en Java - Ejercicio en clase(Triples de Pitágoras) Un triángulo rectángulo puede tener lados cuyas longitudes sean valores enteros. El conjunto de tres valores enteros para las longitudes de los lados de un triángulo recto se conoce como triple de Pitágoras (o triples pitagóricas). Las longitudes de los tres lados deben satisfacer la relación que establece que la suma de los cuadrados de los lados es igual al cuadrado de la hipotenusa. Escriba una aplicación para encontrar todos los triples de Pitágoras para lado1, lado2 y la hipotenusa, que no sean mayores a 500. Use un ciclo for triplemente anidado para probar todas las posibilidades.


Deitel – Como programar en Java - Ejercicio en clase

public class UsaDeitel_5_21 { public static void main(String args[]) { Deitel_5_21 miObjeto = new Deitel_5_21();miObjeto.Pitagoras(); }}

public class Deitel_5_21 {public int Tamano = 500; public void Pitagoras() {System.out.print("\n Este programa prueba e imprime todas las ternas"); System.out.printf(" pitagoricas para numeros no mayores que %d ", Tamano); System.out.print(" mediante la fuerza bruta.\n"); for ( int i = 1; i <= Tamano; i++ ) for ( int j = 1; j <= Tamano; j++ ) for ( int k = 1; k <= Tamano; k++ ) { if ( i*i == j*j + k*k ) System.out.printf("%3d\t%3d\t%3d\n", i, j, k); } }}

ALGORITMO VORAZ

• Avido, devorador o goloso• Sigue una heurística consistente en elegir la

opción óptima en cada paso local con la esperanza de llegar a una solución general óptima.

• Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.

ALGORITMO VORAZ

• Dado un conjunto finito de entradas , un algoritmo voraz devuelve un conjunto (seleccionados) tal que y que además cumple con las restricciones del problema inicial.

• A cada conjunto que satisfaga las restricciones se le suele denominar prometedor, y si este además logra que la función objetivo se minimice o maximice (según corresponda) diremos que es una solución óptima.

ALGORITMO VORAZ

Habitualmente, los elementos que intervienen son:1. Un conjunto o lista de candidatos (tareas a procesar, vértices del grafo, etc)2. Un conjunto de decisiones ya tomadas (candidatos ya escogidos)3. Una función que detemina si un conjunto de candidatos es una solución al

problema (aunque no tiene por qué ser la óptima)4. Una función que determina si un conjunto es completable, es decir, si

añadiendo a este conjunto nuevos candidatos es posible alcanzar una solución al problema, suponiendo que esta exista

5. Una función de selección que escoge el candidato aún no seleccionado que es más prometedor

6. Una función objetivo que da el valor/coste de una solución (tiempo total del proceso, la longitud del camino, etc) y que es la que se pretende maximizar o minimizar;

ALGORITMO VORAZ

Candidatos

Decisiones ya tomadas(candidatos ya escogidos)

Conjunto de candidatos es una solución al problema

Conjunto es completable

Escoge el candidato aún no seleccionado que es

más prometedor

Función objetivo que da el valor/coste de una

solución

ALGORITMO VORAZ

Los algoritmos voraces proceden por pasos. 1. Inicialmente el conjunto de candidatos es vacío. 2. En cada paso, se intenta añadir al conjunto el mejor

candidato de los aún no escogidos, utilizando la función de selección.

3. Si el conjunto resultante no es completable, se rechaza el candidato y no se le vuelve a considerar en el futuro.

4. En caso contrario, se incorpora al conjunto de candidatos escogidos y permanece siempre en él.

5. Tras cada incorporación se comprueba si el conjunto resultante es una solución del problema.

ALGORITMO VORAZ

ALGORITMO VORAZ

• Los elementos del esquema anterior se convierten en:• Candidato: conjunto finito de monedas de, por ejemplo, 1, 5,

10 y 25 unidades, con una moneda de cada tipo por lo menos;• Solucion: conjunto de monedas cuya suma es la cantidad a

pagar;• Completable: la suma de las monedas escogidas en un

momento dado no supera la cantidad a pagar;• Funcion de seleccion: la moneda de mayor valor en el

conjunto de candidatos aún no considerados;• Función objetivo: número de monedas utilizadas en la

solución

fuerza bruta - voraces

Documents