Java Graph Package

This Java Class provide an interface to work with graphs (Direct an Undirect raphs). You can get output format to generate "bmp" graphs with Graphviz.

PROJECT HOME

JAVADOC

Step sample:


1. Import class


2. Code



3. Get results




4. Generate graph with output String Graphviz

Floyd algorithm

The problem: We have a Graph, no direct and valued, also, we have a vector with N stages. For example, one stage is between nodes 2 and 5, other stage is between nodes 5 and 1 , ect ...
We need the minimun path between first stage and last stage through the middle stages in order.

The solution: We use, Floyd algorithm.

The graph:


The stages :



The output:

Algorítmica en php - The Knight's Tour

El juego de The Knight's Tour

En un post anterior explicaba el algoritmo minimax (como introducción a la poda alfa-beta). Ahora veremos un poco de algorítmica, mas concretamente el backtracking. Podría decirse (a groso modo) que sería una busqueda minimax o poda alfa-beta pero sin heurística, además, el backtracking nos asegura que siempre encontrará la solución (si la hay) recorriendo así todos los estados posibles.

En wikipedia podemos obtener las reglas y una explicación de su complejidad, excelentes.

Pongo la implementación en PHP como una primera aproximación para la resolución del problema (La implementación la he realizado en php y orientada a objetos para que sea mas facil comprender el proceso de backtracking, evidentemente, no persigo eficiencia).


Backtraking




El software dispone de modo traza para ver los pasos de "vuelta atrás"



Algunos tiempos de ejecución en mi ordenador:

• Tablero 4x4 => 0.19897794723511 seg.
  

• Tablero 5x5 => 39.455229997635 seg.

• Tablero 6x6 => 364.00200605392 seg.

• Tablero 7x7 => 39521.259037971 segundos

• Tablero 8x8 => aún ejecutándose :)

Se observa (sin analizar matemáticamente la complejidad del algoritmo) su complejidad claramente exponencial.

Inteligencia Artificial - MINIMAX - Clisp

Descargar Codigo Fuente / Download Source Code

En el juego de restar cuadrados, dos jugadores juegan por turno restando cuadrados de números de una cantidad inicial, elegida al azar entre 10 y 1000. El siguiente turno partirá de la cantidad resultante de restar el cuadrado elegido a la cantidad, y así sucesivamente.

Por ejemplo, si la cantidad elegida es 17 y juega MAX, éste tendrá cuatro movimientos posibles: restar 4*4, quedando 1, restar 3*3, quedando 8, restar 2*2, quedando 13, o restar 1*1, quedando 16.

MAX y MIN juegan por turno y pierde el que no pueda realizar más movimientos, es decir, cuando la cantidad sea igual a 0.

Ejemplos de partida, partiendo de 13 y jugando MAX:

Partida 1:
MAX juega 2*2, quedan 9
MIN juega 3*3, MAX pierde

Partida 2:
MAX juega 1*1, quedan 12
MIN juega 3*3, quedan 3
MAX juega 1*1, quedan 2
MIN juega 1*1, queda 1
MAX juega 1*1, MIN pierde

--

Pilas y colas en PHP, estructuras de datos

Resolver problemas algoritmicos con pilas, colas, listas y arboles proporciona un metodo eficaz para ganar habilidad a la hora de resolver problemas recursivamente (o no). Tenemos una amplia gama de dificultades dentro de los problemas, aqui tengo algun ejemplo del tipico problema de invertir pila y cola, ademas de los TADs (Tipo Abstracto de Datos) para el manejo de estas estructuras.

Tad cola


Tad pila


Algunos ejemplos tipicos de trabajo con estas pilas :