Durante una época dediqué mis esfuerzos a propiciar lo que ahora se llama Computational Think a través de la programación lógica. Había una forma de analizar los problemas, era a través de la búsqueda en profundidad en esquemas arborescentes, habiendo transformado previamente los problemas en esquemas en árbol, es decir habiendo obtenido una representación de este tipo del problema.
Se trataba de implementar esquemas lógicos a través del lenguaje de programación Prolog. Simplificando mucho es lo que hacía con la geometría, la recursividad o la modularización LOGO. Todo ello concluyó en la edición de un libro, del que ahora queda algún ejemplar por las librerias de viejo:
TÉCNICAS DE PROGRAMACIÓN DECLARATIVA EN EL AULA. TURBO PROLOG 2.00.
ZAPATA ROS, Miguel.
De él sacamos lo que sigue.
El problema de los puentes de Könisberg y el backtraking
En la programación declarativa, en determinadas ocasiones interesa cortar la búsqueda en profundidad y provocar el Backtracking en un punto determinado.
Esto sucede cuando, por ejemplo, queremos obtener una única respuesta a una interrogación, y previsiblemente el programa contiene alguna bifurcación.
También sucede cuando el programa tiene un crecimiento desmedido en función de la abundancia de nodos del árbol correspondiente, o de cláusulas dobladas o triplicadas.
En este caso se produce lo que se llama una “explosión combinatoria" o un “crecimiento exponencial”. De tal manera que el ordenador puede perderse en la búsqueda o verse desbordado en su capacidad por un crecimiento de este tipo.
Otra ocasión en que, por ejemplo, conviene cortar la búsqueda se produce cuando el ordenador cae en un bucle sin fin.
Otras veces lo que interesa es provocar la vuelta atrás aunque ésta no tenga en buena lógica por qué producirse. De tal manera que una vez conseguido un objetivo parcial y satisfecha una cláusula, el ordenador se comportase a todos los efectos como si la búsqueda hubiera fallado, forzando con ello seguir la búsqueda en profundidad en esa rama por si hubiera más cláusulas que la satisfaciesen, en vez de esperar a que se culminase la vuelta atrás.
Este recurso interesa sobre todo cuando queremos que se produzcan una serie de acciones en un determinado orden. Es decir que funcione, el programa y el sistema, de modo procedimental.
Para ambos fines -corte y fallo- existen en Turbo Prolog dos predicados predefinidos: ! (CORTE) y FAIL (FALLO).
Veamos ahora con más detenimiento cómo funcionan. Para ello vamos a utilizar varios ejemplos. Uno de ellos nos lo proporciona el problema de “Los puentes de Kónigsberg”:
Königsberg (hoy Kaliningrado) es una ciudad de la Prusia oriental (donde nació, murió y vivió toda su vida Immanuel Kant), en la parte que actualmente pertenece a la Federación Rusa, cruzada por el río Pregel (hoy Pregolya) que forma dos islas, entre las cuales y las dos orillas habí una serie de siete puentes:
Mapa de Königsberg en la época de Leonhard Euler, que muestra dónde se encontraban los siete puentes (en verde claro) y las ramas del río (en celeste).
http://upload.wikimedia.org/wikipedia/commons/thumb/5/5d/Konigsberg_bridges.png/300px-Konigsberg_bridges.png (URL de la imagen)
En la actualidad en Google Maps lo podemos ver:
Dos de los siete puentes originales no sobrevivieron al bombardeo de Königsberg en la Segunda Guerra Mundial. Otros dos puentes fueron posteriormente demolidos y reemplazadas por una moderna autopista. Los otros tres puentes se mantienen, aunque sólo dos de ellos son de la época de Euler (uno fue reconstruido en 1935).
Por lo tanto, a partir de 2000 , en la actualidad hay cinco puentes en Kaliningrado.
En rojo los que se conservan, al menos en su posición. En azul los que no existen.
Vista de STREET VIEW desde el puente que une las dos islas, que las unen según el esquema.
En la época en que escribimos el libro no existía Google Maps. Utilizamos algo más esquemático:
Las gentes de esta ciudad discutían frecuentemente sobre si era posible ir de una orilla a la otra pasando por todos los puentes una sola vez.
Este problema alcanzó fama en su tiempo y fué finalmente resuelto en sentido negativo por Euler en 1.736.
No obstante es frecuentemente utilizado, aún hoy día, como ejemplo en Topología, Teoría de Grafos, etc.
En el libro lo utilizamos como hemos visto como ejemplo para ilustrar Backtraking, corte y fallo. Lo formalizamos utilizando para ello un programa Prolog. Lo hacemos en pasos sucesivos y aprovecharemos para comentar los predicados “corte” y “fallo”.
A los amigos prologueros proponemos completar el
programa para resolver el problema completo utilizando PROLOG.
El procedimiento en esencia viene ilustrado en las cuatro páginas que adjuntamos:
Comentarios
Publicar un comentario