Какие проблемы подходят для государственных машин?

Ответ 1

Самый простой ответ - вероятно, что они подходят практически для любой проблемы. Не забывайте, что сам компьютер также является конечным автоматом.

Независимо от этого, конечные машины обычно используются для проблем, где есть некоторый поток ввода, и деятельность, которая должна выполняться в данный момент, зависит от последних элементов, видимых в этом потоке в этой точке.

Примеры этого потока ввода: некоторый текстовый файл в случае разбора, строка для регулярных выражений, события, такие как player entered room для AI игры и т.д.

Примеры действий: быть готовыми к чтению числа (после того, как другой номер, за которым следует +, появился на входе в парсере для калькулятора), развернитесь (после того, как игрок приблизился, а затем чихнул), совершите прыгающий удар (после нажатия игрока влево, влево, вправо, вверх, вверх).

Ответ 2

Хорошим ресурсом является бесплатный State Machine EBook. Мой собственный быстрый ответ ниже.

Когда ваша логика должна содержать информацию о том, что произошло в последний раз, когда она была запущена, она должна содержать состояние.

Таким образом, конечная машина - это просто любой код, который запоминает (или действует) информацию, которая может быть получена только путем понимания того, что произошло раньше.

Например, у меня есть сотовый модем, который должна использовать моя программа. Он должен выполнить следующие шаги:

• reset модем
• инициировать связь с модемом
• дождитесь, когда сила сигнала укажет на хорошее соединение с башней.
• ...

Теперь я могу заблокировать основную программу и просто выполнить все эти шаги по порядку, ожидая, что каждый из них будет запущен, но я хочу дать отзыв пользователя и выполнить другие операции одновременно. Поэтому я реализую это как конечный автомат внутри функции и запускаю эту функцию 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 работает медленно, поэтому мне нужно подождать ответа. В идеале, когда я отправляю сообщение, я использую одну функцию, а затем мне все равно, что происходит, но где-то моя программа должна следить за строкой, отправлять и отвечать на эти сообщения, разбивать их на более мелкие части и повторно собирать куски полученных сообщений в окончательное сообщение.

Ответ 3

Протоколы состояния, такие как TCP, часто представлены как государственные машины. Однако редко бывает, что вы хотите внедрить что-либо в качестве собственно конечной машины. Обычно вы будете использовать одно из них, т.е. Выполнять повторяющееся действие, сидя в одном состоянии, регистрируя данные во время их перехода или обмениваясь данными, оставаясь в одном состоянии.

Ответ 4

Рабочий процесс (см. WF в .net 3.0)

Ответ 5

У них много применений, синтаксические анализаторы являются заметными. Я лично использовал упрощенные государственные машины для реализации сложных многошаговых диалогов задач в приложениях.

Ответ 6

Пример анализатора. Недавно я написал парсер, который берет двоичный поток из другой программы. Значение текущего элемента parsed указывает размер/значение следующих элементов. Существует (небольшое) конечное число элементов. Следовательно, машина состояний.

Ответ 7

Они отлично подходят для моделирования вещей, которые меняют статус, и имеют логику, которая срабатывает при каждом переходе.

Я бы использовал конечные машины для отслеживания пакетов по почте или, например, для отслеживания различных статов пользователя во время процесса регистрации.

По мере того как число возможных значений состояния увеличивается, число переходов взрывается. В этом случае государственные машины много помогают.

Ответ 8

AI в играх очень часто реализуется с использованием State Machines. Помогает создать дискретную логику, которую намного проще построить и протестировать.

Ответ 9

Объекты в играх часто представлены как государственные машины. Символ AI может быть:

• Ограждение
• Агрессивная
• патрулирование
• Спящий

Итак, вы можете видеть, что они могут моделировать простые, но эффективные состояния. Конечно, вы, возможно, могли бы создать более сложную непрерывную систему.

Другим примером может быть такой процесс, как совершение покупки в Google Checkout. Google предоставляет ряд состояний для финансов и заказа, а затем информирует вас о транзитах, таких как очистка кредитной карты или об отказе, и позволяет сообщить, что заказ отправлен.

Ответ 10

Совместимость регулярных выражений, анализ, управление потоком в сложной системе.

Регулярные выражения - это простая форма конечного автомата, в частности конечные автоматы. Они имеют естественное представление как таковое, хотя их можно реализовать с помощью взаимно рекурсивных функций.

Государственные машины, когда они будут хорошо реализованы, будут очень эффективными.

Существует отличный компилятор конечных машин для нескольких целевых языков, если вы хотите сделать читаемый конечный автомат.

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

Он также позволяет избежать страшного "goto".

Ответ 11

Что приходит в голову:

• Робот/Машинная манипуляция... эти роботы на фабриках
• Моделирование игр, (SimCity, Racing Game и т.д.)

Обобщение: когда у вас есть строка входов, которая при взаимодействии с кем-либо из них требует знания предыдущих входов или, другими словами, при обработке любого отдельного входа требуется знание предыдущих входов. (то есть, он должен иметь "состояния" )

Не так много, что я знаю, что это не сводится к проблеме разбора.

Ответ 12

Как примечание, вы можете реализовать государственные машины с соответствующими хвостовыми вызовами, как я объяснил в вопросе хвоста рекурсии.

В этом примере каждая комната в игре считается одним из состояний.

Кроме того, аппаратное проектирование с VHDL (и другими языками логического синтеза) во всех случаях использует аппаратные средства для описания аппаратного обеспечения.

Ответ 13

Если вам нужен простой случайный процесс, вы можете использовать цепочку Маркова, которая может быть представлена ​​как конечная машина (учитывая текущее состояние, на следующем шаге цепь будет находиться в состоянии X с определенной вероятностью).

Ответ 14

Любое приложение рабочего процесса, особенно с асинхронными действиями. У вас есть элемент в рабочем процессе в определенном состоянии, и конечный автомат знает, как реагировать на внешние события, поместив элемент в другое состояние, после чего произойдет какое-то другое действие.

Ответ 15

Концепция состояния очень полезна, когда приложения "запоминают" текущий контекст вашей системы и правильно реагируют, когда приходит новая информация. Любое нетривиальное приложение имеет это понятие, встроенное в код через переменные и условные обозначения.

Итак, если ваше приложение должно реагировать по-разному каждый раз, когда он получает новую информацию из-за контекста, в котором вы находитесь, вы можете смоделировать свою систему с помощью государственных машин. Примером может служить интерпретация ключей калькулятора, которая зависит от того, что вы обрабатываете в этот момент времени.

Напротив, если ваше вычисление не зависит от контекста, а исключительно от входа (например, функция, добавляющая два числа), вам не понадобится конечный автомат (или, лучше сказать, у вас будет конечный автомат с нулевым значением состояния)

Некоторые люди разрабатывают все приложение с точки зрения государственных машин, так как они фиксируют основные вещи, которые нужно учитывать в вашем проекте, а затем использовать некоторую процедуру или автокодеры, чтобы сделать их исполняемыми. Для этого требуется определенная парадигма, но я нашел ее очень эффективной.