상태 머신은 어떤 종류의 문제에 유용합니까?[닫은]

https://stackoverflow.com/questions/40602

09-06-2019
|

문제

상태 머신은 어떤 종류의 프로그래밍 문제에 가장 적합합니까?

상태 기계를 사용하여 파서가 구현된다는 내용을 읽었지만 상태 기계로 구현해야 하는 문제에 대해 알아보고 싶습니다.

해결책

가장 쉬운 대답은 아마도 거의 모든 문제에 적합하다는 것입니다.컴퓨터 자체도 상태 머신이라는 점을 잊지 마세요.

그럼에도 불구하고, 상태 머신은 일반적으로 입력 스트림이 있고 특정 순간에 수행되어야 하는 활동이 해당 지점에서 해당 스트림에 표시되는 마지막 요소에 따라 달라지는 문제에 사용됩니다.

이 입력 스트림의 예:구문 분석의 경우 일부 텍스트 파일, 정규 표현식용 문자열, 다음과 같은 이벤트 player entered room 게임 AI 등

활동의 예:숫자를 읽을 준비가 되어 있어야 합니다(다른 숫자 다음에 숫자가 따라옴). + 계산기용 파서의 입력에 표시됨), 돌아서기(플레이어가 접근한 후 재채기한 후), 점핑 킥 수행(플레이어가 왼쪽, 왼쪽, 오른쪽, 위쪽, 위쪽을 누른 후).

다른 팁

좋은 자료는 무료입니다 상태 머신 전자책.내 자신의 빠른 답변은 다음과 같습니다.

논리가 마지막으로 실행되었을 때 발생한 상황에 대한 정보를 포함해야 하는 경우 상태도 포함해야 합니다.

따라서 상태 머신은 단순히 이전에 발생한 일을 이해해야만 얻을 수 있는 정보를 기억(또는 그에 따라 작동)하는 코드입니다.

예를 들어, 내 프로그램에서 사용해야 하는 셀룰러 모뎀이 있습니다.다음 단계를 순서대로 수행해야 합니다.

모뎀 재설정
모뎀과의 통신 시작
신호 강도가 타워와의 연결 상태가 양호함을 나타낼 때까지 기다립니다.
...

이제 기본 프로그램을 차단하고 모든 단계를 순서대로 진행하면서 각 단계가 실행될 때까지 기다릴 수 있지만 사용자에게 피드백을 제공하고 동시에 다른 작업을 수행하고 싶습니다.그래서 저는 이것을 함수 내부의 상태 머신으로 구현하고 이 함수를 초당 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와 같은 상태 저장 프로토콜은 종종 상태 머신으로 표시됩니다.그러나 상태 머신으로 어떤 것을 구현해야 하는 경우는 거의 없습니다.일반적으로 하나의 손상을 사용합니다.한 상태에 있는 동안 반복 작업을 수행하거나, 전환하는 동안 데이터를 로깅하거나, 한 상태를 유지하면서 데이터를 교환하도록 하세요.

워크플로(.net 3.0의 WF 참조)

파서는 많은 용도로 사용되며 그 중 파서는 주목할만한 것입니다.저는 개인적으로 애플리케이션에서 복잡한 다단계 작업 대화 상자를 구현하기 위해 단순화된 상태 머신을 사용해 왔습니다.

파서의 예.나는 최근에 다른 프로그램에서 바이너리 스트림을 취하는 파서를 작성했습니다.구문 분석된 현재 요소의 의미는 다음 요소의 크기/의미를 나타냅니다.가능한 (작은) 유한한 수의 요소가 있습니다.따라서 상태 머신.

상태를 변경하는 항목을 모델링하는 데 적합하고 각 전환에서 트리거되는 논리가 있습니다.

예를 들어, 우편으로 패키지를 추적하거나 등록 프로세스 중에 사용자의 다양한 상태를 추적하기 위해 유한 상태 시스템을 사용합니다.

가능한 상태 값의 수가 증가할수록 전환 수가 폭발적으로 늘어납니다.이 경우 상태 머신이 많은 도움이 됩니다.

게임의 객체는 종종 상태 머신으로 표현됩니다.AI 캐릭터는 다음과 같습니다.

