elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Puzzle 8 mi algoritmo sera eficiente? o no lo es?
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Puzzle 8 mi algoritmo sera eficiente? o no lo es?  (Leído 4,146 veces)
nolasco281


Desconectado Desconectado

Mensajes: 319


Ver Perfil
Puzzle 8 mi algoritmo sera eficiente? o no lo es?
« en: 16 Abril 2014, 04:14 am »

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
  1. int main(int argc, char** argv)
  2. {
  3. string inicio = "835416270";
  4.  
  5. printf ("Prueba n1\n");
  6. string  meta = "123804765";
  7. intel(meta, inicio);
  8.  
  9. printf("Ejemplo 2\n");
  10. meta = "216408753";
  11. intel(meta, inicio);
  12. return 0;
  13. }

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.


En línea

Lo que se puede imaginar... se puede programar.
El Benjo


Desconectado Desconectado

Mensajes: 392



Ver Perfil WWW
Re: Puzzle 8 mi algoritmo sera eficiente? o no lo es?
« Respuesta #1 en: 16 Abril 2014, 06:00 am »

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.


En línea

www.es.neftis-ai.com

Sí hay un mejor lenguaje de programación y es ese con el que puedes desarrollar tus objetivos.
nolasco281


Desconectado Desconectado

Mensajes: 319


Ver Perfil
Re: Puzzle 8 mi algoritmo sera eficiente? o no lo es?
« Respuesta #2 en: 16 Abril 2014, 06:15 am »

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
  1. string inicio = "835416270";
  2. printf ("Prueba n1\n");
  3. string  meta = "123804765";

muchas gracias por responder saludos : ).
En línea

Lo que se puede imaginar... se puede programar.
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Puzzle 8 mi algoritmo sera eficiente? o no lo es?
« Respuesta #3 en: 16 Abril 2014, 12:18 pm »

No aclaras que es lo que hace tu algoritmo :huh:

"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.
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
NikNitro!


Desconectado Desconectado

Mensajes: 1.309


Galletaaa!!!


Ver Perfil WWW
Re: Puzzle 8 mi algoritmo sera eficiente? o no lo es?
« Respuesta #4 en: 16 Abril 2014, 12:49 pm »

Usas heurística o abres un árbol?

Salud
En línea

ivancea96


Desconectado Desconectado

Mensajes: 3.414


ASMático


Ver Perfil WWW
Re: Puzzle 8 mi algoritmo sera eficiente? o no lo es?
« Respuesta #5 en: 16 Abril 2014, 14:07 pm »

No aclaras que es lo que hace tu algoritmo :huh:

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').
En línea

nolasco281


Desconectado Desconectado

Mensajes: 319


