Для каких задач хороши конечные машины?[закрыто]
https://stackoverflow.com/questions/40602
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Для каких задач программирования конечные автоматы больше всего подходят?
Я читал о парсерах, реализуемых с использованием конечных автоматов, но хотел бы узнать о проблемах, которые требуют реализации как конечный автомат.
Решение
Самый простой ответ, вероятно, заключается в том, что они подходят практически для любой проблемы. Не забывайте, что сам компьютер также является конечным автоматом.
Независимо от этого, конечные автоматы обычно используются для задач, в которых есть некоторый поток ввода, и действие, которое необходимо выполнить в данный момент, зависит от последних элементов, увиденных в этом потоке в этой точке.
Примеры этого потока ввода: некоторый текстовый файл в случае разбора, строка для регулярных выражений, события, такие как игрок вошел в комнату для игрового ИИ и т. д.
Примеры действий: будьте готовы прочитать число (после того, как на входе в анализаторе калькулятора появится другое число, за которым после кода + ) развернуться (после того, как игрок подошел и чихнул ), выполнить прыжок с прыжка (после того, как игрок нажал влево, вправо, вверх, вверх).
Другие советы
Хорошим ресурсом является эта бесплатная электронная книга конечных автоматов . Мой быстрый ответ ниже.
Когда ваша логика должна содержать информацию о том, что произошло в последний раз, она должна содержать состояние.
Таким образом, конечный автомат - это просто любой код, который запоминает (или действует на) информацию, которая может быть получена только путем понимания того, что произошло раньше.
Например, у меня есть сотовый модем, который должна использовать моя программа. Он должен выполнить следующие шаги по порядку:
<Ол>Теперь я могу заблокировать основную программу и просто выполнить все эти шаги по порядку, ожидая, пока каждый из них запустится, но я хочу оставить отзыв о своем пользователе и одновременно выполнить другие операции. Поэтому я реализую это как конечный автомат внутри функции и запускаю эту функцию 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 работает медленно, поэтому мне нужно дождаться ответа. В идеале, когда я отправляю сообщение, я использую одну функцию, и тогда мне все равно, что происходит, но где-то моя программа должна отслеживать линию и отправлять и отвечать на эти сообщения, разбивая их на более мелкие части и собирая части полученных сообщений в последнее сообщение.
Протоколы с отслеживанием состояния, такие как TCP, часто представлены как конечные автоматы. Однако редко вы захотите реализовать что-либо как конечный автомат. Обычно вы будете использовать повреждение одного, т. Е. Выполнять повторяющееся действие, находясь в одном состоянии, регистрируя данные во время перехода или обмениваясь данными, оставаясь в одном состоянии.
Рабочий процесс (см. WF в .net 3.0)
У них много применений, особенно заметны парсеры. Я лично использовал упрощенные конечные автоматы для реализации сложных многоэтапных диалогов задач в приложениях.
Пример парсера. Недавно я написал парсер, который принимает двоичный поток из другой программы. Значение текущего проанализированного элемента указывает размер / значение следующих элементов. Возможно (небольшое) конечное число элементов. Отсюда и конечный автомат.
Они отлично подходят для моделирования вещей, которые меняют статус, и имеют логику, которая срабатывает при каждом переходе.
Я бы использовал конечные автоматы для отслеживания пакетов по почте или, например, для отслеживания различных данных пользователя в процессе регистрации.
По мере увеличения числа возможных значений состояния количество переходов увеличивается. В этом случае очень помогают конечные автоматы.
Объекты в играх часто представляются в виде конечных автоматов.Персонаж с искусственным интеллектом может быть:
- Охраняющий
- Агрессивный
- Патрулирование
- Спящий
Таким образом, вы можете видеть, что они могут моделировать некоторые простые, но эффективные состояния.Конечно, вы, вероятно, могли бы создать более сложную непрерывную систему.
Другим примером может служить такой процесс, как совершение покупки в Google Checkout.Google указывает несколько состояний для финансовых операций и заказа, а затем информирует вас о транзакциях, таких как списание средств с кредитной карты или отклонение, и позволяет вам сообщить ему, что заказ отправлен.
Сопоставление регулярных выражений, анализ, управление потоком в сложной системе.
Регулярные выражения - это простая форма конечного автомата, а именно конечных автоматов. Они имеют естественное представление как таковое, хотя их можно реализовать с помощью взаимно рекурсивных функций.
Конечные автоматы, когда реализованы хорошо, будут очень эффективными.
Существует отличный компилятор конечного автомата для ряда целевых языков, если вы хотите сделать читаемый конечный автомат.
http://research.cs.queensu.ca/~thurston/ragel/
Это также позволяет вам избежать страшного «перехода».
ИИ в играх очень часто реализуется с помощью State Machines. Помогает создавать дискретную логику, которую гораздо проще создавать и тестировать.
Вот что приходит на ум::
- Манипулирование роботом / Машиной...эти роботизированные руки на фабриках
- Игры-симуляторы (SimCity, Гоночные игры и т.д.)
Обобщающий:Когда у вас есть строка входных данных, которая при взаимодействии с любым из них требует знания предыдущих входных данных или, другими словами, при обработке любого отдельного входного сигнала требуется знание предыдущих входных данных.(то есть у него должны быть "состояния")
Однако, насколько я знаю, не так много такого, что нельзя было бы свести к проблеме синтаксического анализа.
В качестве дополнительного примечания вы можете реализовать конечные автоматы с соответствующими хвостовыми вызовами, как я объяснил в хвостовой рекурсии вопрос.
В этом примере каждая комната в игре считается одним состоянием.
Кроме того, при разработке аппаратного обеспечения с использованием VHDL (и других языков логического синтеза) везде используются конечные автоматы для описания аппаратного обеспечения.
Если вам нужен простой случайный процесс, вы могли бы использовать цепочку Маркова, которая может быть представлена в виде конечного автомата (учитывая текущее состояние, на следующем шаге цепочка с определенной вероятностью будет находиться в состоянии X).
Любое приложение рабочего процесса, особенно с асинхронными действиями. У вас есть элемент в рабочем процессе в определенном состоянии, и конечный автомат знает, как реагировать на внешние события, переводя элемент в другое состояние, после чего происходит какое-то другое действие.
Концепция состояния очень полезна для приложений, которые "запоминают" текущий контекст вашей системы и правильно реагируйте на поступление новой информации. В любом нетривиальном приложении это понятие встроено в код через переменные и условные выражения.
Так что если ваше приложение должно реагировать по-разному каждый раз, когда оно получает новую информацию, из-за контекста, в котором вы находитесь, вы можете смоделировать вашу систему с помощью конечных автоматов. Примером может служить интерпретация ключей на калькуляторе, которая зависит от того, что вы обрабатываете в данный момент времени.
Напротив, если ваши вычисления зависят не от контекста, а исключительно от ввода (например, функция, добавляющая два числа), вам не понадобится конечный автомат (или, точнее, у вас будет конечный автомат с нулем) состояния)
Некоторые люди разрабатывают все приложение в терминах конечных автоматов, поскольку они собирают важные вещи, которые необходимо учитывать в вашем проекте, а затем используют некоторые процедуры или автокодеры, чтобы сделать их исполняемыми. Программирование таким способом требует некоторой парадигмы, но я нашел это очень эффективным.
