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

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Obtener ruta más corta
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Obtener ruta más corta  (Leído 7,202 veces)
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Obtener ruta más corta
« en: 12 Junio 2013, 23:22 pm »

Me encuentro en un problema un poco elemental. A ver si alguien me puede dar alguna pista de como resolverlo.

Tenemos una cuadrícula tal que:



Ahí tenemos dos cuadrados pintados:



Partiendo del cuadrado rojo, tenemos que obtener una ruta para llegar al cuadrado azul (moviendose verticalmente/horizontalmente). Para complicar más la cosa ponemos algunos obstaculos aleatorios:



La ruta más corta sería:

(7,2)
(7,9)
(10,9)


¿Cómo podríamos implementar esto en C++?


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
aguml


Desconectado Desconectado

Mensajes: 378



Ver Perfil
Re: Obtener ruta más corta
« Respuesta #1 en: 13 Junio 2013, 00:03 am »

yo no te puedo ayudar en eso pero alguna vez he preguntado por algo parecido y me comentaron que buscara info sobre como se crean juegos y sobre los algoritmos de colisiones asi que supongo que es lo que necesitas.


En línea

xiruko


Desconectado Desconectado

Mensajes: 437


Ver Perfil
Re: Obtener ruta más corta
« Respuesta #2 en: 14 Junio 2013, 23:26 pm »

Citar
La ruta más corta sería:
(7,2)
(7,9)
(10,9)

De hecho hay varias que son las más cortas. La que indicas es de 14 cuadrados, igual que por ejemplo, (2, 7) - (9, 7) - (9, 10) o (8, 2) - (8, 3) - (9, 3) - (9, 10), donde el primer número sería la fila y el segundo la columna.

Como primera aproximación, podrías intentar que el cuadrado rojo vaya alternativamente hacia la coordenada x e y del cuadrado azul. Es decir, primero intente ir hasta la coordenada x, si llega a la fila o columna donde está el azul o choca con algo que entonces intente ir hasta la y, si vuelve a chocar que vaya a la x, etc. y así hasta que llegue. En el ejemplo que pones, este algoritmo daría alguna de las soluciones que te he comentado arriba.

Igualmente es demasiado simple así que no le pidas mucho... Si por ejemplo llegaras a chocar y el cuadrado rojo estuviera rodeado por obstáculos, ahí te quedarías... O si chocas con algo mientras estás en la fila o columna donde está el cuadrado azul, te quedarías ahí también...

Pero bueno, igual te da alguna idea para poder empezar.

Saludos!
En línea

ecfisa

Desconectado Desconectado

Mensajes: 114


Ver Perfil
Re: Obtener ruta más corta
« Respuesta #3 en: 15 Junio 2013, 00:54 am »

Hola amchacon.

Lo que buscas se resuelve mediante teoría de grafos, en este enlace tenes una explicación genérica: grafos.


Saludos.   :)
En línea

OmarHack


Desconectado Desconectado

Mensajes: 1.268


Ver Perfil
Re: Obtener ruta más corta
« Respuesta #4 en: 15 Junio 2013, 01:15 am »

Puedes trazar todas las rutas posibles, y seleccionar las más cortas para usar en el programa.
En línea

I like to test things.
lapras

Desconectado Desconectado

Mensajes: 140



Ver Perfil WWW
Re: Obtener ruta más corta
« Respuesta #5 en: 15 Junio 2013, 01:47 am »

El algoritmo de dijkstra te podria servir. O algo adaptado.
En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Obtener ruta más corta
« Respuesta #6 en: 15 Junio 2013, 12:16 pm »

De hecho hay varias que son las más cortas. La que indicas es de 14 cuadrados, igual que por ejemplo, (2, 7) - (9, 7) - (9, 10) o (8, 2) - (8, 3) - (9, 3) - (9, 10), donde el primer número sería la fila y el segundo la columna.

Como primera aproximación, podrías intentar que el cuadrado rojo vaya alternativamente hacia la coordenada x e y del cuadrado azul. Es decir, primero intente ir hasta la coordenada x, si llega a la fila o columna donde está el azul o choca con algo que entonces intente ir hasta la y, si vuelve a chocar que vaya a la x, etc. y así hasta que llegue. En el ejemplo que pones, este algoritmo daría alguna de las soluciones que te he comentado arriba.

Igualmente es demasiado simple así que no le pidas mucho... Si por ejemplo llegaras a chocar y el cuadrado rojo estuviera rodeado por obstáculos, ahí te quedarías... O si chocas con algo mientras estás en la fila o columna donde está el cuadrado azul, te quedarías ahí también...

Pero bueno, igual te da alguna idea para poder empezar.

Saludos!
No me sirve, los obstaculos pueden estar dispuestos de cualquier forma... Prefiero un método genérico  :silbar:

Hola amchacon.

Lo que buscas se resuelve mediante teoría de grafos, en este enlace tenes una explicación genérica: grafos.


Saludos.   :)

El algoritmo de busqueda en anchura es interesante   :)

El algoritmo de dijkstra te podria servir. O algo adaptado.
Pero aquí las distancias son iguales... No sé si vale la pena *_*
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
lapras

