Siguiente: Minimización de autómatas Un nivel arriba: Expresiones regulares y sistemas Anterior: El mundo de los

PB visto como un AF

Sea n > 1. Sea $\left(e_k\right)_{0\leq k\leq a_n-1}$ el conjunto de estados correspondientes al PB con n bloques, $\mbox{\rm PB}_n$. Según vimos anteriormente $a_n=\sum_{k=0}^{n-1}k!{n-1\choose k}{n\choose k}$. $\forall i \in \mbox{\bf n}\forall j \in \mbox{\bf n+1}-\{ i\}$ codificaremos a la instrucción ``Colóquese el bloque i sobre el objeto j'' mediante un símbolo especial m_ij. Claramente, un tal símbolo m_ij sólo podrá aplicarse a un estado e_k cuando en este estado ni i ni j tienen un bloque encima, a menos que j = 0, es decir, que el objeto j sea precisamente el piso. Introduzcamos entonces un estado más, e_an, de inconsistencia. Sea pues $E=\left(e_k\right)_{0\leq k\leq a_n}$ el conjunto de estados y sea $M=\left(m_{ij}\right)_{ij\in\mbox{\bf n}\times\mbox{\bf n+1}}$ el conjunto de símbolos del autómata correspondiente al $\mbox{\rm PB}_n$. Las transiciones en él, estarán dadas por la función $T : E \times M \rightarrow E$ tal que $\forall (e_k, m_{ij}) \in E \times M$, T(e_k, m_ij) es bien el estado de inconsistencia e_an, en el caso que m_ij no pueda aplicarse a e_k, o bien es el estado que difiere de e_k tan sólo por la aplicación del movimiento m_ij a e_k, cuando ésta es posible. A guisa de ejemplos, en las tablas 4.4 y 4.5 mostramos las tablas de transición de los autómatas correspondientes a 2 y 3 bloques respectivamente.

  

Table 4.4: Matriz de transición del autómata correspondiente a 2 bloques.

  

Table 4.5: Matriz de transición del autómata correspondiente a 3 bloques.

Ahora, para el (semi-)autómata $\mbox{\it AF\/}_n=(E_n,M_n,T_n)$ correspondiente a $\mbox{\it PB\/}_n$ consideremos la matriz $\mbox{\bf A}_n\in \mbox{\it ER\/}(M_n)^{E_n\times E_n}$ tal que $\forall i,j\leq a_n$:

$$a_{ij}=\sum\{m\in M_n\vert T_n(e_i,m)=e_j\}.$$

Para dos bloques, se tiene

$$\mbox{\bf A}_2=\left[\begin{array}{cccl} m_{20} + m_{10}& m_... ... 0& 0& 0& m_{20} + m_{10} + m_{12} + m_{21} \end{array}\right]$$

Para dos bloques, se tiene la matriz de la tabla 4.6.

  

Table 4.6: Matriz de coeficientes del sistema de derivadas.

Para $\mbox{\bf A}_2$ se puede calcular su potencia ``estrella'' por el algoritmo descrito anteriormente. Se obtiene que

$$\mbox{\bf A}_2^*=\left[\begin{array}{llll} b_{11} & b_{12} &... ...34} \\ b_{41} & b_{42} & b_{43} & b_{44} \end{array}\right]$$

donde

$$\begin{eqnarray*}b_{11} &=& \left(\left(\left(m_{20} + m_{10}\right)^* m_{12} m_... ...\ b_{44} &=& \left(m_{20} + m_{10} + m_{12} + m_{21}\right)^* \end{eqnarray*}$$

Hemos visto que en teoría es posible utilizar los algoritmos presentados, relativos a los autómatas finitos, para encontrar a todos los posibles planes para pasar de un estado a otro en el Mundo de los Bloques y resolver así cualquier instancia del PB. En la práctica, hemos visto que, incluso para el caso trivial de sólo dos bloques, la solución con este enfoque es difícil. De hecho, la complejidad de este algoritmo crece notablemente, en tiempo y en espacio, con el número n de bloques considerados.
Siguiente: Minimización de autómatas Un nivel arriba: Expresiones regulares y sistemas Anterior: El mundo de los