Algoritmos Voraces
Enviado por japonpop25 • 19 de Febrero de 2015 • 398 Palabras (2 Páginas) • 413 Visitas
Algoritmos voraces
Algoritmo, las 8 reinas
Colocar la reina N en la primera casilla valida de la fila N.
Si una reina no puede llegar a colocarse en ninguna casilla, se vuelve atrás y se cambia la posición de la reina N-1.
Intentar colocar las reinas restantes en las filas que quedan.
Problema de las n Reinas El problema de las ocho Reinas es generalizado por el problema de las n Reinas. El problema consiste en colocar n Reinas en un tablero de ajedrez de de tal manera que ninguna de las Reinas quede atacando a otra. El tamaño del tablero de ajedrez para este problema es de tamaño n*n. Existe un algoritmo que resuelve este problema generalizado usando la recursión.
Algoritmo, problema de la mochila
El conjunto de candidatos son los objetos, tomándose de ellos cierta fracción
Un conjunto de candidatos es completable si la suma de sus pesos no supera la capacidad de la mochila, y es una solución si iguala dicha capacidad.
La función objetivo a maximizar es∑_(1≤i≤n)▒〖b_i x_i 〗
La función de selección es la mas difícil de terminar
Si procedemos vorazmente, en cada paso debemos considerar un objeto y tomar cierta fracción suya.
La cuestión de que fracción se toma es mas fácil de resolver: si hemos elegido el mejor candidato, tomamos todo lo que podamos de el.
Cual es el mejor candidato:
Primera estrategia: elegir un objeto con el mayor beneficio total (el primero), sin embargo, la mochila se llena muy rápidamente con poco beneficio total.
Segunda estrategia: elegir el objeto que llene menos mochila, para acumular beneficios de un numero mayor de objetos, sin embargo, es posible que se elija un objeto con poco beneficio simplemente porque pesa poco.
La tercera estrategia: que es la optima, es tomar siempre el objeto que proporcione mayor beneficio por unidad de peso.
Algoritmo, problema del caballo
Para resolver este problema se puede utilizar la técnica de backtracking con un algoritmo recursivo relativamente simple: marcar la posición solicitada, hacer una lista de las siguientes posiciones vacías a las que se puede saltar desde la posición marcar, y tomar la primera de ellas, marcándola entonces en forma recursiva. Si en alguno de los pasos recursivos no se alcanza una solución, la casilla se desmarca y se pasa a la siguiente que estaba en la lista. Si se termina la lista y no se llega a una solución, entonces se devuelve a la casilla anterior desde la que se hizo el llamado.
...