algorithm - ステートマシンはどのような問題に適していますか?

Question

ステートマシンが最も適しているプログラミングの問題は何ですか?

ステートマシンを使用して実装されているパーサーについて読んだことがありますが、ステートマシンとして実装することを叫んでいる問題について知りたいと思います。

score 15 · Accepted Answer

最も簡単な答えは、おそらく、ほとんどすべての問題に適しているということです。コンピューター自体もステートマシンであることを忘れないでください。

それにもかかわらず、ステートマシンは通常、何らかの入力ストリームがあり、特定の瞬間に実行する必要があるアクティビティが、その時点でそのストリームに表示される最後の要素に依存する問題に使用されます。

この入力ストリームの例: 解析の場合のテキストファイル、正規表現の文字列、player entered roomゲーム AIなどのイベントなど。

アクティビティの例: 数字を読む準備をする (別の数字の後に+電卓のパーサーの入力に表示された後)、向きを変える (プレイヤーが近づいてくしゃみをした後)、ジャンピングキックを実行する (プレイヤーが左を押した後、左、右、上、上）。

score 10 · Accepted Answer

良いリソースは、この無料のState Machine EBookです。私自身の簡単な答えは以下です。

前回の実行時に起こったことに関する情報をロジックに含める必要がある場合は、状態を含める必要があります。

したがって、ステートマシンとは、以前に何が起こったかを理解することによってのみ取得できる情報を記憶する (またはそれに基づいて動作する) コードです。

たとえば、プログラムで使用する必要があるセルラーモデムがあります。次の手順を順番に実行する必要があります。

モデムをリセットする
モデムとの通信を開始する
信号強度がタワーとの良好な接続を示すまで待ちます
...

これで、メインプログラムをブロックして、これらすべての手順を順番に実行し、それぞれが実行されるのを待つことができますが、ユーザーにフィードバックを提供し、同時に他の操作を実行したいと考えています。したがって、これを関数内のステートマシンとして実装し、この関数を 1 秒間に 100 回実行します。

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
}

より複雑なステートマシンは、プロトコルを実装します。たとえば、私が使用した ECU 診断プロトコルは 8 バイトのパケットしか送信できませんが、より大きなパケットを送信する必要がある場合があります。ECUが遅いので、応答を待つ必要があります。理想的には、メッセージを送信するときに 1 つの関数を使用し、何が起こってもかまいませんが、どこかでプログラムが回線を監視し、これらのメッセージを送信して応答し、メッセージを小さな断片に分割し、受信したメッセージの断片を再構築する必要があります。最後のメッセージ。

score 2 · Accepted Answer

TCPなどのステートフルプロトコルは、多くの場合、ステートマシンとして表されます。ただし、ステートマシンとして適切なものを実装する必要があることはめったにありません。通常、1つの破損を使用します。つまり、1つの状態にあるときに繰り返しアクションを実行したり、遷移中にデータをログに記録したり、1つの状態のままでデータを交換したりします。

score 1 · Accepted Answer

1

ワークフロー（.net 3.0のWFを参照）

于 2008-09-02T20:46:19.177 に答える

score 1 · Accepted Answer

それらには多くの用途があり、パーサーは注目に値するものです。私は個人的に単純化されたステートマシンを使用して、アプリケーションに複雑なマルチステップタスクダイアログを実装しました。

score 1 · Accepted Answer

パーサーの例。最近、別のプログラムからバイナリストリームを取得するパーサーを作成しました。解析された現在の要素の意味は、次の要素のサイズ/意味を示します。可能な要素の数は（小さい）有限です。したがって、ステートマシン。

score 1 · Accepted Answer

これらは、ステータスを変更するものをモデル化するのに最適であり、遷移ごとにトリガーするロジックを備えています。

たとえば、メールでパッケージを追跡したり、登録プロセス中にユーザーのさまざまなステータスを追跡したりするために、有限状態マシンを使用します。

