Camino Escondido

 

Ya anteriormente he escrito sobre técnicas de búsqueda, como en esta ocasión no intento desarrollar el tema, les recomiendo que para una introducción más amplia revisen mi anterior apunte el cual pueden encotrar en: http://www.olimpiadadeinformatica.org.mx/Clases.htm

La idea de este apunte es ilustrar la forma correcta de definir un espacio de búsqueda para resolver un problema de manera eficiente, en especifico, el problema a resolver es Camino Escondido.  Para los que no conozcan el problema, hago un breve resumen eliminando la historia y presentando el problema matemático de forma plana:

Se tiene una matriz de números enteros de tamaño N x N y una secuencia S de números también enteros.  Se desea encontrar un camino, realizando movimientos sólo en sentido vertical u horizontal, que vaya desde cierta celda A en la fila superior hasta cierta celda B en la fila inferior tal que los números en las celdas por las que pase el camino correspondan a los números en la secuencia S en el mismo orden.  En caso de que los números de la secuencia S se terminen se inicia de nuevo por el primero.  Por ejemplo, para una secuencia S={3,5,8} los caminos {A,3,5,8,3,5,B}, {A,3,5,B} ó {A,3,5,8,3,5,8,3,5,8,B} serían caminos válidos (obviamente además de estos tres hay muchos otros caminos que también serían válidos).  El tamaño máximo para N es 300 y el largo máximo para la secuencia S es 50.  Como resultado se deberá entregar el largo del camino válido más corto que exista o un -1 en caso de que no exista ningún camino válido.

El problema se presenta de manera inmediata como una búsqueda, el alumno "...debe encontrar un camino...". En cualquier búsqueda la primera pregunta que debe acudir a la mente del "buscador" es ¿Qué estoy buscando? Aunque suena obvio, la mayoría (y al decir mayoría hablo en verdad de una amplia mayoría) de los alumnos a los que he visto a lo largo de los años, rara vez se hacen esta pregunta de manera explícita.  Hagámoslo entonces esta vez.

¿Qué estoy buscando? Para contestar correctamente la pregunta es necesario haber leído con atención el problema y comprenderlo correctamente. En este caso específico, estamos buscando el camino válido más corto entre la celda A y la celda B. 

Ya sabemos lo que estamos búscando. ¿Cuál es el siguiente paso? Por supuesto, algo que parece obvio y sin embargo poca gente hace; preguntarse ¿Cómo es lo que estoy buscando? Para cuestiones de problemas de informática esto se traduce: ¿Cómo se representa lo que estoy buscando?

¿Cómo se representa lo que estoy buscando? Para este problema, un camino se representa como una secuencia de celdas contiguas, ya sea de manera horizontal o vertical, de la matriz, que inicia en la celda A y termina en la celda B.

Una vez especificado el objeto que buscamos, surgen varias otras preguntas interesantes sobre las características del mismo. Estas preguntas se aplican a casos particulares y no es sencillo generalizarlas como las dos anteriores, sin embargo, basta decir que una vez especificado el objeto de la búsqueda deben intentar conocerse la mayor cantidad de características posible del mismo.

Un punto importante para el problema que estamos investigando es:

¿Cuál es el largo máximo que puede tener un camino? Inicialmente podríamos pensar que el largo máximo posible es el número de celdas en la matriz, es decir, NxN. Pero leyendo el problema con atención podremos observar que nunca se dijo que el camino no podía pasar 2 veces por la misma celda.  Eliminada esta limitante vemos entonces que el largo máximo de un camino puede ser mayor que el número total de celdas de la matriz. De hecho, el largo máximo de un camino puede ser MUUUY grande.

Muy bien, ya sabemos que estamos buscando, también sabemos como es. Sigamos adelante, aqui viene la pregunta más importante hasta el momento ¿En donde debemos buscarlo?

¿En donde debemos buscar? Esta es la pregunta clave en cualquier problema de búsqueda y su correcta respuesta es lo que nos definirá el espacio de búsqueda. Volvamos a nuestro problema, la primera opción que se ocurre es construir todos los caminos posibles (válidos e inválidos) y entre ellos buscar el que queremos.

Dado que no definimos una cota superior para el largo máximo del camino, la cantidad de caminos que podemos construir es hasta el momento infinita, y aunque ya salió al mercado el Intel Xeon Dual Dual Core con HyperThreading (que equivale a tener 8 procesadores en paralelo), aún eso es insuficiente para buscar entre un número infinito de caminos. Por suerte para nosotros no es necesario que esperemos 5 años más (estoy escribiendo en enero del 2007) para que salga al mercado, el ahora en prototipo, microprocesador de 80 nucleos. Que de cualquier forma seguiría siendo insuficiente ;)

