sábado, 10 de mayo de 2008

Algoritmos - Backtracking

Luego de mucho intentar entender este tipo de algoritmos, a dos semanas de mi examen logre entenderlos :D.


funcion buscar(parametros){

if(esFactible(..)){

if(no pase(..)){

pongo la ficha tentativamente
if(termine(..)){
exito
}else{
inicializo alternativas y busco entre las exitosas la mas útil
}
}//fin de "no pasé"

}//fin es factible

}

Hasta aquí parece sencillo, pero igual me llevo varios meses entenderlo :S. Por eso aquí les dejo el último ejercicio de examen que pude resolver.

Desarrolle una funcion que recibiendo un tablero de ajedres vacío,y una posicion inicial perteneciente al tablero imprima una secuencia de movimientos del caballo que no repite ninguna casilla y visita todas las casillas del tablero.




public class Camino {

public int[][] tablero;
public int nroPasos =0;
public int ocupadas = 0;

public boolean exito = false;

public Object clone(){
Camino camino = new Camino();
camino.tablero = new int[this.tablero.length][this.tablero[0].length];
camino.nroPasos = this.nroPasos;
camino.ocupadas = this.ocupadas;


for(int x=0;x < camino.tablero.length;x++){
for(int y=0;y < camino.tablero[x].length;y++){
camino.tablero[x][y] = this.tablero[x][y];
}
}


return camino;
}
}
package domain;

public class Tablero{

private int libre = 0;

private Camino mejorCamino = null;

private int[][] alternativas = {
{1,-2},
{2,-1},

{-1,2},
{-2,1},

{-1,-2},
{-2,-1},

{1,2},
{2,1}
};

private boolean exito = false;

private int[][] tablero;

private void inicializarTablero(int n){
this.tablero = new int[n][n];
for(int x=0;x < n;x++){
for(int y=0;y < n;y++){
this.tablero[x][y] =0;
}
}
}


private void buscarCamino(Camino camino, int xOrig,int yOrig){
camino.exito = false;
if(factible(camino.tablero,xOrig,yOrig)){
if(!pase(camino.tablero,xOrig,yOrig)){
//pongo tentativamente el paso en el tablero

camino.nroPasos++;
camino.ocupadas++;
camino.tablero[xOrig][yOrig] = camino.nroPasos;
if(termine(camino)){
camino.exito = true;
}else{

for(int i = 0;i < this.alternativas.length;i++){
Camino caminoAlt = (Camino)camino.clone();
this.buscarCamino(caminoAlt, xOrig+this.alternativas[i][0], yOrig+this.alternativas[i][1]);
//me quedo con las mejores opciones
if(this.mejorCamino == null){
if(caminoAlt.exito){
mejorCamino = caminoAlt;
}
}
}
}
}
}
}

private boolean termine(Camino camino) {

return camino.ocupadas == camino.tablero.length * camino.tablero[0].length;
}

/**
* decide si puede pasar
* @param laberinto
* @param x
* @param y
* @return boolean
*/
private boolean factible(int[][] tablero, int x, int y) {
return this.perteneceAlTablero(tablero, x, y);
}

private boolean pase(int[][] tablero, int x, int y) {
return tablero[x][y] !=this.libre;
}

private boolean perteneceAlTablero(int[][] tablero, int x, int y) {
if(x>=0 && y>=0){
return x < tablero.length && y < tablero[x].length;
}else{
return false;
}

}

/**
* imprime el laberinto
* @param laberinto
*/
public void imprimirCamino(Camino camino){
if(camino == null){
System.out.println("No se encontro un camino");
}else{
System.out.println("********** El caballo*********");
for(int x=0;x < camino.tablero.length;x++){
System.out.println("");
for(int y=0;y < camino.tablero[x].length;y++){
System.out.print(" " + camino.tablero[x][y] + " ");
}
}
System.out.println("");
System.out.println("*******************");
}

}

public Tablero(){
this.inicializarTablero(5);
Camino camino = new Camino();
camino.tablero = this.tablero;

this.buscarCamino(camino, 3,3);
this.imprimirCamino(mejorCamino);


}


}

Nota: perdon por la indentacion, pero me costo pila meter el codigo aca :(
si quieren el codigo bien hecho se los mando por mail

Diferentes tipos de interfaces

Desde:
http://www.ingeniuz.com/2008/04/08/sobre-el-diseno-de-interfaces/

domingo, 4 de mayo de 2008

IronMan - Cómo hacer una buena pelicula

No es un tutorial, es un halago para todo el equipo de IronMan.
Cero quejas sobre esta pelicula. Llevé a ver esta pelicula a mi novia ( quien aún no vió Matrix ni le gusta Spiderman) y le encantó.
Espero que salgan más peliculas como esta!
Después de haber visto esta película llegué a casa y retome mi incursion en el mundo de la robótica.

A NO PERDERSELA!

El Robot Economico

En Robotic lab podemos ver muchos tutoriales y noticias sobre robotica.

En mundobot podemos encontrar un tutorial que permite armar un robot con piezas de electrodomesticos que tenemos repartidos por toda la casa.

Yo de a poco voy a empezar a armar este pequeño robot, entreverando con el beetle robot, e iré poniendo el progreso aquí.

Más info:
http://members.tripod.com/robomaniac_2001/id46.htm

jueves, 1 de mayo de 2008

Imaginan el mundo sin Clark Kent?

Imaginan el mundo sin Clark Kent? aquí les dejo un trailer de el capitulo 150 de smallville dirigido por Tom Welling