ACOTACIÓN Y RAMIFICACION

El metodo de ramificar y acotar ayuda a resolver problemas complejos de programacion a traves de subprogramas, con la que se puede llegar a una solucion. Las "ramas" de este modelo iran "creciendo" o extendiendose dependiendo de las variables a resolver. Este metodo generalmente es utilizado en la resolucion de problemas de optimizacion, ya que resolver problemas NP-hard y obtener una solucion optima requiere de demasiado esfuerzo computacional, y esta herramienta ayuda a que el esfuerzo computacional no sea demasiado. Tambien se utiliza para los problemas de juegos.

El metodo genera nodos las cuales son soluciones de cada variable, que se sigue extendiendo, estas ramificaciones de las soluciones dadas por el metodo continuan creciendo siempre y cuando la siguiente solucion este dentro de lo optimo. El algoritmo busca el espacio de soluciones dadas por la mejor solucion.

El objetivo de este algoritmo sera encontrar el valor minimo de una funcion f(x) donde el rango de x esta determinado sobre un conjunto S de posibles soluciones. La iteracion tiene 3 componentes principales:

• seleccion de el nodo para procesos

• calcular los limites

• ramificar

Para cada nodo que se genera en la ramificacion tendremos:

• Cota superior del beneficio optimo que podemos alcanzar apartir del nodo i.

• Cota inferior del beneficio optimo que podemos alcanzar a partir del nodo i.

• Benificio estima optimo que se puede encontrar a partir del nodo i.

Las cotas deben ser fiables para poder determinar cuando se hace una acota y el beneficio estimado ayuda a decidir que parte del arbol evaaluar primero.

Estrategias para la ramificacion

Hacer un recrrido en un arbol de soluciones

Hacer distintos tipos de recorrido: en profundidad, en anchura, segun el beneficio estimado.

Para poder hacer los recorrido se utiliza una lista de nodos vivos. Estos nodos vivos son los que han sido generados pero que no han sido explorados todavia. son los nodos pendientes de tratar por el algoritmo.

en esta imagen los nodos de colores son los colores aun no explorados, o nodos vivos.

Aqui el pseudocodigo del algoritmo de ramificacion:

Funcion RyP {

P = Hijos(x,k)

mientras ( no vacio(P) )

x(k) = extraer(P)

si esFactible(x,k) y G(x,k) < optimo

si esSolucion(x)

Almacenar(x)

sino

RyP(x,k+1)

}

Algoritmo A*

Algoritmo A* o A estrella es un algoritmo pathfinding para encontrar el camino mas corto entre puntos A y B, generalmente utilizado en juegos ya que el primero en usarlo fue Pac-Man. Algunos algoritmos de busqueda pueden basarse unicamente en la heuristica de encontrar el camino mas corto, pero hay veces que se tiene que tomar en cuenta en tomar un camino largo para tener un mejor solucion, y un buen algoritmo de busqueda lo considera.

Este algoritmo evalua los nodos combinando g(n), el coste para alcanzar el nodo y h*(n), el coste estimado de ir al nodo objetivo que seria: f* (n) = g(n) + h* (n). La optimilidad de este algoritmo es sencillo de analizar si se usan busqueda-arboles.

La idea general de este algoritmo es:

• minimizar el coste estimado total de un camino en el arbol de busqueda

• Combinar:

-el coste para llegar al nodo n, y

-el coste aproximado para llegar a un nodo meta desde el nodo n

Muchos juegos de un solo jugador suelen utilizar algoritmos comunes de busqueda heuristica, aunque realemnte las soluciones a un juego de un jugador puede encontrarse en cualquier algoritmo de fuerza bruta sin heuristica alguna, siempre y cuando se disponga del tiempo y memoria necesarios. Aplicado este algoritmo a los juegos, este intentara de encontrar todos los movimientos ncesarios para llegar del estado inicial al estado final,

...