Una vez definido un primer espacio de búsqueda, el siguiente paso es recortarlo lo más posible hasta llegar a una cardinalidad manejable. Para nuestro problema hay dos recortes inmediatos:

 

Hemos avanzado algo, sin embargo, aún no llegamos a un punto en donde podamos asegurar una correcta solución en tiempo para cualquier instancia posible del problema. Es muy importante siempre calcular el tamaño del espacio de búsqueda y pensar que en el peor de los casos nuestro programa va a tener que buscar en la totalidad del espacio, piensen en el caso en el que no haya solución, para estar seguros tenemos que buscar entre todas las opciones, de modo que para asegurar una calificación de 100% requerimos que el tamaño del espacio sea tal que aún examinándolo completamente nuestro programa termine en el tiempo establecido.

¿Cómo continuar?  Cuando se han aplicado a un espacio de búsqueda todos los recortes que se ocurren sin éxito, una técnica que resulta efectiva en muchos casos es la siguiente: determinar si dentro de las posibles soluciones existen sub-soluciones que sean equivalentes.  :O !!!???

A que nos referimos con el enunciado anterior. Es común para muchos problemas que una solución se construya con elementos más básicos, a los que en este caso llamamos sub-soluciones­.  Para nuestro problema, dado que una solución es un camino, una sub-solución sería un prefijo del camino, es decir, si la solución es {A,3,5,8,3,B}, entonces {A,3,5} es una sub-solución, ya que a partir de ella podemos construir la solución que buscamos. Dos sub-soluciones son equivalentes si la forma de llegar desde ellas a la solución búscada es EXACTAMENTE LA MISMA.

¿De qué nos sirve tener sub-soluciones equivalentes? En realidad eso depende un poco del problema específico, sin embargo, en la mayoría de los casos el beneficio viene de que dos sub-soluciones se pueden comparar de manera directa y en base a eso decidir cual de las dos es óptima dados los criterios que buscamos.

Apliquemos la técnica a nuestro problema para aclarar un poco las cosas.

¿Cuáles serían dos sub-soluciones equivalentes? Dijimos anteriormente que una sub-solución es cualquier prefijo de un camino solución, como un camino es un sucesión de celdas de la matriz, entonces una sub-solución se definiría como una sucesión de celdas en la matriz que va de la celda A a la celda Q.  La solución debe de seguir los números especificados por la secuencia S, de modo que nuestra sub-solución que termina en Q además se encuentra en una cierta posición de la secuencia S a la que llamaremos p.  Supongamos ahora que conocemos la solución desde (Q,p) hasta B, entonces todas las sub-soluciones que terminen en (Q,p) son equivalentes ya que su camino hacia B es el mismo sin importar la manera en la que llegaron a (Q,p).

Como dijimos antes, lo bueno de encontrar sub-soluciones equivalentes es que las podemos comparar de manera objetiva. Para nuestro problema, queremos el camino más corto. Si tenemos dos sub-soluciones (Q,p) su camino más corto hacia la celda B es el mismo, por lo tanto, podemos decir que la sub-solución cuya longitud sea menor entre las dos es mejor para nuestros propositos, si ambas son de la misma longitud, entonces podemos simplemente tomar cualquiera de las dos, ya que, a fin de cuentas, son equivalentes.

Esto nos limita nuestro espacio de búsqueda dramaticamente, ya que no tenemos que buscar dos veces en un misma sub-solución, de modo que nuestra búsqueda se limita a la cantidad de sub-soluciones que existan.  Para nuestro caso todas las duplas (Q,p) posibles. Dado que Q es una celda de la matriz, existen N x N posibles valores para Q.  Asi mismo, p representa una posición en la secuencia S así que la cantidad de valores posibles para p es igual al largo de la secuencia S.  Sustituyendo por los valores máximos posibles tenemos que en el peor caso nuestra búsqueda abarcara un total de (300) x (300) x (50) = 4,500,000 estados!  Algo completamente asequible incluso para un modesto Pentium III a 800MHz en alrededor de 1 segundo.

Queda un último problema por resolver, para que nuestra idea funcione, es necesario que no necesitemos revisar más de una vez cada sub-solución. Para que esto sea cierto, tenemos que asegurar que la primera vez que nos topamos con una sub-solución desconocida hasta el momento, lo hacemos con el mejor camino posible.  Sin embargo esto es algo sencillo de hacer y que queda como tarea, al igual que la implementación para el lector.  Como nota cabe aclarar que una implementación razonable de esta solución no debe abarcar mas alla de 50 líneas (incluidas declaraciones), así que no busquen nada complicado :)