Camino mas corto entre dos puntos de una matriz [algoritmo]

Buen día.

El día de hoy plantearemos un ejercicio o reto de programación  el cual constara de su  respectiva descripción y que si gustan después de la misma, pueden realizarlo y mandar su solución la cual sera publicada; El objetivo de hacer este post, surge de la necesidad de platear ciertos criterios a la hora de afrontar retos de programación  dado que en muchas partes (universidades, comunidades, team's, etc..) las personas suelen subestimar el poder de la programación  a un a sabiendas de que es esta, la que hace mover todo internet, desde el punto de vista tanto de informática (general) como de seguridad informática y/o hacking.

Ejercicio "Camino más corto entre dos puntos de una matriz":

Tenemos una matriz de MxN, y deseamos hallar el camino más corto entre el punto de origen O(1,1) y un punto P(x,y) dado de forma aleatoria o no secuencial. 

Datos de entrada: Para los datos de entrada, pediremos las coordenadas del punto final (x,y) dado que las coordenadas del punto de origen serán por defecto (1,1), también se pedirá que ingrese el tamaño de la matriz o espacio a utilizar, en este caso se pedirá de la forma MxN. 

Datos de salida: La matriz de MxN puede contener cualquier tipo de caracteres, pero el camino o ruta demarcado por el programa debe ser señalado por el carácter "+". 

Ejemplo: Dada una matriz de 4x5, vamos a hallar la ruta más corta entre el punto origen (1,1) y el punto (4,3) : 

La salida de este programa es : 

Ahora como se puede observar, los caracteres "+" representan la ruta más corta desde el punto origen O(1,1) hasta el punto P(4,3)

Si así gustan, puede detenerse aquí e intentar plantear su propia solución al problema, dado que la solución que expondremos, simplemente es una de las tantas soluciones posibles; Esperamos su solución..

Para poder entender mejor la explicación, es recomendable tener conocimientos básicos sobre lo que es una matriz. Saber que un punto o coordenada se expresa mediante sus subindices (M,N) donde M representa la fila y N representa la columna donde se encuentra dicho punto.

La manera correcta y el punto clave de esté ejercicio en particular, yace en que se parte de un punto que siempre va a ser fijo, en este caso el punto O(1,1) osea que partimos desde la esquina superior izquierda hacia cualquier otro punto de la matriz. Teniendo en cuenta esté primer hecho, ahora tenemos que ver como podemos llegar hasta cualquier otro punto de la matriz, así qué cavilando y cavilando (Dijo el viejo Grinch), notamos que podemos llegar a cualquier punto de la matriz, si aumentamos el numero de filas del punto inicial hasta que sea igual al numero de filas del punto final, y esto también lo hacemos con las columnas, si aumentamos el numero de columnas del punto inicial hasta que sea igual al numero de columnas del punto final.  Una vez culminado este proceso,  habremos llegado desde el punto inicial hasta el punto final.

Dicho de otra manera tenemos que nuestro punto inicial es O(1f,1c) y nuestro punto final es P(4f,3c) (en las coordenadas incluí la f y la c, para especificar fila y columna respectivamente), así que para que 1f sea igual a 4f, tendremos que ir sumando de a uno en uno hasta que 1f se convierta en 4f, y unas vez logrado esto, ahora repetimos el mismo procedimiento con 1c y 3c, en este caso tendremos que ir sumando de a uno en uno, hasta que 1c se convierta en 3c. Representando cada nueva posición con un carácter "+", gráficamente esto quedaría así:

Como podemos observar, ya hemos logrado hallar una ruta desde el punto de Origen O(1,1) hasta el punto P(4,3), pero si lo pensamos bien, este método no solo sirve para estos puntos dados, sino que si lo probamos con otros puntos de otra matriz, también podremos hallar una ruta desde un punto hasta el otro. Para este ejemplo vamos a utilizar una Matriz de 4x8, y vamos a hallar la ruta desde el punto de origen O(1,1) hasta el punto final P(3,7), si intentamos igualar filas con filas y columnas con columnas, aumentadolos de a uno en uno, obtendremos la siguiente ruta:

Con esto podemos estar seguros de que existe una manera de hallar una ruta desde un punto origen hasta cualquier punto dado. Vale aclarar que es evidente que este método no nos da la ruta más corta entre dos puntos, pero sí nos da una ruta o camino, así que vamos a hacer un código de prueba,  intentado simular todo este procedimiento, así se nos hará más fácil entender el código final.

Ver Codigo en Pastebin[1]

La realidad es que si explico todo el código, este post se puede tornar más largo y repetitivo de lo normal, así que trataré de explicar las funciones más importantes y espero que mirando el código ustedes lo puedan entender a la perfección (igualmente cualquier duda la pueden comentar).El código consta de dos parte importantes en este caso de dos funciones llamadas camino_corto() y matriz(), las cuales respectivamente se encargan de buscar el camino o ruta entre los dos puntos de la matriz y de generar la matriz de tamaño MxN según lo que el usuario desee.

Matriz(M,N): Está función es la encargada de generar la matriz en la cual vamos a trabajar, y es por esto, que hemos utilizado las variables de tipo LISTA para poder simular el funcionamiento de una matriz; a este tipo de listas también las denominan listas Bidimensionales o en otros lenguajes de programación Arrays Bidimensionales, dado que constan de una lista incrustada dentro de otra lista.

¿Qué particularidad tienen este tipo de lista Bidimensionales?, la caracteristica principal es que podemos acceder a los datos por medio de dos coordenadas [M,N], un ejemplo claro de esto es intentar acceder al valor g, que se encuentra en la lista bidimensional LB=[[1,2,3,4],['a','b','c','d'],[5,6,7,8],['f','g','h','i']], como podemos ver, para acceder al valor 'g', tendríamos que llamar a la variable LB así:  LB[3][1], lo cual nos devolvería el valor 'g'. Y aunque no lo parece, esta lista bidimensional tiene el mismo funcionamiento de una matriz de 4x4; para entenderlo un poco mejor habría que acomodar la lista en forma de matriz gráfica, quedando así:

Ahora que hemos organizado las sublistas en forma de matriz, ya podemos ver un poco su parecido ¿verdad?, pero bueno, para que quede más claro aun, al momento de llamar a la variable LB[3][1], lo que le estamos diciendo (ver imagen), es que de la fila 3, coja el valor de la columna 1, mirándolo junto con la imagen ese valor corresponde a 'g'.

Espero que con este ejemplo quede claro el funcionamiento de las listas bidimensionales como matrices, dado que comprender este funcionamiento nos dará las herramientas para entender el código.

Ahora, la manera que utilizamos para crear la matriz, es itinerando dos bucles for, uno dentro de otro, de esta manera el for interno nos agregará a la variable columna, un total de N caracteres u objetos que en este caso corresponden a la cantidad N de columnas, mientras tanto el bucle for inicial o superior al anterior, nos definirá cuantas veces quiere que creemos una variable columna (lista), que tenga todas las N columnas dentro de ella, con lo que estaríamos generando M filas, dado que estamos incrustando una lista dentro de otra lista, y en este caso la lista incrustada actuaría como Fila de la matriz.

camino_corto(f1,c1,f2,c2,lista): Esta función es la encargada de generar todo el camino o ruta desde un punto hasta el otro, así que para esto se piden 5 datos importantes, f1 y c1 que corresponden a las coordenadas del punto de origen, que en este caso serán por defecto (0,0). También tenemos f2 y c2, que corresponden a las coordenadas del punto final (siendo f2 la fila y c2 la columna), y por ultimo le pedimos que nos ingrese la matriz en la cual se llevaran a cabo estos procedimientos; dado que en python no están definidas las variables de tipo matriz, utilizamos listas bidimensionales que resultan tener el mismo funcionamiento (esta lista será generada por la función matriz(M,N)).

¿Como funciona el camino_corto? Bueno, en realidad en este caso su funcionamiento es muy sencillo pero vamos a utilizar funciones recursivas para que todo sea mucho más rápido; Partiendo del procedimiento manual que ya hicimos, tenemos claro que el primer paso que debemos hacer es comparar las filas de ambos puntos, en este caso f1 y f2; como ya sabemos, si ambas filas son iguales solo necesitaremos un desplazamiento entre columnas, pero si no son iguales, necesitamos aumentar f1 hasta que sea igual a f2, para después realizar el respectivo desplazamiento entre columnas.  Todo este procedimiento lo hacemos utilizando funciones recursivas, lo que quiere decir que dentro de la función, llamaremos de nuevo a la misma función, pero ahora con parametros diferentes, hasta que llegue a un punto donde se deje de llamar así misma y nos retorne el resultado final.

Recapitulando un poco, tenemos que:

1. Comparamos f1 y f2
   1. Si son iguales, quiere decir que el desplazamiento se hace en las columnas
      1. Aumentamos a c1 de uno en uno, hasta que sea igual a c2
   2. Si f1 es menor que f2, quiere decir que necesitamos desplazarnos por las filas
      1. Aumentamos f1 de uno en uno hasta que sea igual a f2
2. Cuando f1 y f2 sean igual, y c1 y c2 sean iguales, quiere decir que hemos hallado el camino, asi que detenemos el programa

Como podemos observar, con este codigo es obligatorio que primero se haga el movimiento en las filas y una vez f1 y f2 sean iguales, empezamos a realizar el movimiento entre columnas,  aumentando a c1 de uno en uno hasta que sea igual a c2.

 

Como podemos observar, el codigo funciona a la perfección y nos genera una ruta o camino desde el punto origen O(0,0) hasta el punto final P(8,6). Pero notamos que aunque nos da una ruta desde un punto hasta otro, dicha ruta no es la más corta :( , y pues nuestra verdadera meta es encontrar la ruta más corta posible entre ambos puntos, así que ahora diseñaremos nuestro algoritmos para que nos genere la ruta más corta.

¿Pero como podemos hacer para que halle la ruta más corta? Creo que todos concordamos en qué  el camino más corto entre dos puntos tendría que estar sujeto a pasos diagonales, como ocurre en la siguiente imagen.

¿Ahora cómo damos los pasos diagonales?, en principio la idea que precede es la de ir aumentando los pasos de forma (f1+1) y (c1+1) con esto obtendríamos cada punto "+" demarcado de cada paso, y haríamos este proceso tantas veces como sea necesario hasta que (f1+n) sea igual a (f2) y (c1+n) sea igual a (c2).

 

Gráficamente también podemos observar este comportamiento para poder dar los pasos diagonales; así que nuestro programa tendrá que hacer y funcionar de la misma manera (nota: no es obligatorio este funcionamiento, se puede hacer de diferentes maneras), pero también sin olvidar que aunque tenemos pasos diagonales, en muchos casos se necesitan pasos horizontales (sobre las columnas). El código que hice  es prácticamente el mismo que el que utilizamos antes, pero con la pequeña excepción de que ahora nuestra función camino_corto(), será mucho más extensa y explicita, dado que agregamos no solo pasos diagonales sino también pasos horizontales y verticales (desplazamiento por columnas y por filas).

Ver codigo en Pastebin[2].

Como pueden observar, el único cambio que sufrió con respecto al primer código que hicimos, yace en la función que busca el camino_corto(), en donde ahora especificamos los pasos diagonales junto con los horizontales y verticales.

Aunque el código parece largo es muy simple de comprender, básicamente solo hemos colocado ciertos pasos extra con respecto al código anterior que diseñamos; Para poder saber si se puede dar un paso diagonal (f1+n,c1+n), lo primero que revisamos es si f1+n y c1+n siguen siendo menores o iguales que f2 y c2, en caso de que sean menores, podemos dar el paso en forma diagonal sin ningún problema, dado que no corremos el riesgo de pasarnos el punto final; En caso de que sean iguales f1+n=f2 y c1+n=c2, quiere decir que solo nos queda un paso diagonal por dar y después de eso habremos llegado hasta nuestro punto final (f2,c2); si se fijan bien, cuando decimos o evaluamos f1+n y c1+n, lo que en verdad estamos haciendo es como  llevar una vara o perro guía,  él nos dirá si al hacer ese paso, quedaremos fuera del punto que esperábamos o aun nos faltan pasos por dar, pero es importante tener en cuenta que simplemente nos estamos preguntando eso, aun no hemos dado el paso hasta que no estemos seguros de la respuesta de nuestro perro guía :)

En principio con el código que hicimos, no estamos evaluando a f1+n y c1+n de forma simultanea, primero hacemos las comparaciones por fila, (f1==f2) (f1+n==f2) (f1+n<f2) y según el resultado de cada una de estas posibles comparaciones entre filas, definimos las posibles comparaciones entre columnas (c1==c2) (c1+n<c2) (c1<c2)... teniendo los datos de estas comparaciones definimos que paso dar, ya sea un paso en forma diagonal, vertical(filas) o horizontal(columnas), obviamente tenemos que guardar registro de cada paso que demos, en este caso la manera de guardar dicho registro consiste en que cada nueva posición la demarcaremos con el carácter "+" .

Y este es básicamente el funcionamiento de nuestro querido programa que encuentra la ruta más corta entre el punto de origen O(0,0) y un punto P(x,y) cualquiera. Espero que lo disfrutaran y pues que entendiesen este concepto, en realidad me anime un poco en hacer este post, dado que al principio uno mira complicado el problema pero después se va desentrañando hasta su más oscuro ser y resulta no ser  tan complicado como en un principio se pensaba;  Sí!!, la matrices se utilizan mucho en programación, una vez tienes los conceptos fundamentales podrás plantearte la manera en como resolver muchos problemas...

Cualquier duda, comentario o insulto, sera bienvenido y con gusto les sera respondido.