Für welche Probleme sind Zustandsmaschinen gut?[geschlossen]

Question

Für welche Programmierprobleme eignen sich Zustandsmaschinen am besten?

Ich habe gelesen, dass Parser mithilfe von Zustandsautomaten implementiert werden, würde aber gerne mehr über Probleme erfahren, die nach einer Implementierung als Zustandsautomaten schreien.

Answer 1

Die einfachste Antwort ist wahrscheinlich, dass sie für praktisch jedes Problem geeignet sind.Vergessen Sie nicht, dass ein Computer selbst auch eine Zustandsmaschine ist.

Unabhängig davon werden Zustandsautomaten typischerweise für Probleme verwendet, bei denen es einen Eingabestrom gibt und die Aktivität, die zu einem bestimmten Zeitpunkt ausgeführt werden muss, von den letzten Elementen abhängt, die zu diesem Zeitpunkt in diesem Strom gesehen werden.

Beispiele für diesen Eingabestrom:eine Textdatei beim Parsen, eine Zeichenfolge für reguläre Ausdrücke, Ereignisse wie z player entered room für Spiel-KI usw.

Beispiele für Aktivitäten:Seien Sie bereit, eine Zahl zu lesen (nach einer anderen Zahl, gefolgt von einem + in der Eingabe in einem Parser für einen Taschenrechner auftauchen), sich umdrehen (nachdem der Spieler sich genähert und dann geniest hat), einen Sprungtritt ausführen (nachdem der Spieler links, links, rechts, oben, oben gedrückt hat).

Answer 2

Eine gute Ressource ist diese kostenlose E-Book „Zustandsmaschine“..Meine eigene schnelle Antwort ist unten.

Wenn Ihre Logik Informationen darüber enthalten muss, was bei der letzten Ausführung passiert ist, muss sie einen Status enthalten.

Eine Zustandsmaschine ist also einfach jeder Code, der sich Informationen merkt (oder darauf reagiert), die nur durch das Verständnis dessen, was zuvor passiert ist, gewonnen werden können.

Ich habe zum Beispiel ein Mobilfunkmodem, das mein Programm verwenden muss.Es müssen die folgenden Schritte der Reihe nach ausgeführt werden:

1. Setzen Sie das Modem zurück
2. initiieren Sie die Kommunikation mit dem Modem
3. Warten Sie, bis die Signalstärke eine gute Verbindung mit einem Turm anzeigt
4. ...

Jetzt könnte ich das Hauptprogramm blockieren und einfach alle diese Schritte der Reihe nach ausführen und darauf warten, dass sie ausgeführt werden. Ich möchte jedoch meinem Benutzer Feedback geben und gleichzeitig andere Vorgänge ausführen.Also implementiere ich dies als Zustandsmaschine innerhalb einer Funktion und führe diese Funktion 100 Mal pro Sekunde aus.

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
}

Komplexere Zustandsmaschinen implementieren Protokolle.Beispielsweise kann ein von mir verwendetes Steuergeräte-Diagnoseprotokoll nur 8-Byte-Pakete senden, aber manchmal muss ich größere Pakete senden.Das Steuergerät ist langsam, daher muss ich auf eine Antwort warten.Wenn ich eine Nachricht sende, verwende ich im Idealfall eine Funktion und dann ist es mir egal, was passiert, aber irgendwo muss mein Programm die Leitung überwachen und diese Nachrichten senden und darauf reagieren, sie in kleinere Teile aufteilen und die Teile der empfangenen Nachrichten wieder zusammensetzen die letzte Botschaft.

Answer 3

Zustandsbehaftete Protokolle wie TCP werden häufig als Zustandsmaschinen dargestellt.Es kommt jedoch selten vor, dass Sie etwas als eigentliche Zustandsmaschine implementieren möchten.Normalerweise verwenden Sie eine Verfälschung von eins, d. h.Lassen Sie es eine wiederholte Aktion ausführen, während es sich in einem Zustand befindet, Daten protokollieren, während es übergeht, oder Daten austauschen, während es in einem Zustand bleibt.

Answer 4

Workflow (siehe WF in .net 3.0)

Answer 5

Sie haben viele Einsatzmöglichkeiten, insbesondere Parser.Ich persönlich habe vereinfachte Zustandsmaschinen verwendet, um komplexe mehrstufige Aufgabendialoge in Anwendungen zu implementieren.

Answer 6

Ein Parser-Beispiel.Ich habe kürzlich einen Parser geschrieben, der einen Binärstream von einem anderen Programm übernimmt.Die Bedeutung des aktuell analysierten Elements gibt die Größe/Bedeutung der nächsten Elemente an.Es sind eine (kleine) endliche Anzahl möglicher Elemente möglich.Daher eine Zustandsmaschine.

Answer 7

Sie eignen sich hervorragend zum Modellieren von Dingen, die ihren Status ändern, und verfügen über eine Logik, die bei jedem Übergang ausgelöst wird.

Ich würde Finite-State-Maschinen verwenden, um beispielsweise Pakete per Post zu verfolgen oder um die verschiedenen Status eines Benutzers während des Registrierungsprozesses zu verfolgen.

Mit zunehmender Anzahl möglicher Statuswerte explodiert die Anzahl der Übergänge.Zustandsmaschinen helfen in diesem Fall sehr.

Answer 8

Objekte in Spielen werden oft als Zustandsautomaten dargestellt.Ein KI-Charakter könnte sein:

• Bewachung
• Aggressiv
• Patrouillieren
• Schlafend

Sie können also sehen, dass diese einige einfache, aber effektive Zustände modellieren könnten.Natürlich könnten Sie wahrscheinlich ein komplexeres kontinuierliches System erstellen.

Ein weiteres Beispiel wäre ein Vorgang wie der Kauf über Google Checkout.Google gibt eine Reihe von Zuständen für „Finanzen“ und „Bestellung“ an und informiert Sie dann über Übergänge wie die Freigabe oder Ablehnung Ihrer Kreditkarte und ermöglicht Ihnen die Mitteilung, dass die Bestellung versandt wurde.

Answer 9

Vergleich regulärer Ausdrücke, Analyse, Flusskontrolle in einem komplexen System.

Reguläre Ausdrücke sind eine einfache Form von Zustandsautomaten, insbesondere endliche Automaten.Sie haben als solche eine natürliche Darstellung, obwohl es möglich ist, sie mithilfe gegenseitig rekursiver Funktionen zu implementieren.

Zustandsautomaten werden, wenn sie gut implementiert sind, sehr effizient sein.

Es gibt einen hervorragenden Zustandsmaschinen-Compiler für eine Reihe von Zielsprachen, wenn Sie eine lesbare Zustandsmaschine erstellen möchten.

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

Außerdem können Sie so das gefürchtete „Gehe zu“ vermeiden.

Answer 10

KI in Spielen wird sehr oft mithilfe von State Machines implementiert.Hilft bei der Erstellung diskreter Logik, die viel einfacher zu erstellen und zu testen ist.

Answer 11

Dinge, die mir in den Sinn kommen, sind:

• Roboter-/Maschinenmanipulation...diese Roboterarme in Fabriken
• Simulationsspiele (SimCity, Rennspiel usw.)

Verallgemeinernd:Wenn Sie über eine Reihe von Eingaben verfügen, die bei der Interaktion mit einer dieser Eingaben die Kenntnis der vorherigen Eingaben erfordern, oder mit anderen Worten, wenn die Verarbeitung einer einzelnen Eingabe die Kenntnis der vorherigen Eingaben erfordert.(das heißt, es muss „Zustände“ haben)

Allerdings gibt es nicht viel, von dem ich weiß, dass es nicht auf ein Parsing-Problem reduziert werden kann.

Answer 12

Nur als Randbemerkung: Sie können Zustandsautomaten mit richtigen Tail Calls implementieren, wie ich im erklärt habe Schwanzrekursion Frage.

In diesem Beispiel wird jeder Raum im Spiel als ein Staat betrachtet.

Außerdem werden beim Hardwaredesign mit VHDL (und anderen Logiksynthesesprachen) überall Zustandsmaschinen zur Beschreibung von Hardware verwendet.

Answer 13

Wenn Sie einen einfachen stochastischen Prozess benötigen, können Sie eine Markov-Kette verwenden, die als Zustandsmaschine dargestellt werden kann (angesichts des aktuellen Zustands befindet sich die Kette im nächsten Schritt mit einer bestimmten Wahrscheinlichkeit im Zustand X).

Answer 14

Jede Workflow-Anwendung, insbesondere mit asynchronen Aktivitäten.Sie haben ein Element im Workflow in einem bestimmten Status und die Zustandsmaschine weiß, wie sie auf externe Ereignisse reagieren soll, indem sie das Element in einen anderen Status versetzt, woraufhin eine andere Aktivität stattfindet.

Answer 15

Das Zustandskonzept ist für Anwendungen sehr nützlich, um sich den aktuellen Kontext Ihres Systems zu „merken“ und richtig zu reagieren, wenn eine neue Information eintrifft.Bei jeder nicht trivialen Anwendung ist dieser Gedanke über Variablen und Bedingungen in den Code eingebettet.

Wenn Ihre Anwendung also aufgrund des Kontexts, in dem Sie sich befinden, jedes Mal anders reagieren muss, wenn sie eine neue Information erhält, können Sie Ihr System mit einem Zustandsautomaten modellieren.Ein Beispiel wäre die Interpretation der Tasten eines Taschenrechners, die davon abhängt, was Sie gerade verarbeiten.

Im Gegenteil, wenn Ihre Berechnung nicht vom Kontext abhängt, sondern ausschließlich von der Eingabe (wie eine Funktion, die zwei Zahlen addiert), benötigen Sie keinen Zustandsautomaten (oder besser gesagt, Sie haben einen Zustandsautomaten mit null Zuständen).

Manche Leute entwerfen die gesamte Anwendung in Form von Zustandsautomaten, da sie die wesentlichen Dinge erfassen, die in Ihrem Projekt berücksichtigt werden müssen, und sie dann mithilfe einer Prozedur oder eines Autocoders ausführbar machen.Es erfordert einige Paradigmenwechsel, auf diese Weise zu programmieren, aber ich fand es sehr effektiv.