Puzzle 8 mi algoritmo sera eficiente? o no lo es?

[nolasco281]

Hola.

alquien comento aca este problema y me propuse a resolverlo

ahora bien mi pregunta es:

Mi algoritmo sera eficiente;
estos son los parametros que le mando a la funcion pero me resuelve el problema en 15  pasos,
ahora lo probe el mismo problema en una pagina de internet que resuelve este tipo de problemas y lo resuelve en 14 pasos asi que no se que pensar.

que no esta siendo eficiente del todo no?

Código (cpp) [Seleccionar] Expandir

int main(int argc, char** argv)
{
string inicio = "835416270";

printf ("Prueba n1\n");
string  meta = "123804765";
intel(meta, inicio);

printf("Ejemplo 2\n");
meta = "216408753";
intel(meta, inicio);
return 0;
}

aca el ejemplo



aca mi salida que indica que se realizo en 15 pasos.



una pregunta mas en que tengo que basarme para indicar si mi algoritmo es bueno, en el tiempo de ejecucion que llevo en resolver el problema, o en el algoritmo que estoy implementando?

saludos muchas gracias.

[El Benjo]

La eficiencia de un algoritmo se mide en dos áreas básicas: La velocidad de ejecución y el uso de memoria. Decir si un algoritmo es mejor que otro dependerá de tu objetivo o, mejor dicho, de tus recursos. Si dispones de un procesador muy rápido pero tienes poca memoria deberás optimizar el código para que ahorre memoria. Otra cosa, el código que dejas hace uso del algoritmo que usas pero en ningún momento dejas el código del algoritmo para analizar en qué puntos te podemos dar sugerencias. Tampoco explicas qué es lo que hace.

Si dejas más detalles te podremos decir cómo puede mejorar. Saludos.

[nolasco281]

Hola si tienes mucha razon lo que muestro de codigo no es nada para saber si mi algoritmo es eficiente no, el problema es que ya preguntaron aca por este ejercicio como una tarea y si subo el codigo le estare haciendo la tarea.

Pero entiendo bien lo que tratas de decir. en cuanto a que hace el programa es buscar la mejor solucion o la ruta mas corta para solucionar el problema, y en cuantos pasos se resuelve un juego Puzzle 8.

como puedes notar en esta parte de codigo le indico el problema desordenado que seria 835416270
y como lo quiero ordenado seria 123804765 para hacer esto lo realiza en 15 pasos.

tomando el 0 como espacio vacio y donde se van moviendo los demas numero para quedar ordenados.

Código (cpp) [Seleccionar] Expandir

string inicio = "835416270";
printf ("Prueba n1\n");
string  meta = "123804765";

muchas gracias por responder saludos : ).

[amchacon]

No aclaras que es lo que hace tu algoritmo

"Supongo" que hacer permutaciones para formar el cuadrado original... Eso lo puedes plantear así:

- Un for que vaya recorriendo todos los elementos de array desde 0 hasta size()-1.
- Para cada elemento hay otro for (desde i hasta size()). Lo que hace es comprobar si la pieza [j] es la que debería ir en la posición . Si es así lo intercambia.

Con 8 permutaciones ya tienes el cuadrado formado.

[NikNitro!]

Usas heurística o abres un árbol?

Salud

[ivancea96]

No aclaras que es lo que hace tu algoritmo

Con 8 permutaciones ya tienes el cuadrado formado.

Ese no es el objetivo del juego. El rompecabezas trata de ir deslizando pieza a pieza, teniendo un hueco vacío ('0').

[nolasco281]

El rompecabezas trata de ir deslizando pieza a pieza, teniendo un hueco vacío ('0').

Asi es como comenta ivancea96

Hola aca esta el codigo para que me aconsegen

saludos y gracias por responder

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <stdio.h>
#include <map>
#include <string>
#include<queue>
#include <cstdlib>

using namespace std;

class Nodo
{
public:
int profundidad, est;
string str;

Nodo (string str1, int profundidad1, int est1)
{
str = str1; //Estado
profundidad = profundidad1; //Profundidad
est = est1; // valor de evaluacion
}
};

class Profundidad
{
public:
int profundida, est;
string prev;

Profundidad(string prev1, int profundida1, int est1)
{
prev = prev1;  //Estado anterior
profundida = profundida1; //Profundidad
est = est1; //Valor de evaluacion
}
};

bool operator< (Nodo n1, Nodo n2)
{
bool sw = true;
if(n1.est == n2.est)
sw = (n1.str < n2.str) ? true:false;

else
sw = (n1.est > n2.est) ? true:false;

return sw;
}

//Evaluacion del nodo
//profundidad
//str: estada
//Meta: estado objetivo

