Étant donné que j’ai une chaîne d’ entrée , par exemple: aab
Et on me donne une chaîne cible , par exemple: bababa
Et puis on me donne un ensemble de règles de transformation. Par exemple:
ab -> bba b -> ba
Comment pourrais-je faire, en C, un algorithme qui trouverait le nombre minimal de transformations à appliquer dans la chaîne d’entrée pour obtenir la chaîne cible.
Dans cet exemple, par exemple, le nombre serait 3. Parce que nous ferions:
1 - Apply rule 1 (abba) 2 - Apply rule 1 again (bbaba) 3 - Apply rule 2 (bababa)
Il peut arriver qu’avec une entrée et une cible, il n’y ait pas de solution et cela doit également être noté.
Je suis assez perdu dans les stratégies pour le faire. Cela me vient à l’esprit de créer un automate, mais je ne sais pas comment je pourrais l’appliquer dans cette situation. Je pense que le problème est intéressant et que je fais des recherches en ligne, mais tout ce que je peux trouver, ce sont des transformations à partir de règles, mais pas comment faire en sorte que ce soit un minimum.
EDIT: Comme l’une des réponses suggérées, nous pourrions créer un graphique à partir de la chaîne initiale et créer des nœuds résultant de l’application de transformations au nœud précédent. Cependant, cela pose certains problèmes, de mon sharepoint vue:
Imaginez que j’ai une transformation qui ressemble à ceci a -> ab. Et ma chaîne initiale est ‘a’. Et ma chaîne de sortie est ‘c’. Donc, je continue à faire des transformations (croissance du graphique) comme ceci:
a -> ab ab -> abb abb -> abbb …
Comment saurais-je que je dois arrêter de construire le graphique?
Je ne pense pas qu’il existe une solution efficace pour cela. Je pense que vous devez faire une première recherche en profondeur. en faisant cela, vous saurez que dès que vous avez une solution, c’est la solution la plus courte .
EDIT :
Image: modifiez d’abord la largeur de la chaîne
Chaque couche est faite à partir de la précédente en appliquant toutes les règles possibles à toutes les sous-chaînes possibles. Par exemple, la règle b->ba
peut être appliquée à abba
pour chaque b
. Il est important de n’appliquer qu’une seule règle et de ne pas oublier cette chaîne (par exemple, ababa et abbaa) dans une liste. Vous devez avoir complètement chaque couche dans une liste dans votre programme avant de commencer la couche suivante (= largeur en premier).
EDIT 2 :
Vous écrivez vous avez maintenant une sortie c
. Pour cela, vous avez évidemment besoin d’une règle avec XX->c
. Alors disons que tu as la règle aaa->c
. Maintenant, dans la couche 2, vous aurez une chaîne aaa
qui provient de certaines règles a->aa
. Vous appliquerez alors a->aa
nouveau et obtiendrez aaaa
, ce qui est correct, car vous devriez aller d’abord en largeur, puis vous appliquerez la règle aaa->c
à aaa
et vous aurez maintenant la couche 3 composée de aaaa
, c
et autres. Vous ne continuez pas à modifier aaaa
car cela irait à la couche 4, vous avez déjà trouvé la cible c
dans la couche 3 pour pouvoir vous arrêter.
EDIT 3 :
Vous demandez maintenant si vous pouvez décider d’un ensemble de règles non spécifié comment décider quand arrêter la superposition. En général, c’est impossible, on l’appelle le problème Halting https://en.wikipedia.org/wiki/Halting_problem .
MAIS Pour des règles spécifiques, vous pouvez dire si vous pouvez un jour atteindre la sortie.