domingo, 25 de noviembre de 2018

¿Existe un método universal para resolver problemas?

No tengo duda de que los genios no nacen, sino se hacen a través de practica efectiva acumulada (recomiendo ver estos videos [Pt1,Pt2]). Entiendo también que debe haber una componente genética en el proceso, pero no la considero sustancial. Si todos podemos ser genios, entonces la pregunta ahora es si existe un método efectivo que no vuelva maestros de la resolución de problemas. No podría dar alguno pero si creo que si es posible hacer un bosquejo inicial que nos lleve al método que buscamos si lo refinamos lo suficiente.

Definir el problema. Aparentemente esto no parece llevarnos a algún lado pero pensémoslo de otra manera. Cuando comencé a aprender Prolog me pareció muy interesante el hecho de que la solución a un problema se encuentra únicamente a través de la definición correcta del problema. No es que la solución brote de la anda. Prolog al ser un lenguaje declarativo, su interprete utiliza una serie de algoritmos que procesan los "hechos" del problema. Si le das al interprete una descripción de los hechos lógicamente consiste al problema que quieres resolver entonces tendrás su solución. Esto es un ejemplo de como un replanteamiento del problema puede abrirnos un camino a su solución.

Dividir el problema en sub-problemas. Si el problema es simple (no necesariamente fácil de resolver, pero simple en el sentido de no ser divisible) este paso no será necesario. Pero si el problema es complejo, resulta muy útil partirlo en diferentes problemas (en principio más fáciles de resolver). Pudiera ser el caso que para resolver el problema sea necesario primero desarrollar alguna habilidad en particular o investigar sobre algún tema en especifico (la práctica e investigación también son sub-tareas en este sentido).

Cuestionar las restricciones. Este punto está relacionado con la definición del problema. Una vez que lo hemos definido tenemos que pensar: ¿son necesarias todas las restricciones que estoy considerando o estoy poniendo restricciones que no existen en el problema? Esto se conoce también como pensar fuera de la caja. Es necesario hacer notar que hace falta definir la caja antes de hablar sobre lo que está fuera de ella. Por ello, esto debe hacerse sólo después de hacer al menos un primer intento de definición del problema.

Explorar los recursos disponibles. Cuando se haya definido el problema y descartado restricciones ficticias es hora de poner manos a la obra. Se deben hacer las siguientes preguntas: ¿qué podría usar de todo lo que sé y de todo lo que está a mi alrededor (o en el ambiente o contexto del problema)? ¿he resuelto antes problemas similares?, en caso de que me falte experiencia o información ¿dónde podría conseguirla o a quién podría consultar? Una técnica también inspirada de Prolog es hacer un diccionario de hechos y reglas , es decir, anotar o tener presente en la mente todas las características de los elementos y relaciones de causa y efecto tanto en el problema como en el ambiente del problema [cosas como: "A es un T","si ocurre X entonces Y", "si se quita W entonces Z", etc].

Pensar al revés. Sé que quisiéramos que las soluciones a nuestros problemas estén a un sólo paso de nosotros. A veces es verdad y esa solución se hace evidente al definir el problema de forma ingeniosa o de eliminar restricciones ficticias. Pero muchas veces los problemas requieren de una solución de varias etapas. Una manera de atacar este tipo de problemas es partir del estado deseado (meta) que llamaremos "G(n)" y tratar de pensar: ¿cual tendría que ser el estado anterior inmediato G(n-1)? ¿cómo podría resolver de G(n-1) a G(n)? Este proceso es básicamente una división en subproblemas pero en orden temporal inverso hasta llegar al primer paso [G(1) a G(2)]. Esto se conoce como análisis retrospectivo.

Resistir la frustración. En lo personal creo que este el punto más importante de todos. No es un aspecto metodológico sino psicológico, pero que al dominarlo nos da una herramienta invaluable. No siempre veremos la solución al primer intento. Somos humanos y no puedo pedir no sentir enojo o desesperación ante una falla, pero si pido aguantarla. La buena noticia es que la resistencia o tolerancia a la frustración es como un musculo que se vuelve más fuerte entre más se ejercite. Algunos recomiendan tomar descansos entre las fallas. A mi en lo personal me ha servido muchas veces la actitud de "no me voy a ir de aquí hasta que funcione". Depende realmente de la persona, pero la idea es aguantarse y hacerse fuerte ante el fracaso.

