next up previous contents
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 mij. Claramente, un tal símbolo mij sólo podrá aplicarse a un estado ek 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, ean, 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(ek, mij) es bien el estado de inconsistencia ean, en el caso que mij no pueda aplicarse a ek, o bien es el estado que difiere de ek tan sólo por la aplicación del movimiento mij a ek, cuando ésta es posible. A guisa de ejemplos, en las tablas 4.44.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.
\begin{table}\begin{displaymath}\begin{array}{\vert\vert c\vert cccc\vert\vert}\...
...3} & e_{3} & e_{3} \\ \hline\hline
\end{array}\end{displaymath}
\end{table}


  
Table 4.5: Matriz de transición del autómata correspondiente a 3 bloques.
\begin{table}\begin{displaymath}\begin{array}{\vert\vert c\vert ccccccccc\vert\v...
... & e_{13} & e_{13} \\ \hline\hline
\end{array}\end{displaymath}
\end{table}

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$:

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

Para dos bloques, se tiene

\begin{displaymath}\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]\end{displaymath}

Para dos bloques, se tiene la matriz de la tabla 4.6.
  
Table 4.6: Matriz de coeficientes del sistema de derivadas.
\begin{table}\begin{displaymath}\mbox{\bf A}_3=\left[\mbox{\bf A}_{31}\; \mbox{\...
...{23}+m_{30}+m_{31}+m_{32}
\end{array}\right]
\end{eqnarray*}}
\end{table}

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

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

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.
next up previous contents
Siguiente: Minimización de autómatas Un nivel arriba: Expresiones regulares y sistemas Anterior: El mundo de los
Guillermo Morales-Luna
2000-06-27