algorithm - proyectos - maquinas secuenciales
¿Para qué tipo de problemas son buenas las máquinas de estado? (15)
Cualquier aplicación de flujo de trabajo, especialmente con actividades asincrónicas. Tiene un elemento en el flujo de trabajo en un estado determinado, y la máquina de estados sabe cómo reaccionar ante eventos externos colocando el elemento en un estado diferente, en cuyo punto se produce alguna otra actividad.
¿Para qué tipo de problemas de programación son más adecuadas las máquinas de estado?
He leído acerca de los analizadores que se implementan usando máquinas de estado, pero me gustaría saber qué problemas surgen como una máquina de estado.
El concepto de estado es muy útil para que las aplicaciones "recuerden" el contexto actual de su sistema y reaccionen adecuadamente cuando llega una nueva información. Cualquier aplicación no trivial tiene esa noción incrustada en el código a través de variables y condicionales.
Entonces, si su aplicación tiene que reaccionar de manera diferente cada vez que recibe una nueva información debido al contexto en el que se encuentra, puede modelar su sistema con una máquina de estado. Un ejemplo sería cómo interpretar las claves en una calculadora, que depende de lo que esté procesando en ese momento.
Por el contrario, si su computación no depende del contexto sino únicamente de la entrada (como una función que agrega dos números), no necesitará una máquina de estados (o mejor dicho, tendrá una máquina de estados con estados cero)
Algunas personas diseñan la aplicación completa en términos de máquinas de estado, ya que capturan las cosas esenciales que deben tenerse en cuenta en su proyecto y luego usan algún procedimiento o autocodificadores para que sean ejecutables. Toma algunas oportunidades de paradigma programar de esta manera, pero lo encontré muy efectivo.
Flujo de trabajo (vea WF en .net 3.0)
Igualación de expresiones regulares, Análisis, Control de flujo en un sistema complejo.
Las expresiones regulares son una forma simple de máquina de estados, específicamente autómatas finitos. Tienen una representación natural como tal, aunque es posible implementarlos utilizando funciones mutuamente recursivas.
Las máquinas de estado cuando se implementan bien, serán muy eficientes.
Existe un compilador de máquina de estado excelente para varios idiomas de destino, si desea crear una máquina de estado legible.
http://research.cs.queensu.ca/~thurston/ragel/
También le permite evitar el temido ''goto''.
La IA en los juegos se implementa a menudo usando máquinas estatales. Ayuda a crear lógica discreta que es mucho más fácil de construir y probar.
La respuesta más fácil es, probablemente, que son adecuados para prácticamente cualquier problema. No olvide que una computadora en sí misma también es una máquina de estado.
A pesar de eso, las máquinas de estado se usan generalmente para problemas donde hay un flujo de entrada y la actividad que se debe realizar en un momento dado depende de los últimos elementos que se ven en esa secuencia en ese punto.
Ejemplos de esta secuencia de entrada: algún archivo de texto en el caso del análisis sintáctico, una cadena para expresiones regulares, eventos como el player entered room para juego AI, etc.
Ejemplos de actividades: prepárese para leer un número (después de otro número seguido de un + en la entrada de un analizador), gírelo (después de que el jugador se acercó y luego estornudó), realice una patada de salto (después de presionar el botón hacia la izquierda) , izquierda, derecha, arriba, arriba).
Las cosas que viene a la mente son:
- Robot / manipulación de la máquina ... esos brazos robóticos en las fábricas
- Juegos de simulación, (SimCity, Racing Game, etc.)
Generalización: cuando tiene una cadena de entradas que al interactuar con cualquiera de ellas, requiere el conocimiento de las entradas anteriores o, en otras palabras, cuando el procesamiento de cualquier entrada individual requiere el conocimiento de las entradas anteriores. (es decir, necesita tener "estados")
Sin embargo, no mucho de lo que sé no es reductible a un problema de análisis sintáctico.
Los objetos en los juegos a menudo se representan como máquinas de estado. Un personaje de IA podría ser:
- Vigilancia
- Agresivo
- Patroling
- Dormido
Entonces puede ver que estos podrían modelar algunos estados simples pero efectivos. Por supuesto, probablemente puedas hacer un sistema continuo más complejo.
Otro ejemplo sería un proceso como hacer una compra en Google Checkout. Google otorga varios estados para Finanzas y pedidos, y luego le informa sobre transiciones tales como el retiro de la tarjeta de crédito o el rechazo, y le permite informarle que el pedido ha sido enviado.
Los protocolos de estado como TCP a menudo se representan como máquinas de estado. Sin embargo, es raro que desee implementar algo como una máquina de estado propiamente dicha. Por lo general, utilizará una corrupción de uno, es decir, tendrá que realizar una acción repetida mientras está sentado en un estado, registrando datos mientras transiciones o intercambiando datos mientras permanece en un estado.
Si necesita un proceso estocástico simple, puede usar una cadena de Markov, que puede representarse como una máquina de estado (dado el estado actual, en el siguiente paso la cadena estará en el estado X con una cierta probabilidad).
Solo como una nota al margen, puede implementar máquinas de estado con llamadas de cola adecuadas, como expliqué en la pregunta de recursividad de cola .
En ese ejemplo, cada habitación del juego se considera un estado.
Además, el diseño de hardware con VHDL (y otros lenguajes lógicos de síntesis) utiliza máquinas de estado en todas partes para describir el hardware.
Son geniales para modelar cosas que cambian de estado y tienen lógica que se dispara en cada transición.
Utilizaría máquinas de estados finitos para rastrear paquetes por correo, o para realizar un seguimiento de las diferentes etapas de un usuario durante el proceso de registro, por ejemplo.
A medida que aumenta el número de posibles valores de estado, el número de transiciones explota. Las máquinas de estado ayudan mucho en ese caso.
Tienen muchos usos, siendo los analizadores sintácticos uno notable. Personalmente, he usado máquinas de estado simplificadas para implementar diálogos complejos de tareas de pasos múltiples en las aplicaciones.
Un buen recurso es este State EBook de máquina gratis. Mi propia respuesta rápida está debajo.
Cuando su lógica debe contener información sobre lo que sucedió la última vez que se ejecutó, debe contener el estado.
Entonces, una máquina de estado es simplemente cualquier código que recuerda (o actúa sobre) información que solo puede obtenerse al comprender lo que sucedió antes.
Por ejemplo, tengo un módem celular que mi programa debe usar. Tiene que realizar los siguientes pasos en orden:
- restablecer el módem
- iniciar las comunicaciones con el módem
- espere la intensidad de la señal para indicar una buena conexión con una torre
- ...
Ahora podría bloquear el programa principal y simplemente seguir todos estos pasos en orden, esperando que cada uno se ejecute, pero quiero dar mi opinión al usuario y realizar otras operaciones al mismo tiempo. Así que implemento esto como una máquina de estado dentro de una función, y ejecuto esta función 100 veces por segundo.
enum states{reset,initsend, initresponse, waitonsignal,dial,ppp,...}
modemfunction()
{
static currentstate
switch(currentstate)
{
case reset:
Do reset
if reset was successful, nextstate=init else nextstate = reset
break
case initsend
send "ATD"
nextstate = initresponse
break
...
}
currentstate=nextstate
}
Las máquinas de estado más complejas implementan protocolos. Por ejemplo, un protocolo de diagnóstico de la ECU que utilicé solo puede enviar paquetes de 8 bytes, pero a veces necesito enviar paquetes más grandes. La ECU es lenta, así que tengo que esperar una respuesta. Idealmente, cuando envío un mensaje, uso una función y luego no me importa lo que suceda, pero en algún lugar mi programa debe monitorear la línea y enviar y responder a estos mensajes, dividiéndolos en partes más pequeñas y volviendo a ensamblar las piezas de los mensajes recibidos. el mensaje final.
Un ejemplo de analizador Recientemente escribí un analizador sintáctico que toma un flujo binario de otro programa. El significado del elemento actual analizado indica el tamaño / significado de los siguientes elementos. Hay un número (pequeño) de elementos finitos posible. De ahí una máquina de estado.