¿Para qué tipo de problemas sirven las máquinas de estados?[cerrado]

Question

¿Para qué tipo de problemas de programación son más adecuadas las máquinas de estados?

He leído sobre analizadores que se implementan utilizando máquinas de estado, pero me gustaría conocer los problemas que exigen ser implementados como una máquina de estado.

Answer 1

Probablemente la respuesta más sencilla sea que sirven para prácticamente cualquier problema.No olvide que una computadora en sí misma también es una máquina de estados.

Independientemente de eso, las máquinas de estados se usan típicamente para problemas en los que hay algún flujo de entrada y la actividad que debe realizarse en un momento dado depende de los últimos elementos vistos en ese flujo en ese punto.

Ejemplos de este flujo de entrada:algún archivo de texto en el caso del análisis, una cadena para expresiones regulares, eventos como player entered room para juegos de IA, etc.

Ejemplos de actividades:Esté preparado para leer un número (después de otro número seguido de un + han aparecido en la entrada de un analizador de una calculadora), darse la vuelta (después de que el jugador se acercó y luego estornudó), realizar una patada con salto (después de que el jugador presionó izquierda, izquierda, derecha, arriba, arriba).

Answer 2

Un buen recurso es este gratis. Libro electrónico sobre la máquina de estados.Mi propia respuesta rápida está a continuación.

Cuando su lógica debe contener información sobre lo que sucedió la última vez que se ejecutó, debe contener estado.

Entonces, una máquina de estados es simplemente cualquier código que recuerda (o actúa sobre) información que sólo puede obtenerse entendiendo lo que sucedió antes.

Por ejemplo, tengo un módem celular que mi programa debe usar.Tiene que realizar los siguientes pasos en orden:

1. restablecer el módem
2. iniciar comunicaciones con el módem
3. espere a que la intensidad de la señal indique una buena conexión con una torre
4. ...

Ahora podría bloquear el programa principal y simplemente seguir todos estos pasos en orden, esperando a que se ejecute cada uno, pero quiero brindarle comentarios a mi usuario y realizar otras operaciones al mismo tiempo.Entonces implemento esto como una máquina de estados 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 estados más complejas implementan protocolos.Por ejemplo, un protocolo de diagnóstico de la ECU que utilicé sólo puede enviar paquetes de 8 bytes, pero a veces necesito enviar paquetes más grandes.La ECU es lenta, así que necesito 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 partes de los mensajes recibidos en el mensaje final.

Answer 3

Los protocolos con estado como TCP suelen representarse como máquinas de estado.Sin embargo, es raro que desee implementar algo como una máquina de estados propiamente dicha.Por lo general, utilizará una corrupción de uno, es decir.haga que realice una acción repetida mientras se encuentra en un estado, registre datos mientras realiza la transición o intercambie datos mientras permanece en un estado.

Answer 4

Flujo de trabajo (ver WF en .net 3.0)

Answer 5

Tienen muchos usos, siendo los analizadores uno notable.Personalmente he utilizado máquinas de estado simplificadas para implementar diálogos de tareas complejos de varios pasos en aplicaciones.

Answer 6

Un ejemplo de analizador.Recientemente escribí un analizador 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 (pequeño) número finito de elementos posibles.De ahí una máquina de estados.

Answer 7

Son excelentes para modelar cosas que cambian de estado y tienen una lógica que se activa en cada transición.

Usaría máquinas de estados finitos para rastrear paquetes por correo o para realizar un seguimiento de los diferentes estados de un usuario durante el proceso de registro, por ejemplo.

A medida que aumenta el número de valores de estado posibles, el número de transiciones se dispara.Las máquinas de estados ayudan mucho en ese caso.

Answer 8

Los objetos de los juegos suelen representarse como máquinas de estados.Un personaje de IA podría ser:

• custodiando
• Agresivo
• patrullando
• Dormido

Como puedes ver, estos podrían modelar algunos estados simples pero efectivos.Por supuesto, probablemente podrías crear un sistema continuo más complejo.

Otro ejemplo sería un proceso como realizar una compra en Google Checkout.Google proporciona una serie de estados para Finanzas y Pedidos, y luego le informa sobre transiciones como la compensación de la tarjeta de crédito o el rechazo, y le permite informarle que el pedido ha sido enviado.

Answer 9

Coincidencia 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 implementarlas utilizando funciones mutuamente recursivas.

Las máquinas de estados, cuando se implementan bien, serán muy eficientes.

Existe un excelente compilador de máquinas de estados para varios idiomas de destino, si desea crear una máquina de estados legible.

http://research.cs.queensu.ca/~thurston/ragel/

También te permite evitar el temido 'goto'.

Answer 10

La IA en los juegos se implementa muy a menudo mediante máquinas de estados.Ayuda a crear una lógica discreta que es mucho más fácil de construir y probar.

Answer 11

Las cosas que me vienen a la mente son:

• Manipulación de robots/máquinas...Esos brazos robóticos en las fábricas.
• Juegos de simulación (SimCity, juegos de carreras, etc.)

Generalizando:Cuando se 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 única requiere el conocimiento de las entradas anteriores.(es decir, necesita tener "estados")

Sin embargo, no hay mucho que yo sepa que no se pueda reducir a un problema de análisis.

Answer 12

Solo como nota al margen, puede implementar máquinas de estado con llamadas de cola adecuadas como lo expliqué en el recursión de cola pregunta.

En ese ejemplo, cada habitación del juego se considera un estado.

Además, el diseño de hardware con VHDL (y otros lenguajes de síntesis lógica) utiliza máquinas de estado en todas partes para describir el hardware.

Answer 13

Si necesita un proceso estocástico simple, puede usar una cadena de Markov, que puede representarse como una máquina de estados (dado el estado actual, en el siguiente paso la cadena estará en el estado X con una cierta probabilidad).

Answer 14

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 estado sabe cómo reaccionar ante eventos externos colocando el elemento en un estado diferente, momento en el cual ocurre alguna otra actividad.

Answer 15

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 incorporada 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, podría modelar su sistema con máquinas de estado.Un ejemplo sería cómo interpretar las teclas de una calculadora, lo que depende de lo que esté procesando en ese momento.

Por el contrario, si tu cálculo no depende del contexto sino únicamente de la entrada (como una función que suma dos números), no necesitarás una máquina de estados (o mejor dicho, tendrás una máquina de estados con cero estados)

Algunas personas diseñan toda la aplicación en términos de máquinas de estado, ya que capturan los aspectos esenciales a tener en cuenta en su proyecto y luego utilizan algún procedimiento o codificadores automáticos para hacerlos ejecutables.Se necesita cierta oportunidad paradigmática para programar de esta manera, pero lo encontré muy efectivo.