Pour quels types de problèmes les machines d’état sont-elles utiles ?[fermé]

Question

Pour quels types de problèmes de programmation les machines à états sont-elles les plus adaptées ?

J'ai lu des informations sur les analyseurs implémentés à l'aide de machines à états, mais j'aimerais en savoir plus sur les problèmes qui nécessitent d'être implémentés en tant que machine à états.

Answer 1

La réponse la plus simple est probablement qu’ils conviennent à pratiquement tous les problèmes.N'oubliez pas qu'un ordinateur lui-même est aussi une machine à états.

Indépendamment de cela, les machines à états sont généralement utilisées pour des problèmes pour lesquels il existe un certain flux d'entrée et l'activité qui doit être effectuée à un moment donné dépend des derniers éléments vus dans ce flux à ce stade.

Exemples de ce flux d'entrée :un fichier texte dans le cas de l'analyse, une chaîne pour les expressions régulières, des événements tels que player entered room pour l'IA du jeu, etc.

Exemples d'activités :être prêt à lire un nombre (après un autre nombre suivi d'un + sont apparus dans l'entrée d'un analyseur pour une calculatrice), se retourner (après que le joueur s'est approché puis éternué), effectuer un coup de pied sauté (après que le joueur a appuyé sur gauche, gauche, droite, haut, haut).

Answer 2

Une bonne ressource est-ce gratuit Livre électronique sur les machines à états.Ma propre réponse rapide est ci-dessous.

Lorsque votre logique doit contenir des informations sur ce qui s'est passé lors de sa dernière exécution, elle doit contenir un état.

Ainsi, une machine à états est simplement n'importe quel code qui mémorise (ou agit sur) des informations qui ne peuvent être obtenues qu'en comprenant ce qui s'est passé auparavant.

Par exemple, j'ai un modem cellulaire que mon programme doit utiliser.Il doit effectuer les étapes suivantes dans l'ordre :

1. réinitialiser le modem
2. initier la communication avec le modem
3. attendez que la force du signal indique une bonne connexion avec une tour
4. ...

Maintenant, je pourrais bloquer le programme principal et simplement suivre toutes ces étapes dans l'ordre, en attendant que chacune s'exécute, mais je souhaite donner mon avis à mon utilisateur et effectuer d'autres opérations en même temps.J'implémente donc cela en tant que machine à états dans une fonction et j'exécute cette fonction 100 fois par seconde.

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
}

Les machines à états plus complexes implémentent des protocoles.Par exemple, un protocole de diagnostic ECU que j'ai utilisé ne peut envoyer que des paquets de 8 octets, mais je dois parfois envoyer des paquets plus gros.L'ECU est lent, je dois donc attendre une réponse.Idéalement, lorsque j'envoie un message, j'utilise une fonction, puis je me fiche de ce qui se passe, mais quelque part, mon programme doit surveiller la ligne, envoyer et répondre à ces messages, les divisant en morceaux plus petits et réassemblant les morceaux de messages reçus en le message final.

Answer 3

Les protocoles avec état tels que TCP sont souvent représentés comme des machines à états.Cependant, il est rare que vous souhaitiez implémenter quoi que ce soit en tant que machine à états proprement dite.Habituellement, vous utiliserez une corruption de celui-ci, c'est-à-diredemandez-lui d'effectuer une action répétée tout en étant dans un état, d'enregistrer des données pendant la transition ou d'échanger des données tout en restant dans un état.

Answer 4

Flux de travail (voir WF dans .net 3.0)

Answer 5

Ils ont de nombreuses utilisations, les analyseurs étant l’une des plus notables.J'ai personnellement utilisé des machines à états simplifiées pour implémenter des boîtes de dialogue de tâches complexes en plusieurs étapes dans des applications.

Answer 6

Un exemple d'analyseur.J'ai récemment écrit un analyseur qui prend un flux binaire d'un autre programme.La signification de l'élément actuel analysé indique la taille/signification des éléments suivants.Il existe un (petit) nombre fini d’éléments possibles.D’où une machine à états.

Answer 7

Ils sont parfaits pour modéliser des éléments qui changent de statut et ont une logique qui se déclenche à chaque transition.

J'utiliserais des machines à états finis pour suivre les colis par courrier ou pour suivre les différentes statistiques d'un utilisateur pendant le processus d'inscription, par exemple.