Desconectado Desconectado

Mensajes: 140



Ver Perfil WWW
Re: Obtener ruta más corta
« Respuesta #7 en: 15 Junio 2013, 17:27 pm »

Vale la pena por que el algoritmo de dijkstra es muy eficiente.
Te he hecho un programita en c++ que calcula el camino más corto entre dos celdas de un array.
Tienes obstaculos que se representan con un 1.

La función "getShortestPath" es la que lo hace todo y en el main lo que se hace es probar un ejemplo.

Código
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4.  
  5. using namespace std;
  6.  
  7. class Cell{
  8. int x;
  9. int y;
  10. public:
  11. int getx(){return x;}
  12. int gety(){return y;}
  13. void setx(int x){this->x=x;}
  14. void sety(int y){this->y=y;}
  15.  
  16. bool operator==(Cell o){return x==o.x && y==o.y;}
  17. Cell operator=(Cell o){x=o.x; y=o.y; return *this;}
  18.  
  19. Cell(int x,int y):x(x),y(y){}
  20. Cell():x(0),y(0){}
  21. };
  22. vector<Cell> getShortestPath(Cell ori, Cell dest, int array[], int width, int height);
  23.  
  24.  
  25.  
  26. int main(){
  27. int ejemplo[]={
  28. 0,1,0,1,0,0,0,0, //0: void
  29. 0,1,0,1,0,0,0,0, //1: obstacle
  30. 0,1,0,1,0,0,0,0,
  31. 0,1,0,1,0,0,0,0,
  32. 0,1,0,1,0,0,0,0,
  33. 0,1,0,1,0,0,0,0,
  34. 0,0,0,1,0,0,0,0,
  35. 0,0,0,0,0,0,0,0};
  36.  
  37. vector<Cell> camino= getShortestPath(Cell(0,0),Cell(7,0),ejemplo,8,8);
  38. for(int i=0;i<camino.size();i++){
  39. cout<<"("<<camino[i].getx()<<", "<<camino[i].gety()<<")"<<endl;
  40. }
  41.  
  42. }
  43.  
  44. vector<Cell> getShortestPath(Cell ori, Cell dest, int array[], int width, int height){
  45.  
  46. if(ori==dest) return vector<Cell>();
  47. unsigned int *sizes=new unsigned int[width*height];
  48. Cell *prev=new Cell[width*height];
  49. for(int i=0;i<width*height;i++){sizes[i]=-1; prev[i]=Cell(-1,-1);}
  50.  
  51. sizes[ori.getx()+ori.gety()*width]=0;
  52. prev[ori.getx()+ori.gety()*width]=ori;
  53.  
  54.  
  55. queue<Cell> porVisitar;
  56. porVisitar.push(ori);
  57.  
  58. while(!porVisitar.empty()){
  59. Cell cur=porVisitar.front();
  60. porVisitar.pop();
  61. cout<<porVisitar.size()<<endl;
  62. for(int i=-1;i<2;i++)
  63. for(int j=-1;j<2;j++)
  64. if( (cur.getx()+j)>=0 && (cur.getx()+j)<width && (cur.gety()+i)>=0 && (cur.gety()+i)<height && //is not out of bounds
  65. array[(cur.getx()+j)+(cur.gety()+i)*width]==0 && //is not an obstable
  66. sizes[cur.getx()+cur.gety()*width]+1 < sizes[(cur.getx()+j)+(cur.gety()+i)*width] //there is not a better path
  67. ){
  68. sizes[(cur.getx()+j)+(cur.gety()+i)*width]=sizes[cur.getx()+cur.gety()*width]+1;
  69. prev[(cur.getx()+j)+(cur.gety()+i)*width]=Cell(cur.getx(),cur.gety());
  70. porVisitar.push(Cell(cur.getx()+j,cur.gety()+i));
  71. }
  72.  
  73. }
  74.  
  75. if(prev[dest.getx()+dest.gety()*width]==Cell(-1,-1)) return vector<Cell>();
  76.  
  77. Cell pp=dest;
  78. vector<Cell> res(sizes[dest.getx()+dest.gety()*width]+1);
  79. for(int i=res.size()-1; !(pp==ori); i--){
  80. res[i]=pp;
  81. pp=prev[pp.getx()+pp.gety()*width];
  82. }
  83.  
  84. return res;
  85.  
  86. }
  87.  

Lo que se hace es considerar que:
1) Toda celda del array es un nodo.
2) Todas las celdas estan conectadas a sus vecinas.
3) Todas las aristas son bidireccionales.
4) Todas las aristas miden lo mismo: 1.

Y con esto lo que se hace es implementar dijkstra en un caso particular más sencillo.

Te pongo un pastebin para que puedas copiar y pegar:
http://pastebin.com/unRpQgK5
« Última modificación: 15 Junio 2013, 17:36 pm por lapras » En línea

amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: Obtener ruta más corta
« Respuesta #8 en: 15 Junio 2013, 21:07 pm »

Muyy interesante  :o

Es todo lo que necesitaba gracias  ;-)
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
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines