Buenas, qué tal:
Estoy intentando realizar cierto problema utilizando backtracking, dicho problema es el siguiente:
En un tablero de ajedrez de tamaño n×n se coloca un rey en una casilla arbitraria (x0 , y0). Cada casilla (xi , yi) del tablero tiene asignado un peso p(xi , yi) , de tal forma que a cada recorrido R=((x0 , y0),...,(xk , yk)) se le puede asignar un valor que viene determinado por la siguiente expresión:
P(R) = (Sumatorio desde i=1 hasta k) i p(xi , yi)
El problema consiste en buscar el recorrido de peso mínimo que visite todas las casillas del tablero sin repetir ninguna.
El siguiente algoritmo especifica los movimientos válidos del rey:
Código:
void MovimientosRey(int movX[8], int movY[8]){
movX[1]=0; movY[1]=1;
movX[2]=-1; movY[2]=1;
movX[3]=-1; movY[3]=0;
movX[4]=-1; movY[4]=-1;
movX[5]=0; movY[5]=-1;
movX[6]=1; movY[6]=-1;
movX[7]=1; movY[7]=0;
movX[8]=1; movY[8]=1;
}
El siguiente algoritmo calcula el peso:
Código:
int Peso(int tam, int t[TAM][TAM]){
int i, j, p=0;
for(i=0;i<tam;i++){
for(j=0;j<tam;j++){
p = p+t[i][j]*i*j;
}
}
return p;
}
Y por último, el algoritmo backtracking:
Código:
int VueltaAtras(int movX[8], int movY[8], int tam, int t[TAM][TAM], int k, int x, int y){
int orden=1, coste, u, v;
int i, j;
while(orden!=9){
u = x+movX[orden];
v = y+movY[orden];
if((u>=1) && (u<=tam) && (v>=1) && (v<=tam) && (t[u][v]==0)){
t[u][v]=k;
if(k<tam*tam)
VueltaAtras(movX, movY, tam, t, k+1, u, v);
else{
coste = Peso(tam, t);
if(coste < minimo){
minimo = coste;
for(i=0;i<tam;i++){
for(j=0;j<tam;j++){
mejorSolucion[i][j] = t[i][j];
}
}
}
}
t[u][v]=0;
}
orden++;
}
return minimo;
}
Siendo el programa principal el siguiente:
Código:
int main(){
int movX[8], movY[8];
int tam;
minimo=1000000000;
MovimientosRey(movX, movY);
printf("Solicitando informacion del problema:\n");
printf("1.- Introduzca el tamano del tablero: ");
scanf("%d", &tam);
printf("\tGenerando tablero %dx%d.\n", tam, tam);
int t[tam][tam];
int i, j, x, y;
for(i=0;i<tam;i++){
for(j=0;j<tam;j++){
t[i][j]=0;
}
}
printf("3.- Posicion inicial del rey:\n");
printf("\ta.- Fila: ");
scanf("%d", &x);
printf("\tb.- Columna: ");
scanf("%d", &y);
printf("\tPosicion inicial del rey: (%d, %d).\n", x, y);
t[x][y]=1;
long int inicio, final;
float divisor=1000, ms;
int peso;
printf("\tIniciando busqueda del recorrido minimo...\n");
inicio = GetTickCount();
peso = VueltaAtras(movX, movY, tam, t, 2, x, y);
final = GetTickCount();
ms = (final-inicio)/divisor;
printf("\tBusqueda completada en t=%lf ms.\n", ms);
printf("\tEl peso del recorrido minimo es %d.", peso);
return 0;
}
Sin embargo, no funciona correctamente, por lo que si alguien tiene alguna idea sobre cómo funcionaría, que me lo comente si no es demasiada molestia.
Gracias de antemano.