Laberintos (Parte 9)

(A la parte 8 - A la parte 10)

Reglas

La dificultad de un laberinto (o de un problema) no es en realidad una propiedad objetiva del laberinto en sí (entendiendo la palabra “objetiva” como sinónimo de “independiente del observador”). La dificultad, por el contrario, resulta de la interacción entre el laberinto y quien esté intentando resolverlo. Distintos resolvedores podrán tener eventualmente distinta percepción de qué tan difícil es el problema.

Dicho en otras palabras, un mismo problema puede resultar difícil para una persona, pero fácil para otra. Esto puede suceder, por ejemplo, si la segunda persona tiene más experiencia o mejor preparación que la otra. Si queremos plantear una teoría razonable para medir la dificultad de un laberinto esta circunstancia debe ser tomada en cuenta.

La experiencia o la heurística de Teseo (tal el nombre que siempre daremos al resolvedor) estará representada por un conjunto de reglas de movimiento, las cuales restringen las decisiones que puede tomar Teseo cuando llega a un nodo (recuérdese que sólo en los nodos es donde Teseo cambia de dirección). A modo de ejemplo, mostremos dos reglas posibles, a las que llamaremos reglas básicas:

Regla de no retroceso: cuando Teseo llega a un nodo no retrocederá por el eje por el que acaba de llegar (a menos, claro está, que se trate de un nodo terminal, es decir, que haya llegado a un callejón sin salida en cuyo caso el retroceso es inevitable).

Regla del subgrafo: si Teseo ha recorrido completamente un subgrafo (es decir, ha recorrido todos los nodos y los ejes de cierta región del laberinto) sin encontrar la salida, entonces ya no volverá a entrar en ese subgrafo.

(Aclaración sobre la regla del subgrafo: recuérdese que Teseo lleva un registro de todo lo que ha recorrido y que puede hacer marcas en las paredes del laberinto. Supongamos que llega a un nodo por el que ya ha pasado y que observa que uno de los ejes que salen de ese nodo, por el que ya ha pasado, lleva a una región del laberinto que ya ha explorado completamente, sin éxito. Es decir, que si siguiera por ese eje es seguro que no obtendría ninguna información nueva. En ese caso Teseo omitirá volver a pasar por ese eje.)

Vamos a suponer que cualquier conjunto de reglas considerado contiene al menos estas dos reglas básicas, las cuales están enunciadas bajo la suposición de que Teseo sólo ve el nodo en el que se encuentra (y que, como ya fue dicho tiene registro de todo lo recorrido anteriormente). Si suponemos que, además, Teseo puede ver algunos nodos aún no recorridos (véase al respecto la Parte 5) entonces a estas reglas básicas se agregará la siguiente:

Regla de la salida: si Teseo puede ver la salida entonces se dirigirá a ella por el camino más corto disponible.

Es posible agregar otras reglas, todas las cuales tendrán el objetivo de ayudar a Teseo en su empeño por llegar a la salida. De hecho, las reglas podrán ser específicas de cada tipo de problema. Por ejemplo, si el grafo representa un Sudoku, las reglas reflejarán los trucos y atajos del resolvedor avezado de esa clase de problemas.

Observación: la dificultad del laberinto dependerá del conjunto de reglas establecido, es decir, hablaremos de la dificultad relativa a tal o cual conjunto de reglas. Para un resolvedor más avezado (con un mejor conjunto de reglas) la dificultad del laberinto será en general menor que la dificultad que perciba un resolvedor menos avezado.

Los siguientes postulados limitan las reglas posibles:

Postulado 6: Las reglas están enunciadas en función de la información que posee Teseo.

Postulado 7: Existe al menos un camino que conecta la entrada con la salida y que respeta todas las reglas.

(El postulado 7 quiere decir que el conjunto de reglas debe ser tal que para todo laberinto existe al menos un camino que conecta la entrada con la salida y que es ejecutable sin violar ninguna de las reglas del conjunto. Como tema general de investigación pueden establecerse distintos conjuntos de reglas de movimiento y estudiar qué grafos son conexos con respecto a ellas.)

Postulado 8: Si R y S son dos conjuntos de reglas y R está contenido en S entonces la dificultad relativa a R es mayor o igual que la dificultad relativa a S (dicho más fácilmente, al agregar reglas la dificultad no puede aumentar.)

(Dado un conjunto de reglas, el postulado 8 limita los modos de medir la dificultad y dado un modo de medir la dificultad, limita las reglas que pueden agregarse.)

Observaciones: 1) Podría suceder que al llegar un nodo hubiera conflicto entre dos o más reglas, en ese caso una regla especial indicará cómo proceder (no vale la pena entrar en detalles en este momento, pero puede establecerse un orden de jerarquía entre las reglas o que se elegirá al azar la regla que se aplique u otra alternativa.)

2) A menos que se indique lo contrario, en los ejemplos siempre supondremos que Teseo puede ver solamente el nodo en el que se encuentra, que tiene registro de lo recorrido anteriormente y que sólo usa la regla del subgrafo y la regla de no retroceso.

3) Si al llegar a un nodo la decisión de Teseo no queda completamente determinada entonces elegirá al azar entre todos los ejes permitidos.

En la próxima parte veremos un ejemplo de la aplicación de estas reglas.

(A la parte 8 - A la parte 10)