(A la parte 9 - A la parte 11)
Una regla más
Agregamos a las reglas básicas la siguiente:
Regla de no repetición: si Teseo llega a un nodo ya visitado, al elegir el camino que seguirá, habrá de descartar todos los ejes que ya hubiera transitado antes (si todos los ejes que salen de ese nodo ya han sido recorridos, entonces esta regla no se aplica).
(A la parte 9 - A la parte 11)
24.3.07
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)
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)
22.3.07
Dos tipos de entradas
En este blog hay dos tipos de entradas: las que hacen alguna referencia a sí mismas (del tipo que sea) y las que no lo hacen.
Esta entrada pertenece al segundo tipo.
Bueno, pertenecía al segundo tipo hasta el momento en que escribí la oración anterior, en cuyo caso pasó a formar parte del primer tipo.
Pienso escribir una entrada donde se haga referencia a todas las entradas que no hacen referncia a sí mismas, y sólo esas. Todavía no he decidido si esa entrada debe referirse, o no debe referirse, a sí misma.
Esta entrada pertenece al segundo tipo.
Bueno, pertenecía al segundo tipo hasta el momento en que escribí la oración anterior, en cuyo caso pasó a formar parte del primer tipo.
Pienso escribir una entrada donde se haga referencia a todas las entradas que no hacen referncia a sí mismas, y sólo esas. Todavía no he decidido si esa entrada debe referirse, o no debe referirse, a sí misma.
18.3.07
Laberintos (Parte 8)
(A la parte 7 - A la parte 9)
Suma de laberintos
La suma de los laberintos A y B es el laberinto que se obtiene fusionando la salida de A con la entrada de B:
Postulado 5: La dificultad de A + B es mayor o igual que la suma de la dificultad de A más la dificultad de B.
(A la parte 7 - A la parte 9)
Suma de laberintos
La suma de los laberintos A y B es el laberinto que se obtiene fusionando la salida de A con la entrada de B:
Postulado 5: La dificultad de A + B es mayor o igual que la suma de la dificultad de A más la dificultad de B.
(A la parte 7 - A la parte 9)
15.3.07
Laberintos (Parte 7)
(A la parte 6 - A la parte 8)
Más postulados
Algún tiempo atrás vimos un laberinto y un grafo que servía para representarlo (el grafo A del dibujo de más abajo):
Más postulados
Algún tiempo atrás vimos un laberinto y un grafo que servía para representarlo (el grafo A del dibujo de más abajo):
Pero si bien se mira el grafo B también representa el mismo laberinto. Por lo tanto, aunque A y B no son equivalentes, es razonable que tengan la misma dificultad. Observemos que A se obtiene de B agregando tres nodos a lo largo de uno de sus ejes. Tenemos entonces:
Postulado 4: Si el grafo A se obtiene agregando nodos a lo largo de uno de los ejes de un grafo B entonces A y B tienen la misma dificultad.
7.3.07
Laberintos (Parte 6)
(A la parte 5 - A la parte 7)
Postulados
Vamos a comenzar a establecer algunos postulados que, razonablemente, deberá cumplir cualquier método que se proponga para medir la dificultad de un laberinto.
Postulado 1: La dificultad de un laberinto es un número real mayor o igual que cero. (Obviamente, cuanto mayor sea el número más difícil es el laberinto.)
Postulado 2: La dificultad del laberinto trivial es cero.
Por laberinto trivial entendemos el laberinto que tiene solamente dos nodos (entrada y salida) unidos por un único eje.
Postulados
Vamos a comenzar a establecer algunos postulados que, razonablemente, deberá cumplir cualquier método que se proponga para medir la dificultad de un laberinto.
Postulado 1: La dificultad de un laberinto es un número real mayor o igual que cero. (Obviamente, cuanto mayor sea el número más difícil es el laberinto.)
Postulado 2: La dificultad del laberinto trivial es cero.
Por laberinto trivial entendemos el laberinto que tiene solamente dos nodos (entrada y salida) unidos por un único eje.
Antes de enunciar el tercer postulado imaginemos que los grafos están formados por cuentas de colores unidas por hilos, e imaginemos también que podemos mover las cuentas estirando o contrayendo los hilos tanto como se quiera, sin cortarlos y sin despegar o unir cuentas. Dos grafos se dirán equivalentes si pueden obtenerse uno del otro por medio de las transformaciones que acabamos de describir (como antes, es posible dar definiciones más rigurosas de estos conceptos, pero para todos nuestros fines estas definiciones intuitivas serán más que suficientes).
Por ejemplo, en el dibujo siguiente, los grafos A y B son equivalentes entre sí, pero C no es equivalente a ninguno de los otros dos:
Postulado 3: Dos grafos equivalentes tienen la misma dificultad. (En otras palabras, la dificultad es un invariante topológico de un laberinto.)
En la próxima parte veremos otros postulados que deberán respetarse al medir la dificultad de un laberinto.
Laberintos (Parte 5)
(A la parte 4 - A la parte 6)
Una objeción
Vamos a exponer una objeción que podría hacerse a lo expuesto hasta el momento.
Hemos supuesto que Teseo (nombre que siempre daremos a quien intenta resolver el laberinto) no tiene ninguna percepción más allá del nodo en el que se encuentra parado. Esta percepción limitada sumada a la memoria de los nodos y los ejes que ya ha recorrido es toda la información que tiene Teseo en cualquier momento de su periplo.
Ahora bien, pensemos en laberintos virtuales, por ejemplo en el grafo resultante de un problema de movimientos de fichas. Es frecuente que quien resuelve esta clase de problemas pueda ver (como un ajedrecista) dos, tres o más jugadas por delante de la situación en que se encuentre. En ese caso, diría la objeción, la visión tan limitada que le hemos atribuido a Teseo no refleja la realidad.
La respuesta a la objeción es simple: así como le hemos atribuido a Teseo una visión limitada, con la misma facilidad podemos atribuirle una visión más amplia. Podemos suponer, por ejemplo, que Teseo ve todos los nodos a dos o tres (o la cantidad que se desee) pasos de distancia de aquél nodo en el que se encuentre. La visión que se le atribuya a Teseo, de hecho, puede hacerse depender de la situación real que el grafo esté modelando. El método que expondremos para medir la dificultad de un laberinto resiste perfectamente estas modificaciones.
(A la parte 4 - A la parte 6)
Una objeción
Vamos a exponer una objeción que podría hacerse a lo expuesto hasta el momento.
Hemos supuesto que Teseo (nombre que siempre daremos a quien intenta resolver el laberinto) no tiene ninguna percepción más allá del nodo en el que se encuentra parado. Esta percepción limitada sumada a la memoria de los nodos y los ejes que ya ha recorrido es toda la información que tiene Teseo en cualquier momento de su periplo.
Ahora bien, pensemos en laberintos virtuales, por ejemplo en el grafo resultante de un problema de movimientos de fichas. Es frecuente que quien resuelve esta clase de problemas pueda ver (como un ajedrecista) dos, tres o más jugadas por delante de la situación en que se encuentre. En ese caso, diría la objeción, la visión tan limitada que le hemos atribuido a Teseo no refleja la realidad.
La respuesta a la objeción es simple: así como le hemos atribuido a Teseo una visión limitada, con la misma facilidad podemos atribuirle una visión más amplia. Podemos suponer, por ejemplo, que Teseo ve todos los nodos a dos o tres (o la cantidad que se desee) pasos de distancia de aquél nodo en el que se encuentre. La visión que se le atribuya a Teseo, de hecho, puede hacerse depender de la situación real que el grafo esté modelando. El método que expondremos para medir la dificultad de un laberinto resiste perfectamente estas modificaciones.
(A la parte 4 - A la parte 6)
5.3.07
Laberintos (Parte 4)
(A la parte 3 - A la parte 5)
Laberintos físicos y laberintos virtuales
Existen laberintos físicos, pero también existen laberintos virtuales que recorremos con más frecuencia de la que creemos. Por ejemplo, la resolución de muchos problemas de ingenio equivale a recorrer un grafo. Pensemos en un solitario de fichas, es decir un tipo de problema de ingenio en el que se pide llevar fichas desde cierta configuración inicial hasta otra configuración final siguiendo en el proceso determinadas reglas específicas (véase aquí un ejemplo). Resolver un problema de esta clase equivale a recorrer un grafo o un laberinto, en este grafo cada nodo representa una configuración posible de las fichas, la entrada es la configuración inicial, la salida es la configuración final buscada y dos nodos están conectados si y sólo si es posible pasar de la configuración representada por uno de ellos a la configuración del otro en un único movimiento (1).
Otro ejemplo estaría dado por el tan popular Sudoku. Resolver uno de estos problemas equivale a recorrer un grafo en el que la entrada es el enunciado del problema y la salida es la solución buscada. Por lo tanto nuestra teoría para medir la dificultad de un laberinto permitirá al mismo tiempo medir la dificultad de un problema, al menos, la dificultad de ciertos problemas de ingenio.
Una observación sobre laberintos físicos: Observemos el siguiente grafo e imaginemos que representa un laberinto físico (recuérdese que el nodo rojo es la entrada y el verde es la salida):
Algunos ejes se cortan en puntos que no son nodos, por lo tanto en esos puntos Teseo no puede cambiar de dirección. Para entender físicamente esos cruces debemos imaginar que en esos puntos que no son nodos los caminos no se cortan realmente, sino que uno pasa por encima del otro:
Nota:
(1) Debo hacer aquí dos aclaraciones importantes. Muchas veces los problemas de movimientos de fichas piden hallar el camino más corto que vaya de la configuración inicial a la final. La teoría que expondremos permitirá medir la dificultad de hallar algún camino, pero no la dificultad de hallar el más corto. Por otra parte, en alguno de estos problemas puede suceder que el hecho de que sea posible pasar de la configuración A a la B, pero no de la B a la A. En ese caso, el problema quedaría representado por un grafo dirigido, es decir un grafo en el que los ejes tienen un sentido permitido de tránsito. Nuestra teoría de medición de dificultad será enunciada para grafos no dirigidos, pero podría extenderse sin dificultad a grafos dirigidos.
A la parte 3 - A la parte 5)
Laberintos físicos y laberintos virtuales
Existen laberintos físicos, pero también existen laberintos virtuales que recorremos con más frecuencia de la que creemos. Por ejemplo, la resolución de muchos problemas de ingenio equivale a recorrer un grafo. Pensemos en un solitario de fichas, es decir un tipo de problema de ingenio en el que se pide llevar fichas desde cierta configuración inicial hasta otra configuración final siguiendo en el proceso determinadas reglas específicas (véase aquí un ejemplo). Resolver un problema de esta clase equivale a recorrer un grafo o un laberinto, en este grafo cada nodo representa una configuración posible de las fichas, la entrada es la configuración inicial, la salida es la configuración final buscada y dos nodos están conectados si y sólo si es posible pasar de la configuración representada por uno de ellos a la configuración del otro en un único movimiento (1).
Otro ejemplo estaría dado por el tan popular Sudoku. Resolver uno de estos problemas equivale a recorrer un grafo en el que la entrada es el enunciado del problema y la salida es la solución buscada. Por lo tanto nuestra teoría para medir la dificultad de un laberinto permitirá al mismo tiempo medir la dificultad de un problema, al menos, la dificultad de ciertos problemas de ingenio.
Una observación sobre laberintos físicos: Observemos el siguiente grafo e imaginemos que representa un laberinto físico (recuérdese que el nodo rojo es la entrada y el verde es la salida):
Algunos ejes se cortan en puntos que no son nodos, por lo tanto en esos puntos Teseo no puede cambiar de dirección. Para entender físicamente esos cruces debemos imaginar que en esos puntos que no son nodos los caminos no se cortan realmente, sino que uno pasa por encima del otro:Nota:(1) Debo hacer aquí dos aclaraciones importantes. Muchas veces los problemas de movimientos de fichas piden hallar el camino más corto que vaya de la configuración inicial a la final. La teoría que expondremos permitirá medir la dificultad de hallar algún camino, pero no la dificultad de hallar el más corto. Por otra parte, en alguno de estos problemas puede suceder que el hecho de que sea posible pasar de la configuración A a la B, pero no de la B a la A. En ese caso, el problema quedaría representado por un grafo dirigido, es decir un grafo en el que los ejes tienen un sentido permitido de tránsito. Nuestra teoría de medición de dificultad será enunciada para grafos no dirigidos, pero podría extenderse sin dificultad a grafos dirigidos.
A la parte 3 - A la parte 5)
Suscribirse a:
Entradas (Atom)