Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Backtracking

No description
by

stalin aguiar

on 23 October 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Backtracking

Vuelta atrás,
El término "backtrack"
Lehmer en la década de 1950.
La nanotecnología puede ser usada para crear dispositivos no detectables – micrófonos o cámaras de tamaño de una moléculas
Que significado tiene ...?
Udla
ESTRUCTURA DE DATOS

Stalin Aguiar
Andrés Baldeón
Alexis Benavides
Cynthia Duque
Diego Flores
Julio Tobar
Objetivo BUSCAR SOLUCIONES
Backtracking
Ventajas......
a) Si la solución es infinita, y si esta existe, no se encontrará nunca.
b) Consume mucha memoria para tener que almacenar los ciclos de búsqueda.

Desventajas
comúnmente utiliza la recursividad pero no siempre


a) Si existen una o las soluciones el backtracking las calcula.
b) Es relativamente sencillo de implementar en los problemas a resolver.
c) Se adapta a características en especifico de el problema.
Ejemplo resuelto de Backtracking recursivo. Agencia matrimonial.
Es de una agencia matrimonial quiere garantizar a sus clientes el mejor servicio y proporcionar garantías de poder encontrar una pareja estable. Para ello dispone de dos matrices de números naturales: H[1..n][1..N] y M[1..N][1..N] tales que H[i][j] indica la preferencia de un hombre i por una mujer j y M[i][j] la preferencia de una mujer i por un hombre j, para i y j entre 1 y N. Establecida una asignación de N parejas, si existe algún hombre y alguna mujer que, sin estar emparejados entre sí, se prefieren mutuamente a sus respectivas parejas, entonces la asignación es inestable; si no se da tal caso la asignación es estable. Desarrollar un algoritmo que encuentre los emparejamientos estables.
DE que se trata?
8 Reinas
Dada un tablero se plantea de la forma siguiente: dado un tablero de ajedrez(8*8 casillas), hay que situar ocho reinas de forma que ninguna de ellas pueda actuar("Comer") sobre ninguna de las otras.
El objetivo del problema es encontrar la fila en la que se sitúa la reina de la columna i, se define el array entero, reinas[], de tal forma que cada elemento contenga el índice de fila donde se sitúa la reina, o bien cero. el numero de reina, i, es a su vez el índice de columna dentro de la cual se puede colocar entre los ocho posibles valores de fila
final int N = 8;
final int n = (N+1);
int [] reinas = new int[n];
Código
Codificación del algoritmo de las 8 reinas:
En la clase OchoReinas se declaran como atributos los datos que se han establecido para representar el problema. el metodo solucionReina() es la interfaz de la clase para resolver el problema. Este llama a ponerReina() que realiza todo el trabajo de solución con llamadas recursivas.
package agencia;

public class matri {





private static void parejas_va(int[][] H, int[][] M, int[] sol, int k, boolean[] asignado)
{
for (int hombre = 1; hombre <= DefineConstants.N; hombre++)
{
if (!asignado[hombre])
{
sol[k] = hombre; // ensayo
asignado[hombre] = true; // marcado
if (estable(H, M, sol, k)) //condición de poda
{
if (k == DefineConstants.N) // comprobación de si es solución
{
imprimir(sol);
}
else // pasar al siguiente nivel
{
parejas_va(H, M, sol, k + 1, asignado);
}
}
asignado[hombre] = false; // desmarcado
}
}
}
private static boolean estable(int[][] H, int[][] M, int[] sol, int k)
{

boolean respuesta = true;
int i = 1;
while (i < k && respuesta)
{
respuesta = ((M[k][sol[i]] <= M[k][sol[k]] || H[sol[i]][k] <= H[sol[i]][i]) && (M[i][sol[k]] <= M[i][sol[i]] || H[sol[k]][i] <= H[sol[k]][k]));
i++;
}
return respuesta;
}
private static void imprimir(int[] sol)
{
for (int i = 1; i <= DefineConstants.N; i++)
{
System.out.print("Mujer ");
System.out.print(i);
System.out.print(" - Hombre ");
System.out.print(sol[i]);
System.out.print("\n");
}
System.out.print("\n");
}

private static int[][] H =
{
{0, 0, 0, 0},
{0, 4, 6, 4},
{0, 6, 4, 5},
{0, 4, 2, 8}
};

private static int[][] M =
{
{0, 0, 0, 0},
{0, 6, 4, 2},
{0, 7, 7, 9},
{0, 8, 4, 3}
};
private int[] sol = new int[DefineConstants.N + 1];

private boolean[] asignado = new boolean[DefineConstants.N + 1];

private int lo()
{
System.out.print("PAREJAS ESTABLES DE LA AGENCIA MATRIMONIAL\n\n");
System.out.print("\n");
parejas_va(H, M, sol, 1, asignado);
system("pause");
return 0;
}

private static void system(String string) {
// TODO Auto-generated method stub

}

final class DefineConstants
{
public static final int N = 3;
}




}

public boolean solucionReinas()
{
solucion = false;
ponerReina(1);
return solucion;
} private void ponerReina(int i)
{
int j;
j = 0; // inicializa posibles movimientos
do {
j++;
reinas[i] = j; // prueba a colocar reina i en fila j,
// a la vez queda anotado el movimiento
if (valido(i))
{
if (i < N) // no completado el problema
{
ponerReina(i+1);
// vuelta atrás
if (!solucion)
reinas[i] = 0;
}
else // todas las reinas colocadas
solucion = true;
}
} while(!solucion && (j < 8));
}
private boolean valido(int i)
{
/* Inspecciona si la reina de la columna i es atacada por
alguna reina colocada anteriormente */
int r;
boolean libre;
libre = true;
for (r = 1; r <= i-1; r++)
{
// no esté en la misma fila
libre = libre && (reinas[i] != reinas[r]);
// no esté en alguna de las dos diagonales
libre = libre && ((i + reinas[i]) != (r + reinas[r]));
libre = libre && ((i - reinas[i]) != (r - reinas[r]));
}
return libre;
}
Full transcript