À mesure que le nombre de valeurs de statut possibles augmente, le nombre de transitions explose.Les machines à états aident beaucoup dans ce cas.

Answer 8

Les objets dans les jeux sont souvent représentés comme des machines à états.Un personnage IA peut être :

• Garde
• Agressif
• Patrouille
• Endormi

Vous pouvez donc voir que ceux-ci pourraient modéliser des états simples mais efficaces.Bien sûr, vous pourriez probablement créer un système continu plus complexe.

Un autre exemple serait un processus tel que réaliser un achat sur Google Checkout.Google donne un certain nombre d'états pour les finances et la commande, puis vous informe des transitions telles que l'effacement ou le rejet de la carte de crédit, et vous permet de l'informer que la commande a été expédiée.

Answer 9

Correspondance d'expressions régulières, Analyse, Contrôle de flux dans un système complexe.

Les expressions régulières sont une forme simple de machine à états, en particulier les automates finis.Ils ont une représentation naturelle en tant que telle, bien qu'il soit possible de les implémenter en utilisant des fonctions mutuellement récursives.

Les machines à états, lorsqu'elles sont bien mises en œuvre, seront très efficaces.

Il existe un excellent compilateur de machine à états pour un certain nombre de langages cibles, si vous souhaitez créer une machine à états lisible.

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

Cela vous permet également d’éviter le redoutable « goto ».

Answer 10

L'IA dans les jeux est très souvent implémentée à l'aide de machines à états.Aide à créer une logique discrète beaucoup plus facile à créer et à tester.

Answer 11

Les choses qui me viennent à l'esprit sont :

• Manipulation de robots/machines...ces bras de robot dans les usines
• Jeux de simulation, (SimCity, Racing Game etc.)

Généraliser :Lorsque vous disposez d'une chaîne d'entrées qui, lors de l'interaction avec l'une d'entre elles, nécessite la connaissance des entrées précédentes ou, en d'autres termes, lorsque le traitement d'une seule entrée nécessite la connaissance des entrées précédentes.(c'est-à-dire qu'il doit avoir des "états")

Cependant, peu de choses à ma connaissance ne sont pas réductibles à un problème d'analyse.

Answer 12

En remarque, vous pouvez implémenter des machines à états avec des appels de queue appropriés, comme je l'ai expliqué dans le récursivité de la queue question.

Dans cet exemple, chaque pièce du jeu est considérée comme un état.

De plus, la conception matérielle avec VHDL (et d'autres langages de synthèse logique) utilise des machines à états partout pour décrire le matériel.

Answer 13

Si vous avez besoin d'un processus stochastique simple, vous pouvez utiliser une chaîne de Markov, qui peut être représentée comme une machine à états (étant donné l'état actuel, à l'étape suivante, la chaîne sera dans l'état X avec une certaine probabilité).

Answer 14

Toute application de workflow, notamment avec des activités asynchrones.Vous avez un élément dans le flux de travail dans un certain état et la machine d'état sait comment réagir aux événements externes en plaçant l'élément dans un état différent, auquel cas une autre activité se produit.

Answer 15

La notion d'état est très utile aux applications pour « se souvenir » du contexte actuel de votre système et réagir correctement lorsqu'une nouvelle information arrive.Toute application non triviale intègre cette notion dans le code via des variables et des conditions.

Ainsi, si votre application doit réagir différemment à chaque fois qu'elle reçoit une nouvelle information en raison du contexte dans lequel vous vous trouvez, vous pouvez modéliser votre système avec une machine à états.Un exemple serait la façon d'interpréter les touches d'une calculatrice, qui dépend de ce que vous traitez à ce moment-là.

Au contraire, si votre calcul ne dépend pas du contexte mais uniquement de l'entrée (comme une fonction additionnant deux nombres), vous n'aurez pas besoin de machine à états (ou mieux dit, vous aurez une machine à états avec zéro état)

Certaines personnes conçoivent l'ensemble de l'application en termes de machines à états, car elles capturent les éléments essentiels à garder à l'esprit dans votre projet, puis utilisent des procédures ou des autocodeurs pour les rendre exécutables.Il faut une certaine chance de paradigme pour programmer de cette manière, mais je l'ai trouvé très efficace.