가드링
공격적인
순찰
죽어

따라서 이러한 모델이 간단하지만 효과적인 상태를 모델링할 수 있음을 알 수 있습니다.물론 더 복잡한 연속 시스템을 만들 수도 있습니다.

또 다른 예로는 Google Checkout에서 구매하는 것과 같은 프로세스가 있습니다.Google은 Financial 및 Order에 대한 여러 상태를 제공한 다음 신용카드 정산 또는 거부 등의 전환을 알리고 주문이 배송되었음을 알릴 수 있습니다.

복잡한 시스템의 정규식 일치, 구문 분석, 흐름 제어.

정규식은 간단한 형태의 상태 머신, 특히 유한 오토마타입니다.상호 재귀 함수를 사용하여 구현하는 것이 가능하지만 자연스러운 표현을 갖습니다.

상태 머신을 잘 구현하면 매우 효율적입니다.

읽을 수 있는 상태 기계를 만들고 싶다면 다양한 대상 언어에 대한 뛰어난 상태 기계 컴파일러가 있습니다.

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

또한 두려운 'goto'를 피할 수도 있습니다.

게임의 AI는 상태 머신을 사용하여 구현되는 경우가 많습니다.훨씬 쉽게 구축하고 테스트할 수 있는 개별 논리를 생성하는 데 도움이 됩니다.

마음에 떠오르는 것들은 다음과 같습니다:

로봇/기계 조작...공장에 있는 로봇 팔

시뮬레이션 게임(SimCity, 레이싱 게임 등..)

일반화:누군가와 상호작용할 때 이전 입력에 대한 지식이 필요한 일련의 입력이 있는 경우, 즉 단일 입력을 처리할 때 이전 입력에 대한 지식이 필요한 경우.(즉, "상태"가 있어야 함)

내가 아는 것 중 구문 분석 문제로 축소될 수 없는 것은 많지 않습니다.

참고로, 제가 설명한 대로 적절한 테일 호출을 사용하여 상태 머신을 구현할 수 있습니다. 꼬리 재귀 질문.

이 예에서 게임의 각 방은 하나의 상태로 간주됩니다.

또한 VHDL(및 기타 논리 합성 언어)을 사용한 하드웨어 설계에서는 모든 곳에서 상태 머신을 사용하여 하드웨어를 설명합니다.

간단한 확률론적 프로세스가 필요한 경우 상태 머신으로 표현될 수 있는 Markov 체인을 사용할 수 있습니다(현재 상태가 주어지면 다음 단계에서 체인은 특정 확률로 상태 X에 있을 것입니다).

특히 비동기 활동이 포함된 모든 워크플로 애플리케이션.워크플로에 특정 상태의 항목이 있고 상태 시스템은 항목을 다른 상태에 배치하여 다른 활동이 발생하는 시점에 외부 이벤트에 반응하는 방법을 알고 있습니다.

상태 개념은 애플리케이션이 시스템의 현재 컨텍스트를 "기억"하고 새로운 정보가 도착할 때 적절하게 반응하는 데 매우 유용합니다.사소하지 않은 응용 프로그램에는 변수와 조건을 통해 코드에 해당 개념이 포함되어 있습니다.

따라서 애플리케이션이 현재 상황 때문에 새로운 정보를 받을 때마다 다르게 반응해야 한다면 상태 머신을 사용하여 시스템을 모델링할 수 있습니다.예를 들어 계산기의 키를 해석하는 방법은 해당 시점에 처리 중인 내용에 따라 달라집니다.

반대로, 계산이 컨텍스트에 의존하지 않고 입력에만 의존하는 경우(예: 두 숫자를 추가하는 함수) 상태 머신이 필요하지 않습니다(또는 더 잘 말하면 상태가 0인 상태 머신을 갖게 됩니다).

어떤 사람들은 프로젝트에서 염두에 두어야 할 필수 사항을 캡처한 다음 일부 프로시저나 자동 코더를 사용하여 실행 가능하게 만들기 때문에 상태 머신 측면에서 전체 애플리케이션을 설계합니다.이런 방식으로 프로그래밍하려면 패러다임의 기회가 필요하지만 매우 효과적이라는 것을 알았습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow