Que tipo de problemas são máquinas de estado é bom?[fechado]

https://stackoverflow.com/questions/40602

09-06-2019
|

Pergunta

Que tipo de problemas de programação são máquinas de estado mais adequada?

Eu li sobre analisadores sendo implementado utilizando máquinas de estado, mas gostaria de saber sobre problemas que gritar para ser implementada como uma máquina de estado.

Solução

A resposta mais fácil é que, provavelmente, eles são adequados para praticamente qualquer problema.Não se esqueça de que um computador em si é também uma máquina de estado.

Independentemente do que máquinas de estado são normalmente utilizados para problemas onde há alguns fluxo de entrada e a atividade que precisa ser feito em um determinado momento depende a última elementos vistos na sequência em que ponto.

Exemplos desta corrente de entrada:algumas arquivo de texto, no caso de análise, uma seqüência de expressões regulares, eventos como player entered room para o jogo, AI, etc.

Exemplos de atividades:estar pronto para ler um número após número, seguido por um + ter aparecem na entrada em um analisador para uma calculadora), voltar-se (após o jogador se aproximou e, em seguida, espirrar), realizar pontapé de salto (depois do jogador pressionado esquerda, esquerda, direita, em cima, em cima).

Outras dicas

Um bom recurso é free Máquina De Estado EBook.A minha própria resposta rápida está abaixo.

Quando sua lógica deve conter informações sobre o que aconteceu a última vez que ele foi executado, ele deve conter estado.

Assim, uma máquina de estado é simplesmente qualquer código que se lembra (ou actos) de informações que só pode ser adquirida através da compreensão do que aconteceu antes.

Por exemplo, eu tenho um modem celular que o meu programa deve usar.Ele deve realizar os seguintes passos:

repor o modem
iniciar uma comunicação com o modem
aguarde a força do sinal para indicar uma boa conexão com uma torre
...

Agora eu poderia bloquear o programa principal e simplesmente passar por todas estas etapas em ordem, esperando por cada um para executar, mas eu quero dar o meu feedback do usuário e executar outras operações ao mesmo tempo.Então eu implementar isso como uma máquina de estado dentro de uma função, e executar esta a funcionar a 100 vezes 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
}

Mais complexas máquinas de estado implementar protocolos.Por exemplo, uma ECU de diagnóstico de protocolo utilizado pode enviar apenas 8 bytes de pacotes, mas às vezes eu preciso enviar maiores pacotes.A ECU é lento, então eu preciso esperar por uma resposta.Idealmente, quando eu enviar uma mensagem eu uso uma função e, em seguida, eu não me importo com o que acontece, mas em algum lugar o meu programa deve acompanhar a linha e enviar e responder a essas mensagens, quebrando-os em pedaços menores e remontar as peças de mensagens recebidas no final da mensagem.

Monitorador de protocolos como o TCP são muitas vezes representados como máquinas de estado.No entanto, é raro que você deve querer implementar qualquer coisa como uma máquina de estado adequado.Geralmente, você irá usar uma corrupção de um, i.é.tê-lo a realizar uma ação repetida ao sentar-se em um estado, log de dados, sem transições, ou a troca de dados, permanecendo em um estado.

Fluxo de trabalho (ver WF in .net 3.0)

Eles têm muitos usos, analisadores de ser uma notável.Eu pessoalmente tenho usado simplificado de máquinas de estado para implementar o complexo multi-passo tarefa de caixas de diálogo em aplicações.

Um analisador exemplo.Recentemente escrevi um analisador que leva uma sequência binária a partir de outro programa.O significado do elemento atual analisado indica o tamanho/significado dos próximos elementos.Há um pequeno número finito de elementos possível.Portanto, uma máquina de estado.

Eles são ótimos para a modelação de coisas que mudam de estado, e ter uma lógica que desencadeia em cada transição.

Eu gostaria de usar máquinas de estado finito para o rastreamento de pacotes pelo correio, ou para manter o controle das diferentes stata de um usuário durante o processo de registro, por exemplo.

Como o número de possíveis valores de status sobe, o número de transições explode.Máquinas de estado ajudar muito nesse caso.

Objetos em jogos são muitas vezes representados como máquinas de estado.Um personagem AI pode ser:

Guarda
Agressivo
Patroling
Dormindo

Assim você pode ver esses podem modelo simples mas eficaz estados.É claro que você provavelmente poderia fazer um mais complexo sistema contínuo.

Outro exemplo seria o de um processo de como fazer uma compra no Google Checkout.Google dá um número de estados Financeiros e da Ordem, e, em seguida, informa-o de transistions, tais como o cartão de crédito de compensação ou ficando rejeitada, e permite que você para informá-lo de que a ordem foi enviada.

Expressão Regular de correspondência, Análise de Fluxo de controle em um sistema complexo.

Expressões regulares são uma forma simples de máquina de estado, especificamente autómatos finitos.Eles têm uma natural represenation como tal, embora seja possível implementá-los utilizando mutuamente funções recursivas.

Máquinas de estado, quando bem aplicado, será muito eficiente.

Há um excelente máquina de estado compilador para um número de línguas-alvo, se você quiser fazer uma legíveis por máquina do estado.

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

Ele também permite que você para evitar o temido 'goto'.

IA em jogos é muito frequentemente implementados utilizando Máquinas de Estado.Ajuda a criar a lógica discreta que é muito mais fácil para criar e testar.

Coisas que vem à mente são:

Robot/Máquina de manipulação de...aqueles robô braços em fábricas

Jogos de simulação, (SimCity, Jogo de Corrida, etc..)

Generalizando:Quando você tem uma seqüência de entradas, que ao interagir com qualquer um deles, requer o conhecimento do anterior entradas ou, em outras palavras, quando o processamento de uma única entrada requer o conhecimento dos factores de produção.(isto é, ele precisa ter "estados")

Não há muito que eu sei que não é redutível a um problema de análise embora.

Como uma nota lateral, você pode implementar máquinas de estado com a devida cauda de chamadas, como já explicado no recursão questão.

Neste exemplo cada quarto no jogo é considerado um estado.

Além disso, o projeto de Hardware com VHDL (e outros lógica síntese de línguas) utiliza máquinas de estado em todos os lugares para descrever o hardware.

Se você precisa de um simples processo estocástico, você pode usar uma cadeia de Markov, que pode ser representado como uma máquina de estado (dado o estado atual, no passo seguinte, a cadeia vai ser no estado X, com uma certa probabilidade).

Qualquer aplicativo de fluxo de trabalho, especialmente com as atividades assíncronas.Você tem um item no fluxo de trabalho em um determinado estado, e o estado da máquina sabe como reagir a eventos externos, colocando o item em um estado diferente, no ponto em que alguma outra atividade ocorre.

O conceito de estado é muito útil para aplicativos para "lembrar" o contexto atual de seu sistema e reagir adequadamente quando uma nova informação chega.Qualquer não trivial aplicativo tem a noção incorporados no código através de variáveis e condicionais.

Então, se o seu aplicativo tem a reagir de forma diferente a cada vez que ele recebe um novo pedaço de informação por causa do contexto em que está, você pode modelar o sistema com máquinas de estado.Um exemplo seria como interpretar as teclas de uma calculadora, que depende de qual o seu processamento naquele ponto no tempo.

Pelo contrário, se o cálculo não dependem do contexto, mas unicamente na entrada (como uma função da adição de dois números), você não precisa de uma máquina de estado (ou melhor dizendo, você vai ter uma máquina de estado, com zero de estados)

Algumas pessoas projetar toda a aplicação, em termos de máquinas de estado desde que captura as coisas essenciais a ter em consideração em seu projeto e, em seguida, usar algum procedimento ou autocoders para torná-los executáveis.Leva algum paradigma chance para o programa dessa maneira, mas eu achei ele muito eficaz.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow