Ir al contenido principal

El problema de los puentes de Königsberg

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).

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

Entradas populares de este blog

Ingeniería de la instrucción/ Ingeniería educativa

Image courtesy CSU Instructional engineering/ Educational Engineering Introducción Según The International Association of Engineers (IAENG) , en su declaración de principios : La palabra "ingeniería" se deriva del latín "ingenium", que significa algo así como "idea brillante", o "destello de genio". Data del siglo XVI, época en que fue aceptada en pleno Renacimiento, impregnada de su espíritu humanista,  y originalmente describía una profesión a la que probablemente hoy llamaríamos  inventor artístico . Los ingenieros aplican los principios y el conocimiento que se tiene de las ciencias matemáticas y naturales, con criterio y creatividad, a desarrollar formas de utilizar los materiales y las fuerzas de la naturaleza en beneficio de la humanidad. Los temas son diversos e incluyen nombres como bioingeniería, ingeniería informática, ingeniería eléctrica y electrónica, ingeniería financiera, ingeniería industrial,.. y hoy incluso se u

Microcredenciales y credenciales acumulables, la última vuelta de rosca de las disrupciones y de la nueva educación universitaria

Seguimos con la evolución que empezó siendo de la educación universitaria abierta online , continuó con las disrupciones universitarias , y ahora se convierte, tras la asunción de significativos estudios formales universitarios en sus grados y postgrados de lo desarrollado en las disrupciones, acelerado por la pandemia, y de lo aprendido con todo ello, en la incipiente NUEVA EDUCACIÓN UNIVERSITARIA . Presentamos pues la nueva ampliación de la línea de tiempo con las microcredenciales o credenciales acumulables . En los artículos, posts y otras intervenciones que se están produciendo, se aduce a factores económicos y de rendimiento de los estudios sin necesidad de culminar los grados y postgrados oficiales. No podría ser de otra forma cuando el epicentro se sitúa en las universidades norteamericanas, donde el coste de los estudios recae directamente sobre estudiantes y familias, así como, en su caso, el rendimiento. También en centros empleadores que pueden encontrar antes una mano

Los periódicos, la universidad y otras crisis

El domingo, cuando bajaba a hacer mi habitual caminata a las 9, vi el quiosco cerrado, me llamó la atención, algo no era igual. Hoy vemos cómo los quioscos languidecen, cuando no cierran. Todos recordamos la ansiedad con que en otros tiempos esperábamos que llegase la edición de Informaciones, Diario 16, El País o el nuevo número de Triunfo. También nos evocan épocas clave para nuestra historia y nuestras historias, y el papel que jugaron en ellas los periódicos, su influencia en la creación de opinión y en la toma de decisiones. Todos recordamos a   Randolph Hearst y a   Ciudadano Kane. La imagen de un quiosco cuya máxima utilidad es la de servir de soporte urbano para la publicidad, como valla, impacta fuertemente sobre esa idea, al tiempo que resulta paradigmática. Algo ha terminado y ya no será igual. La fuerza de la imagen contrarresta todas las argumentaciones que de forma ladina se escriben para disimular la crisis de la prensa impresa y para que no se produzca el e