Ver Perfil
Re: Puzzle 8 mi algoritmo sera eficiente? o no lo es?
« Respuesta #6 en: 16 Abril 2014, 18:02 pm »

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
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <map>
  4. #include <string>
  5. #include<queue>
  6. #include <cstdlib>
  7.  
  8. using namespace std;
  9.  
  10. class Nodo
  11. {
  12. public:
  13. int profundidad, est;
  14. string str;
  15.  
  16. Nodo (string str1, int profundidad1, int est1)
  17. {
  18. str = str1; //Estado
  19. profundidad = profundidad1; //Profundidad
  20. est = est1; // valor de evaluacion
  21. }
  22. };
  23.  
  24. class Profundidad
  25. {
  26. public:
  27. int profundida, est;
  28. string prev;
  29.  
  30. Profundidad(string prev1, int profundida1, int est1)
  31. {
  32. prev = prev1;  //Estado anterior
  33. profundida = profundida1; //Profundidad
  34. est = est1; //Valor de evaluacion
  35. }
  36. };
  37.  
  38. bool operator< (Nodo n1, Nodo n2)
  39. {
  40. bool sw = true;
  41. if(n1.est == n2.est)
  42. sw = (n1.str < n2.str) ? true:false;
  43.  
  44. else
  45. sw = (n1.est > n2.est) ? true:false;
  46.  
  47. return sw;
  48. }
  49.  
  50. //Evaluacion del nodo
  51. //profundidad
  52. //str: estada
  53. //Meta: estado objetivo
  54.  
  55. int estimacion(int profundida, string str, string meta)
  56. {
  57. int i1, i2, i3, i4, k1, k2, pi = profundida, ws;
  58. char cg[3][3], cn[3][3];
  59.  
  60. for (i1 =0; i1<9; i1++)
  61. {
  62. k1 = i1/3;
  63. k2 = i1 - 3 * k1;
  64. cg[k1][k2] = meta.at(i1) - '0';
  65. }
  66. for(i1 =0; i1 < 9; i1++)
  67. {
  68. k1 = i1 /3;
  69. k2 = i1 -3 * k1;
  70. cn[k1][k2] = str.at(i1) - '0';
  71. }
  72.  
  73. for(i1 =0; i1 < 3; i1++)
  74. {
  75. for(i2 =0; i2 < 3; i2++)
  76. {
  77. ws = 1;
  78. for(i3 =0; i3 < 3 && ws > 0; i3++)
  79. {
  80. for(i4 =0; i4 < 3 && ws >0; i4++)
  81. {
  82. if(cg[i3][i4] == cn[i1][i2])
  83. {
  84. ws = 0;
  85. pi += (abs(i3-i1) + abs(i4-i2));
  86. }
  87. }
  88. }
  89. }
  90. }
  91.  
  92. if (cn[1][1] != '0')
  93. pi++;
  94.  
  95. if (cn[0][1] != (cn[0][0]+1)%9)
  96. pi +=2;
  97.  
  98. if (cn[0][2] != (cn[0][1]+1)%9)
  99. pi +=2;
  100.  
  101. if (cn[1][2] != (cn[0][2]+1)%9)
  102. pi +=2;
  103.  
  104. if (cn[2][2] != (cn[1][2]+1)%9)
  105. pi +=2;
  106.  
  107. if (cn[2][1] != (cn[2][2]+1)%9)
  108. pi +=2;
  109.  
  110. if (cn[2][0] != (cn[2][1]+1)%9)
  111. pi +=2;
  112.  
  113. if (cn[1][0] != (cn[2][0]+1)%9)
  114. pi +=2;
  115.  
  116. if (cn[0][0] != (cn[1][0]+1)%9)
  117. pi +=2;
  118.  
  119. return pi;
  120. }
  121.  
  122. int mover (string str, string *res)
  123. {
  124. int k, n = 0;
  125. string str1;
  126.  
  127. k = str.find("0");
  128. switch(k)
  129. {
  130. case 0:
  131. str1 = str.replace(k, 1, str, k+3, 1);
  132. str1 = str1.replace(k+3, 1, 1, '0');
  133. res[n]  = str1;
  134. n++;
  135. str1 = str.replace(k, 1, str, k+1, 1);
  136. str1 = str1.replace(k+1, 1, 1, '0');
  137. res[n] = str1;
  138. n++;
  139. break;
  140.  
  141. case 1:
  142. str1 = str.replace(k, 1, str, k+3, 1);
  143. str1 = str1.replace(k+3, 1, 1, '0');
  144. res[n]  = str1;
  145. n++;
  146. str1 = str.replace(k, 1, str, k-1, 1);
  147. str1 = str1.replace(k-1, 1, 1, '0');
  148. res[n] = str1;
  149. n++;
  150. str1 = str.replace(k, 1, str, k+1, 1);
  151. str1 = str1.replace(k+1, 1, 1, '0');
  152. res[n] = str1;
  153. n++;
  154. break;
  155.  
  156. case 2:
  157. str1 = str.replace(k, 1, str, k+3, 1);
  158. str1 = str1.replace(k+3, 1, 1, '0');
  159. res[n] = str1;
  160. n++;
  161. str1 = str.replace(k, 1, str, k-1, 1);
  162. str1 = str1.replace(k-1, 1, 1, '0');
  163. res[n] = str1;
  164. n++;
  165. break;
  166.  
  167. case 3:
  168. str1 = str.replace(k, 1, str, k-3, 1);
  169. str1 = str1.replace(k-3, 1, 1, '0');
  170. res[n] = str1;
  171. n++;
  172. str1 = str.replace(k, 1, str, k+3, 1);
  173. str1 = str1.replace(k+3, 1, 1, '0');
  174. res[n] = str1;
  175. n++;
  176. str1 = str.replace(k, 1, str, k+1, 1);
  177. str1 = str1.replace(k+1, 1, 1, '0');
  178. res[n] = str1;
  179. n++;
  180. break;
  181.  
  182. case 4:
  183. str1 = str.replace(k, 1, str, k-3, 1);
  184. str1 = str1.replace(k-3, 1, 1, '0');
  185. res[n] = str1;
  186. n++;
  187. str1 = str.replace(k, 1, str, k+3, 1);
  188. str1 = str1.replace(k+3, 1, 1, '0');
  189. res[n] = str1;
  190. n++;
  191. str1 = str.replace(k, 1, str, k-1, 1);
  192. str1 = str1.replace(k-1, 1, 1, '0');
  193. res[n] = str1;
  194. n++;
  195. str1 = str.replace(k, 1, str, k+1, 1);
  196. str1 = str1.replace(k+1, 1, 1, '0');
  197. res[n] = str1;
  198. n++;
  199. break;
  200.  
  201. case 5:
  202. str1 = str.replace(k, 1, str, k-3, 1);
  203. str1 = str1.replace(k-3, 1, 1, '0');
  204. res[n] = str1;
  205. n++;
  206. str1 = str.replace(k, 1, str, k+3, 1);
  207. str1 = str1.replace(k+3, 1, 1, '0');
  208. res[n] = str1;
  209. n++;
  210. str1 = str.replace(k, 1, str, k-1, 1);
  211. str1 = str1.replace(k-1, 1, 1, '0');
  212. res[n] = str1;
  213. n++;
  214. break;
  215.  
  216. case 6:
  217. str1 = str.replace(k, 1, str, k-3, 1);
  218. str1 = str1.replace(k-3, 1, 1, '0');
  219. res[n] = str1;
  220. n++;
  221. str1 = str.replace(k, 1, str, k+1, 1);
  222. str1 = str1.replace(k+1, 1, 1, '0');
  223. res[n] = str1;
  224. n++;
  225. break;
  226.  
  227. case 7:
  228. str1 = str.replace(k, 1, str, k-3, 1);
  229. str1 = str1.replace(k-3, 1, 1, '0');
  230. res[n] = str1;
  231. n++;
  232. str1 = str.replace(k, 1, str, k-1, 1);
  233. str1 = str1.replace(k-1, 1, 1, '0');
  234. res[n] = str1;
  235. n++;
  236. str1 = str.replace(k, 1, str, k+1, 1);
  237. str1 = str1.replace(k+1, 1, 1, '0');
  238. res[n] = str1;
  239. n++;
  240. break;
  241.  
  242. case 8:
  243. str1 = str.replace(k, 1, str, k-3, 1);
  244. str1 = str1.replace(k-3, 1, 1, '0');
  245. res[n] = str1;
  246. n++;
  247. str1 = str.replace(k, 1, str, k-1, 1);
  248. str1 = str1.replace(k-1, 1, 1, '0');
  249. res[n] = str1;
  250. n++;
  251. break;
  252. }
  253.  
  254. return n;
  255. }
  256.  
  257. //Inicial
  258. // Meta
  259.  
  260. void intel(string inicio, string meta)
  261. {
  262. int i1, n, nodo1 = 1, nodo2 =0, profundida =1, ct =1, est;
  263. string str, res[4];
  264. priority_queue<Nodo> p;
  265. map<string, Profundidad> m;
  266. map<string, Profundidad>::iterator it;
  267. bool sw;
  268.  
  269. est = estimacion(profundida, inicio, meta);
  270. m.insert(pair<string, Profundidad>(inicio, Profundidad("", profundida, est)));
  271. p.push(Nodo(inicio, profundida, est));
  272. while (!p.empty())
  273. {
  274. str = p.top().str;
  275. profundida = p.top().profundidad;
  276. nodo2++;
  277.  
  278. //Objetivos
  279. if(str == meta)
  280. {
  281. ct = profundida;
  282. break;
  283. }
  284. //Si no hay una meta
  285. //A~nadidi a la cola, tienen el mismo status y mover el marco
  286. else
  287. {
  288. p.pop();
  289. n = mover(str, res);
  290.  
  291. for (i1 =0; i1 < n; i1++)
  292. {
  293. sw = true;
  294. est = estimacion(profundida+1, res[i1], meta);
  295. it = m.find(res[i1]);
  296.  
  297. if(it != m.end())
  298. {
  299. if(est < ((*it).second).est)
  300. m.erase(it);
  301.  
  302. else
  303. sw = false;
  304. }
  305.  
  306. if (sw)
  307. {
  308. m.insert(pair<string, Profundidad>(res[i1], Profundidad(str, profundida+1, est)));
  309. p.push(Nodo(res[i1], profundida+1, est));
  310. nodo1++;
  311. }
  312. }
  313. }
  314. }
  315.  
  316. //Salida
  317. printf("Implementacion %d %d, Distancia minima %d\n", nodo1, nodo2, ct);
  318.  
  319. while(str.length()>0)
  320. {
  321. printf("\n      %c %c %c\n", str.at(0), str.at(1), str.at(2));
  322. printf("      %c %c %c\n", str.at(3), str.at(4), str.at(5));
  323. printf("      %c %c %c\n", str.at(6), str.at(7), str.at(8));
  324. it = m.find(str);
  325. str = ((*it).second).prev;
  326. }
  327. }
  328.  
  329. int main(int argc, char** argv)
  330. {
  331. string inicio = "835416270";
  332.  
  333. printf ("Prueba n1\n");
  334. string  meta = "123804765";
  335. intel(meta, inicio);
  336.  
  337. printf("Ejemplo 2\n");
  338. meta = "216408753";
  339. intel(inicio, meta);
  340. return 0;
  341. }
« Última modificación: 16 Abril 2014, 18:08 pm por nolasco281 » En línea

Lo que se puede imaginar... se puede programar.
NikNitro!


Desconectado Desconectado

Mensajes: 1.309


Galletaaa!!!


Ver Perfil WWW
Re: Puzzle 8 mi algoritmo sera eficiente? o no lo es?
« Respuesta #7 en: 16 Abril 2014, 22:28 pm »

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

Saludos
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Puzzle 8 en c
Programación C/C++
twins 0 2,124 Último mensaje 21 Junio 2012, 23:27 pm
por twins
Problemas al intentar hacer mas eficiente un algoritmo de ordenacion « 1 2 »
Programación C/C++
Dark00 10 3,229 Último mensaje 14 Noviembre 2012, 23:24 pm
por Dark00
Puzzle 8
Programación C/C++
Luis100710 2 1,537 Último mensaje 16 Abril 2014, 00:29 am
por erickgracia
La red anónima Tor será aún más segura con este nuevo algoritmo
Noticias
wolfbcn 0 1,105 Último mensaje 25 Mayo 2016, 18:43 pm
por wolfbcn
¿Cual es el algoritmo más eficiente para sacar la subcadena común mayor?
Programación General
pran_krr 1 821 Último mensaje 27 Noviembre 2019, 16:45 pm
por Serapis
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines