A che tipo di problemi servono le macchine a stati?[Chiuso]

Question

Per quali tipi di problemi di programmazione sono più adatte le macchine a stati?

Ho letto di parser implementati utilizzando macchine a stati, ma vorrei scoprire problemi che richiedono a gran voce di essere implementati come macchine a stati.

Answer 1

La risposta più semplice è probabilmente che sono adatti praticamente a qualsiasi problema.Non dimenticare che anche il computer stesso è una macchina statale.

Indipendentemente da ciò, le macchine a stati vengono generalmente utilizzate per problemi in cui è presente un flusso di input e l'attività che deve essere eseguita in un dato momento dipende dagli ultimi elementi visti in quel flusso in quel punto.

Esempi di questo flusso di input:alcuni file di testo in caso di analisi, una stringa per espressioni regolari, eventi come player entered room per l'intelligenza artificiale del gioco, ecc.

Esempi di attività:essere pronti a leggere un numero (dopo un altro numero seguito da a + sono apparsi nell'input in un parser per una calcolatrice), girarsi (dopo che il giocatore si è avvicinato e poi ha starnutito), eseguire un calcio in salto (dopo che il giocatore ha premuto sinistra, sinistra, destra, su, su).

Answer 2

Una buona risorsa è questa gratuita E-Book La macchina degli stati.La mia risposta rapida è qui sotto.

Quando la logica deve contenere informazioni su ciò che è accaduto l'ultima volta che è stata eseguita, deve contenere lo stato.

Quindi una macchina a stati è semplicemente qualsiasi codice che ricorda (o agisce su) informazioni che possono essere ottenute solo comprendendo cosa è successo prima.

Ad esempio, ho un modem cellulare che il mio programma deve utilizzare.Deve eseguire i seguenti passaggi in ordine:

1. reimpostare il modem
2. avviare la comunicazione con il modem
3. attendere che la potenza del segnale indichi una buona connessione con una torre
4. ...

Ora posso bloccare il programma principale ed eseguire semplicemente tutti questi passaggi in ordine, aspettando che ciascuno venga eseguito, ma voglio fornire un feedback all'utente ed eseguire altre operazioni contemporaneamente.Quindi lo implemento come una macchina a stati all'interno di una funzione ed eseguo questa funzione 100 volte al secondo.

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
}

Le macchine a stati più complesse implementano protocolli.Ad esempio, il protocollo diagnostico ECU che ho utilizzato può inviare solo pacchetti da 8 byte, ma a volte devo inviare pacchetti più grandi.L'ECU è lenta, quindi devo aspettare una risposta.Idealmente quando invio un messaggio utilizzo una funzione e poi non mi interessa cosa succede, ma da qualche parte il mio programma deve monitorare la linea e inviare e rispondere a questi messaggi, suddividendoli in pezzi più piccoli e riassemblando i pezzi dei messaggi ricevuti in il messaggio finale.

Answer 3

I protocolli con stato come TCP sono spesso rappresentati come macchine a stati.Tuttavia è raro che tu voglia implementare qualcosa come una vera e propria macchina a stati.Di solito utilizzerai una corruzione di uno, ad es.fare in modo che esegua un'azione ripetuta mentre si trova in uno stato, registra dati durante la transizione o scambia dati rimanendo in uno stato.

Answer 4

Flusso di lavoro (vedi WF in .net 3.0)

Answer 5

Hanno molti usi, tra i quali i parser sono notevoli.Personalmente ho utilizzato macchine a stati semplificate per implementare complesse finestre di dialogo di attività in più fasi nelle applicazioni.

Answer 6

Un esempio di parser.Recentemente ho scritto un parser che prende un flusso binario da un altro programma.Il significato dell'elemento corrente analizzato indica la dimensione/significato degli elementi successivi.Ci sono un (piccolo) numero finito di elementi possibili.Quindi una macchina statale.

Answer 7

Sono ottimi per modellare cose che cambiano stato e hanno una logica che si attiva ad ogni transizione.

Utilizzerei macchine a stati finiti per tracciare i pacchi tramite posta o, ad esempio, per tenere traccia dei diversi stati di un utente durante il processo di registrazione.

All'aumentare del numero di possibili valori di stato, il numero di transizioni aumenta.Le macchine statali aiutano molto in questo caso.

Answer 8

Gli oggetti nei giochi sono spesso rappresentati come macchine a stati.Un personaggio AI potrebbe essere:

• Guardia
• Aggressivo
• Pattugliamento
• Addormentato

Quindi puoi vedere che questi potrebbero modellare alcuni stati semplici ma efficaci.Naturalmente probabilmente potresti creare un sistema continuo più complesso.

Un altro esempio potrebbe essere un processo come l'effettuazione di un acquisto su Google Checkout.Google fornisce una serie di stati per Finanziari e Ordine, quindi ti informa di transizioni come la compensazione della carta di credito o il rifiuto e ti consente di informarlo che l'ordine è stato spedito.

Answer 9

Corrispondenza di espressioni regolari, Parsing, Controllo di flusso in un sistema complesso.

Le espressioni regolari sono una forma semplice di macchina a stati, in particolare gli automi finiti.Hanno una rappresentazione naturale come tali, sebbene sia possibile implementarli utilizzando funzioni mutuamente ricorsive.

Le macchine a stati, se implementate bene, saranno molto efficienti.

Esiste un eccellente compilatore di macchine a stati per diversi linguaggi di destinazione, se si desidera creare una macchina a stati leggibile.

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

Permette anche di evitare il temuto "goto".

Answer 10

L'intelligenza artificiale nei giochi viene molto spesso implementata utilizzando macchine a stati.Aiuta a creare una logica discreta che è molto più semplice da costruire e testare.

Answer 11

Le cose che mi vengono in mente sono:

• Manipolazione di robot/macchine...quei bracci robotici nelle fabbriche
• Giochi di simulazione, (SimCity, giochi di corse ecc..)

Generalizzando:Quando si ha una stringa di input che, interagendo con qualcuno di essi, richiede la conoscenza degli input precedenti o in altre parole, quando l'elaborazione di ogni singolo input richiede la conoscenza degli input precedenti.(cioè deve avere "stati")

Tuttavia, non molto di quello che so non è riducibile a un problema di analisi.

Answer 12

Proprio come nota a margine, puoi implementare macchine a stati con chiamate di coda adeguate come ho spiegato nel ricorsione della coda domanda.

In questo esempio ogni stanza del gioco è considerata uno stato.

Inoltre, la progettazione hardware con VHDL (e altri linguaggi di sintesi logica) utilizza macchine a stati ovunque per descrivere l'hardware.

Answer 13

Se hai bisogno di un processo stocastico semplice, potresti utilizzare una catena di Markov, che può essere rappresentata come una macchina a stati (dato lo stato attuale, al passo successivo la catena sarà nello stato X con una certa probabilità).

Answer 14

Qualsiasi applicazione del flusso di lavoro, in particolare con attività asincrone.Hai un elemento nel flusso di lavoro in un determinato stato e la macchina a stati sa come reagire agli eventi esterni posizionando l'elemento in uno stato diverso, a quel punto si verifica un'altra attività.

Answer 15

Il concetto di stato è molto utile affinché le applicazioni "ricordino" il contesto corrente del sistema e reagiscano correttamente quando arriva una nuova informazione.Qualsiasi applicazione non banale ha questa nozione incorporata nel codice tramite variabili e condizionali.

Quindi, se la tua applicazione deve reagire in modo diverso ogni volta che riceve una nuova informazione a causa del contesto in cui ti trovi, potresti modellare il tuo sistema con una macchina a stati.Un esempio potrebbe essere come interpretare i tasti di una calcolatrice, che dipende da cosa stai elaborando in quel momento.

Al contrario, se il tuo calcolo non dipende dal contesto ma esclusivamente dall'input (come una funzione che somma due numeri), non avrai bisogno di una macchina a stati (o per meglio dire, avrai una macchina a stati con zero stati)

Alcune persone progettano l'intera applicazione in termini di macchine a stati poiché catturano le cose essenziali da tenere a mente nel progetto e quindi utilizzano alcune procedure o autocodificatori per renderle eseguibili.Ci vuole qualche possibilità paradigmatica per programmare in questo modo, ma l'ho trovato molto efficace.