Autor Tema: Camino más corto

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

19 Agosto, 2009, 12:50 am
Respuesta #10

Jabato

  • Visitante
¿Que es lo que no entiendes?

19 Agosto, 2009, 01:03 am
Respuesta #11

malpas

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

¿Que es lo que no entiendes?

Hola Jabato.

Supongo que ese proceso que dices lo repites tantas veces hasta haber agotado todas las posibilidas y por cada camino seguido vas viendo la suma y eligiendo la menor ¿no?

Esto lo digo porque en la explicación dices que se hace un 0 en el elemento elegido y ese elemento es sumado a los dos adyacentes. Pero no consigo ver cómo se llega así a la solución. Finalmente obtendrás una suma en el elemento final pero eso no implica que sea la menor. Me lío. ¿Por qué sumar el elemento a los dos adyacentes?

Otra cosa que me ha liado es en la cuarta matriz que has escrito. No sé de dónde sale el 5 en el elemento de la segunda fila y segunda columna.



19 Agosto, 2009, 01:39 am
Respuesta #12

Jabato

  • Visitante
No, hasta agotar todas las posibilidades no, hasta conseguir una simplicidad tal que a simple vista se vea la solución. Y además creo que deben cancelarse las psiciones de la primera fila y columna antes que las demás, es decir barriendo de izquierda a derecha y de arriba abajo.

El 5 ese era un error que ya corregí.

Piensa que esas transformaciones dejan invariante las longitud de todos los caminos. No estoy seguro de como debe finalizarse el proceso, no lo he analizado en profundidad, pero con un ejemplo más sencillo se podrá aclarar, imagino.

Saludos, Jabato. ;D

19 Agosto, 2009, 02:53 am
Respuesta #13

topo23

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 937
  • Karma: +0/-0
Si los unicos movimientos permitidos son ir a la celda de abajo o a la celda de la derecha, entonces la solucion de Jabato es correcta, solo hay que sumar a cada celda el menor de los valores de la izquierda o arriba, e ir recorriendo la matriz en diagonal invertida.

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

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

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

Spoiler
\( \begin{bmatrix}
{0}&{0}&{0}&{42}&{4}\\
{0}&{0}&{39}&{6}&{4}\\
{0}&{34}&{9}&{13}&{15}\\
{35}&{8}&{6}&{7}&{4}
\end{bmatrix} \)


\( \begin{bmatrix}
{0}&{0}&{0}&{0}&{46}\\
{0}&{0}&{0}&{45}&{4}\\
{0}&{0}&{43}&{13}&{15}\\
{0}&{42}&{6}&{7}&{4}
\end{bmatrix} \)


\( \begin{bmatrix}
{0}&{0}&{0}&{0}&{0}\\
{0}&{0}&{0}&{0}&{49}\\
{0}&{0}&{0}&{56}&{15}\\
{0}&{0}&{48}&{7}&{4}
\end{bmatrix} \)


\( \begin{bmatrix}
{0}&{0}&{0}&{0}&{0}\\
{0}&{0}&{0}&{0}&{0}\\
{0}&{0}&{0}&{0}&{64}\\
{0}&{0}&{0}&{55}&{4}
\end{bmatrix} \)


\( \begin{bmatrix}
{0}&{0}&{0}&{0}&{0}\\
{0}&{0}&{0}&{0}&{0}\\
{0}&{0}&{0}&{0}&{0}\\
{0}&{0}&{0}&{0}&{59}
\end{bmatrix} \)


[cerrar]
.