Buscar tener nuevos problemas. Esto pareciera ser algo que todos queremos evitar, pero volverse un masoquista intelectual te da, con el tiempo, un repertorio muy amplio de experiencias que te permite resolver problemas similares, muchas veces con sólo recordar y modificar ligeramente soluciones pasadas.

Todo lo anterior es un apunte personal. No voy a decir que es el elixir sagrado de la resolución de problemas. Pero es lo que me ha funcionado y son notas que iré extendiendo o mejorando sobre la marcha de mi vida.

martes, 6 de noviembre de 2018

Resolviendo acertijos con Prolog

Empecé a aprender Prolog hace unos 2 días. Aunque ya había oído sobre él hace años, me entró mucha curiosidad de aprender a usar este lenguaje en agosto durante un simposio en el IIMAS en dónde presentaron las investigaciones del grupo Golem, quienes desarrollan robots de asistencia. Me impresionó el grado de entendimiento que parecían tener sus robots sobre su entorno a la hora de procesar lenguaje natural y realizar tareas. El sesión de Q@A se comentó que sus programas estaban basados en buena parte en Prolog. La verdad me costó bastante comenzar a pensar como un programador declarativo de forma fluida. Afortunadamente hay bastantes recursos para principiantes, aunque se vuelve más difícil encontrar material claro conforme se avanza en el lenguaje. En esta entrada sólo quiero hacer una corrección a una solución que se da aquí. (Si quieren aprender Prolog desde 0, les recomiendo este curso en Youtube en español. No recuerdo si lo menciona pero pueden usar este compilador en linea: https://swish.swi-prolog.org/ [Este otro curso es más completo pero esta en inglés]). Bien, el acertijo es el siguiente:

”Un alumno de ITS, debido al nerviosismo del primer día de clase, ha anotado el nombre de sus profesores (Elisa, Fernando y Carlos), las asignaturas que se imparten (Lógica, Programación y Matemáticas) y el día de la semana de las distintas clases (lunes, miércoles y viernes), pero sólo
recuerda que:
- La clase de Programación, impartida por Elisa, es posterior a la de Lógica
- A Carlos no le gusta trabajar los lunes, día en el que no se imparte Lógica
Ayudale a relacionar cada profesor con su asignatura, así como el día de la semana que se imparte
(Sabemos que cada profesor imparte una única asignatura y que las clases se dan en días diferentes)”


El acertijo es sencillo y se puede resolver mentalmente. Pero aquí lo interesante es pensar en como resolver este problema con un lenguaje declarativo como Prolog. La falla en el programa de respuesta de este acertijo radica justamente en no considerar que es necesario decirle a la máquina de forma clara cuales son las restricciones del problema. Porque en Prolog, como en el dicho popular, "lo que no está prohibido está permitido". Si se hace la consulta con la base de datos del programa original se puede verificar que trabaja(P,D),imparte(P,M),clase(M,D) devuelve la respuesta correcta del acertijo:

D = miercoles,
M = logica,
P = carlos
D = viernes,
M = programacion,
P = elisa
D = lunes,
M = matematicas,
P = fernando

Si pensamos como un programador tradicional imperativo esto nos debería parecer suficiente. El punto es encontrar esa respuesta ¿no?. El problema es que en un programa de Prolog, todas las consultas deben ser consistentes con las restricciones y soluciones del problema. Observen ahora que si hacemos, por ejemplo, la consulta trabaja(fernando,viernes) ¡la respuesta es verdadera! Esto significa que la computadora no está "entendiendo" realmente la situación. Mi versión de la respuesta que corrige este inconveniente es la siguiente:

Puede verificarse que ahora todas las consultas son consistentes con el problema. La solución la estructuro como una lista de listas con la forma:

S = [[P0,M0,lunes],[P1,M0,miercoles] ,[P2,M0,viernes] ]

Se debe dejar claro que las variables en la lista no pueden repetirse una vez usadas (como lo establece el acertijo). Declaro esto con:

    permutation([P0,P1,P2],Profesores),
    permutation([M0,M1,M2],Materias),  

La función permutation(listaA,listaB) retorna verdadero si listaA es alguna de las posibles permutaciones de listaB. Para entender el resto del programa hará falta revisar el manejo de listas y variables anónimas en los cursos que enlacé. En lo que quiero hacer énfasis es  en que buena parte de los problemas lógicos en los que se requiere repartir atributos a un grupo de objetos pueden resolverse estructurando la respuesta como una lista o una lista de listas y jugando con los operadores de pertenencia, permutación y relaciones de posición entre los elementos de la lista.