Trouver le nombre minimum de transformations nécessaires en fonction de l’entrée et de la chaîne cible

É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?

Disons que j’ai la chaîne suivante aaaa et que j’ai une règle de transformation comme aa-> b. Comment pourrais-je créer les nouveaux nœuds? Je veux dire, comment pourrais-je trouver les sous-chaînes dans cette chaîne d’entrée et les mémoriser?

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

largeur de la chaîne de recherche en premier

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.

Exemple 1: si la cible contient un atome qu’aucune règle ne peut fournir (votre exemple ‘c’).
Exemple 2: si toutes vos règles augmentent la longueur de la chaîne ou la conservent telles quelles (aucune règle ne diminue la longueur de la chaîne)
Exemple 3: vous pouvez supprimer certaines règles si vous avez trouvé par algorithme qu’elles sont cycliques
D’autres exemples existent

comment pixelliser un rectangle en rotation (en 2D par setpixel)