Autor Tema: Camino más corto

0 Usuarios y 1 Visitante están viendo este tema.

17 Agosto, 2009, 08:15 pm
Leído 2584 veces

Mushotoku

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 39
  • Karma: +0/-0
  • Sexo: Masculino
Necesito calcular la longitud del camino mas corto desde la esquina superior izquierda hasta la esquina inferior derecha de un array bidimensional. Un movimiento permitido es moverse una casilla a la derecha o hacia abajo. La longitud de un camino está determinada por la suma de los números que se encuentran en las casillas por las que pasa.

Si por ejemplo el array es \( \begin{bmatrix}{13}&{8}&{9}&{12}&{4}\\{6}&{12}&{9}&{6}&{4}\\{4}&{11}&{9}&{13}&{15}\\{12}&{8}&{6}&{7}&{4}\end{bmatrix} \)

la longitud del camino mas corto es 

                                                 \( 13+6+4+11+8+6+7+4 = 59 \)

La verdad es que no tengo idea como empezar. He intentado varias cosas pero sin resultado. Estoy recién empezando a programar y me manejo con lo básico. ¿Alguna idea de cómo hacerlo?

Saludos.


mas más

17 Agosto, 2009, 09:52 pm
Respuesta #1

malpas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 17
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Si te fijas, creo que tú mismo te has dado la solución. Observa la suma que has escrito.

La solución pasa por, estando en una casilla, mires cuáles de las adayacentes permitidas tiene MENOR valor; eligiendo esa y repitiendo el proceso de nuevo.



17 Agosto, 2009, 11:08 pm
Respuesta #2

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.

Hola

Hola.

Si te fijas, creo que tú mismo te has dado la solución. Observa la suma que has escrito.

La solución pasa por, estando en una casilla, mires cuáles de las adayacentes permitidas tiene MENOR valor; eligiendo esa y repitiendo el proceso de nuevo.




Ese algoritmo puede fallar.
Fíjate el siguiente contraejemplo

\( \begin{bmatrix}
{13}&{100}&{100}&{100}&{100}\\
{6}&{12}&{9}&{\infty}&{100}\\
{4}&{11}&{9}&{\infty}&{100}\\
{12}&{8}&{6}&{\infty}&{100}
\end{bmatrix} \)

Me parece que aquí lo más apropiado es un algoritmo recursivo.
Pero si aún no has visto recursión , podemos pensar que un movimiento hacia abajo vale 1 y a la derecha vale 0.
En este caso, se tiene un camino por cada número de 7 bits.
Luego me fijo si puedo implementarlo.
Saludos.
Eram quod es, eris quod sum.

17 Agosto, 2009, 11:38 pm
Respuesta #3

malpas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 17
  • Karma: +0/-0
  • Sexo: Masculino

Hola

Hola.

Si te fijas, creo que tú mismo te has dado la solución. Observa la suma que has escrito.

La solución pasa por, estando en una casilla, mires cuáles de las adayacentes permitidas tiene MENOR valor; eligiendo esa y repitiendo el proceso de nuevo.




Ese algoritmo puede fallar.
Fíjate el siguiente contraejemplo

\( \begin{bmatrix}
{13}&{100}&{100}&{100}&{100}\\
{6}&{12}&{9}&{\infty}&{100}\\
{4}&{11}&{9}&{\infty}&{100}\\
{12}&{8}&{6}&{\infty}&{100}
\end{bmatrix} \)

Me parece que aquí lo más apropiado es un algoritmo recursivo.
Pero si aún no has visto recursión , podemos pensar que un movimiento hacia abajo vale 1 y a la derecha vale 0.
En este caso, se tiene un camino por cada número de 7 bits.
Luego me fijo si puedo implementarlo.
Saludos.

Tienes razón. Hay que tirar de backtracking.

17 Agosto, 2009, 11:40 pm
Respuesta #4

Teón

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,369
  • Karma: +0/-0
  • Sexo: Masculino
  • C:.J:.T:.