可能なステータス値の数が増えると、遷移の数が爆発的に増加します。その場合、ステートマシンは大いに役立ちます。

score 1 · Accepted Answer

ゲームのAIは、ステートマシンを使用して実装されることがよくあります。構築とテストがはるかに簡単な個別のロジックの作成に役立ちます。

score 1 · Accepted Answer

ゲーム内のオブジェクトは、多くの場合、ステートマシンとして表されます。AIキャラクターは次のようになります。

ガード
攻撃的
パトロール
寝落ち

したがって、これらはいくつかの単純だが効果的な状態をモデル化する可能性があることがわかります。もちろん、おそらくもっと複雑な連続システムを作ることもできます。

もう1つの例は、GoogleCheckoutで購入するなどのプロセスです。Googleは、FinancialとOrderについていくつかの州を提供し、クレジットカードの決済や拒否などの移行について通知し、注文が発送されたことを通知できるようにします。

score 1 · Accepted Answer

複雑なシステムでの正規表現のマッチング、解析、フロー制御。

正規表現は、ステートマシン、特に有限オートマトンの単純な形式です。それらは、相互再帰関数を使用して実装することは可能ですが、それ自体が自然な表現を持っています。

ステートマシンを適切に実装すると、非常に効率的になります。

読み取り可能なステートマシンを作成したい場合は、多くのターゲット言語用の優れたステートマシンコンパイラがあります。

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

また、恐ろしい「goto」を回避することもできます。

score 0 · Accepted Answer

頭に浮かぶのは次のとおりです。

ロボット/機械操作...工場のロボットアーム

シミュレーションゲーム（SimCity、レーシングゲームなど）

一般化：入力の文字列があり、それらのいずれかと対話するときに前の入力の知識が必要な場合、つまり、単一の入力の処理に前の入力の知識が必要な場合。（つまり、「状態」が必要です）

しかし、私が知っていることは、構文解析の問題に還元できないことはあまりありません。

score 0 · Accepted Answer

補足として、末尾再帰の質問で説明したように、適切な末尾呼び出しを使用してステートマシンを実装できます。

その例では、ゲームの各部屋は1つの状態と見なされます。

また、VHDL（およびその他の論理合成言語）を使用したハードウェア設計では、あらゆる場所でステートマシンを使用してハードウェアを記述します。

score 0 · Accepted Answer

状態の概念は、アプリケーションがシステムの現在のコンテキストを「記憶」し、新しい情報が到着したときに適切に反応するために非常に役立ちます。自明でないアプリケーションには、変数と条件を介してコードにその概念が埋め込まれています。

したがって、現在のコンテキストのためにアプリケーションが新しい情報を受信するたびに異なる反応をする必要がある場合は、ステートマシンを使用してシステムをモデル化できます。例としては、電卓でキーを解釈する方法があります。これは、その時点で何を処理しているかによって異なります。

逆に、計算がコンテキストに依存せず、入力のみに依存する場合（2つの数値を加算する関数など）、ステートマシンは必要ありません（より適切には、ステートがゼロのステートマシンがあります）。

一部の人々は、プロジェクトで覚えておくべき重要なことをキャプチャし、いくつかのプロシージャまたはオートコーダーを使用してそれらを実行可能にするため、ステートマシンの観点からアプリケーション全体を設計します。このようにプログラミングするにはパラダイムのチャンスが必要ですが、非常に効果的であることがわかりました。

score 0 · Accepted Answer

単純な確率過程が必要な場合は、ステートマシンとして表すことができるマルコフ連鎖を使用できます (現在の状態を考えると、次のステップでは、連鎖は特定の確率で状態 X になります)。

score 0 · Accepted Answer

特に非同期アクティビティを含むワークフローアプリケーション。ワークフロー内に特定の状態のアイテムがあり、ステートマシンは、アイテムを別の状態にすることで外部イベントに対応する方法を認識しており、その時点で他のアクティビティが発生します。

algorithm - ステートマシンはどのような問題に適していますか?

15 に答える 15

Related

Reference