int estimacion(int profundida, string str, string meta)
{
int i1, i2, i3, i4, k1, k2, pi = profundida, ws;
char cg[3][3], cn[3][3];

for (i1 =0; i1<9; i1++)
{
k1 = i1/3;
k2 = i1 - 3 * k1;
cg[k1][k2] = meta.at(i1) - '0';
}
for(i1 =0; i1 < 9; i1++)
{
k1 = i1 /3;
k2 = i1 -3 * k1;
cn[k1][k2] = str.at(i1) - '0';
}

for(i1 =0; i1 < 3; i1++)
{
for(i2 =0; i2 < 3; i2++)
{
ws = 1;
for(i3 =0; i3 < 3 && ws > 0; i3++)
{
for(i4 =0; i4 < 3 && ws >0; i4++)
{
if(cg[i3][i4] == cn[i1][i2])
{
ws = 0;
pi += (abs(i3-i1) + abs(i4-i2));
}
}
}
}
}

if (cn[1][1] != '0')
pi++;

if (cn[0][1] != (cn[0][0]+1)%9)
pi +=2;

if (cn[0][2] != (cn[0][1]+1)%9)
pi +=2;

if (cn[1][2] != (cn[0][2]+1)%9)
pi +=2;

if (cn[2][2] != (cn[1][2]+1)%9)
pi +=2;

if (cn[2][1] != (cn[2][2]+1)%9)
pi +=2;

if (cn[2][0] != (cn[2][1]+1)%9)
pi +=2;

if (cn[1][0] != (cn[2][0]+1)%9)
pi +=2;

if (cn[0][0] != (cn[1][0]+1)%9)
pi +=2;

return pi;
}

int mover (string str, string *res)
{
int k, n = 0;
string str1;

k = str.find("0");
switch(k)
{
case 0:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n]  = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;

case 1:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n]  = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;

case 2:
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;

case 3:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;

case 4:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;

case 5:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+3, 1);
str1 = str1.replace(k+3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;

case 6:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;

case 7:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k+1, 1);
str1 = str1.replace(k+1, 1, 1, '0');
res[n] = str1;
n++;
break;

case 8:
str1 = str.replace(k, 1, str, k-3, 1);
str1 = str1.replace(k-3, 1, 1, '0');
res[n] = str1;
n++;
str1 = str.replace(k, 1, str, k-1, 1);
str1 = str1.replace(k-1, 1, 1, '0');
res[n] = str1;
n++;
break;
}

return n;
}

//Inicial
// Meta

void intel(string inicio, string meta)
{
int i1, n, nodo1 = 1, nodo2 =0, profundida =1, ct =1, est;
string str, res[4];
priority_queue<Nodo> p;
map<string, Profundidad> m;
map<string, Profundidad>::iterator it;
bool sw;

est = estimacion(profundida, inicio, meta);
m.insert(pair<string, Profundidad>(inicio, Profundidad("", profundida, est)));
p.push(Nodo(inicio, profundida, est));
while (!p.empty())
{
str = p.top().str;
profundida = p.top().profundidad;
nodo2++;

//Objetivos
if(str == meta)
{
ct = profundida;
break;
}
//Si no hay una meta
//A~nadidi a la cola, tienen el mismo status y mover el marco
else
{
p.pop();
n = mover(str, res);

for (i1 =0; i1 < n; i1++)
{
sw = true;
est = estimacion(profundida+1, res[i1], meta);
it = m.find(res[i1]);

if(it != m.end())
{
if(est < ((*it).second).est)
m.erase(it);

else
sw = false;
}

if (sw)
{
m.insert(pair<string, Profundidad>(res[i1], Profundidad(str, profundida+1, est)));
p.push(Nodo(res[i1], profundida+1, est));
nodo1++;
}
}
}
}

//Salida
printf("Implementacion %d %d, Distancia minima %d\n", nodo1, nodo2, ct);

while(str.length()>0)
{
printf("\n      %c %c %c\n", str.at(0), str.at(1), str.at(2));
printf("      %c %c %c\n", str.at(3), str.at(4), str.at(5));
printf("      %c %c %c\n", str.at(6), str.at(7), str.at(8));
it = m.find(str);
str = ((*it).second).prev;
}
}

int main(int argc, char** argv)
{
string inicio = "835416270";

printf ("Prueba n1\n");
string  meta = "123804765";
intel(meta, inicio);

printf("Ejemplo 2\n");
meta = "216408753";
intel(inicio, meta);
return 0;
}

[NikNitro!]

Busca como hacerlo con AIMA. Es mucho más cómodo.
http://aima.cs.berkeley.edu/code.html

Saludos