Hola.
Yo interpreto que los únicos movimientos válidos, son hacia abajo y hacia la derecha.
Refinando un poco las ideas, veo que donde puse "se tiene un camino por cada número de 7 bits."
debí poner "a lo sumo se tiene un camino por cada número de 6 bits."
Ya que el último paso, queda condicionado por el penúltimo.
Saludos.

Editado

Son todos los números de 7 bits, con 3 unos y 4 ceros
En nuestra notación, el camino indicado por Mushotoku, sería \( \mathcal{C}=1101000 \)
Saludos.
Eram quod es, eris quod sum.

18 Agosto, 2009, 01:35 am
Respuesta #5

Jabato

  • Visitante
Vamos a ver, si modificamos la matriz, tratando de implementar ceros en ella podemos simplificar nuestro problema hasta obtener un grado de dificultad tan simple que se vea a simple vista cual es la solución.

\( \begin{bmatrix}{13}&{8}&{9}&{12}&{4}\\{6}&{12}&{9}&{6}&{4}\\{4}&{11}&{9}&{13}&{15}\\{12}&{8}&{6}&{7}&{4}\end{bmatrix} \)

Si yo substituyo el 13 de la posición inicial por un 0 y sumo 13 a las dos posiciones adyacentes la longitud de cualquier camino que sigamos no habrá variado con lo que nuestro problema se convierte ahora en este otro:

\( \begin{bmatrix}{0}&{21}&{9}&{12}&{4}\\{19}&{12}&{9}&{6}&{4}\\{4}&{11}&{9}&{13}&{15}\\{12}&{8}&{6}&{7}&{4}\end{bmatrix} \)

Como puedo repetir el proceso tantas veces como desee, el problema se irá simplificando, por ejemplo repitamos la operación con el 21 que aparece ahora en la segunda posición de la matriz, obtenemos entonces:

\( \begin{bmatrix}{0}&{0}&{30}&{12}&{4}\\{19}&{33}&{9}&{6}&{4}\\{4}&{11}&{9}&{13}&{15}\\{12}&{8}&{6}&{7}&{4}\end{bmatrix} \)

y haciéndolo con el 19 que aparece ahora en la primera posición de la segunda fila obtenemos:

\( \begin{bmatrix}{0}&{0}&{30}&{12}&{4}\\{0}&{52}&{9}&{6}&{4}\\{23}&{11}&{9}&{13}&{15}\\{12}&{8}&{6}&{7}&{4}\end{bmatrix} \)

Vemos que nuestro problema se va simplificando pero la longitud de los caminos no ha variado, la de ningún camino ha variado.

No voy a terminar el proceso pero creo que la idea ha quedado clara, solo hay que completar los ceros hasta que sea imposible continuar y sabrás entonces cual es la longitud del camino más corto. 

En el caso de la última fila y columna no podrás sumar nada más que a una de las posiciones adyacentes pero como en ese caso el camino a seguir es obligado tampoco hay problema en eso.

Creo que de esta forma se obtiene la solución facilmente.

Saludos, Jabato. ;D

18 Agosto, 2009, 11:00 pm
Respuesta #6

Mushotoku

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 39
  • Karma: +0/-0
  • Sexo: Masculino
Gracias a todos por su aporte. Yo habia implementado un algoritmo con la misma esencia que el que pensó Jabato, pero en algun lugar fallaba. Voy a tratar de escribirlo de nuevo y veré si funciona.

Saludos.

18 Agosto, 2009, 11:06 pm
Respuesta #7

Jabato

  • Visitante
Es "Jabato" no "Jobato".

Gracias. Jabato.

18 Agosto, 2009, 11:10 pm
Respuesta #8

Mushotoku

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 39
  • Karma: +0/-0
  • Sexo: Masculino
 ;D ¡Perdón Jabato!

Saludos.

19 Agosto, 2009, 12:45 am
Respuesta #9

malpas

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 17
  • Karma: +0/-0
  • Sexo: Masculino

Sinceramente, no lo he entendido Jabato.