GRAFOS:

-Juego de Nim(Marieband game):

Misere: juego similar pero el que toma el último es el que pierde.

Juego con fósforos. Se quitan de 1 a n fósforos. El siguiente jugador puede quitar de 1 al doble de la cantidad que el otro quitó. Gana el que quita el último.

Se utiliza un grafo dirigido. En ajedrez se usa como reporte de movimiento, la acción de un jugador y la respuesta del otro. Medio movimiento: la jugada de sólo un jugador. 

Para el juego los nodos son pares (i,j) donde i es la cantidad de fósforos que quedan en la mesa, y j es los que se pueden tomar en el siguiente turno. 

El juego es simétrico porque cada jugador tiene las mismas reglas. Es determinístico porque el azar no es parte del juego.

Posiciones terminales: no ofrece posiciones legales, no tiene sucesores.

1. Etiquetar las posiciones terminales. Significa que perdió. 

2. Nodo posición ganador: el siguiente nodo es perdedor (al menos uno). 

3.Nodo posición perdedor: Todos los nodos sucesores son ganadores.

4. Nodo no terminal que lleva a empate. Uno de los sucesores da empate.  

-Atravesar árboles:

Preorden: nodo - hijo izq - hijo der
Enorden: hijo izq - nodo - hijo der
Postorden: Hijo izq - hijo der - nodo

Todos recorren en tiempo lineal. T(n).

-Preacondicionamiento:

invertir tiempo en calcular resultados auxiliares con antelación para acelerar el cálculo de la solución.

a: tiempo en encontrar solución sin precondicionamiento. n*a
b: tiempo con información auxiliar. p: tiempo que se tarda en encontrar esa info. p+n*b

Entonces nos beneficia usar pre cuando n > p/(a-b)

-Ancestralidad de nodos:

Se recorre el árbol en preorden y después en postorden. Prenum y postnum se asignan en cada caso respectivamente.
 

prenum(v) <= prenum(w) = v es ancestro de w, o v está a la izquierda de w.

postnum(v) >= postnum(w) = v es ancestro de w o v está a la derecha de w.

prenum(v) <= prenum(w) y además postnum(v) >= postnum(w) = v es ancestro de w

Búsqueda en profundidad para grafos no dirigidos:

Se elige cualquier nodo como inicial y se marca como visitado. Si hay un nodo adyacente a este, se elige como nuevo punto de inicio, entonces se llama recursivamente a este nodo.
Se llama recursivamente a todos los nodos adyacentes al inicial, y así sucesivamente. Se vuelve a llamar a la función si un nodo no se llega a recorrer. 

8(max(a,n))

Se pude hacer un MST, del recorrido, los nodos usados son los que hace el recorrido, los punteados son los que no se usaron.
Si el grafo no es conexo, se forma un bosque en lugar de un árbol.

Se puede colocar un número, que es el orden en que se recorrieron los nodos. 

Puntos de articulación: 

Los puntos de articulación, el subgrafo que queda cuando ese nodo se elimina ya no es conexo.
-Grafo es biconexo o inarticulado, si es conexo y no tiene puntos de articulación.
-Bicoherente o libre de istmo o conexo doble arco, si cada punto de articulación es unido por al menos dos arcos a cada componente del subgrafo resultante.

Algoritmo para encontrar puntos de articulación:

1. Hacer una búsqueda por profundidad desde cualquier nodo. El prenum es el numero asignado por esta búsqueda.
2. Atravesar el árbol de 1, en postorden, para cada nodo v calcular highest, como en mínimo entre:
      a) prenum de v
      b) prenum de w, cada nodo con arcos punteados.
      c) highest de x, para cada hijo x de v.
3. Determinar puntos de articulación:
      a) La raíz es punto articulación si y sólo si tiene más de un hijo.
      b) Cada otro nodo v es articulación si y sólo sí tiene un hijo tal que highest de hijo es >= que prenum de padre.

 

Búsqueda por profundidad para grafos dirigidos: 

Similar pero basándose en la dirección, pues se puede formar bosque si no es conexo. Igual se mantienen líneas para las conexiones de la búsqueda y punteadas las que no se usaron pero existían.
 

Grafos acíclicos: búsqueda topológica: 

Se puede usar para expresiones aritméticas con subexpresiones repetidas. Números divisores de otros. Y para el desarrollo de eventos, por etapas. 

Se puede usar  búsqueda por profundidad para saber si un grafo es acíclico, y para el ordenamiento topológico de los nodos de un grafo dirigido acíclico. 

 

Búsqueda por amplitud: 

Búsqueda por profundidad sería como una pila o stack LIFO. 
Búsqueda por amplitud sería colla FIFO.

Se siguen las reglas por amplitud y mismas reglas de líneas punteadas.
Grafos no conexos generan bosques.

8(max(a,n))

Está el problema de multiplicar por dos y dividir por 3 para un número. Se recorre en amplitud porque sino se podría nunca encontrar el resultado deseado. 

 

BACKTRACKING:

Grafo implícito:  se tiene información de sus nodos y arcos, así partes relevantes se pueden construir en el camino.

 

Backtracking usa búsqueda por profundidad en un grafo dirigido. Usualmente es un árbol o al menos no hay ciclos DAG (directed acyclic graph).

 

Se busca construir soluciones parciales mientras se procede, esas soluciones delimitan la zona donde puede estar la respuesta. Se comienza de cero y se va construyendo la solución hasta encontrarla, por lo que
podría detenerse al encontrar una o no si se necesitan mas que sólo una.

Y falla si la solución hasta el momento no puede ser completada. En ese momento se devuelve como la búsqueda por profundidad.

 

 

Branch and bound - ramificación y acotamiento: 

Usada para explorar grafos implícitos dirigidos. En cada nodo se calcula el acotamiento de los posibles valores de la solución que están mas lejos en el grafo.

Búsqueda por profundidad: explora los nodos en orden inverso a su creación.
Búsqueda por amplitud: explora los nodos en orden a su creación.

 

Usa computaciones auxiliares para decidir que nodos deben ser visitados después. 

 

 

El principio minimax: 

Se minimiza algo y se maximiza algo. 

Principio heurístico,