Trouver la distance entre deux polynômes (représentés sous forme d'arbres)

Un collègue qui travaille sur la programmation génétique m'a posé la question suivante. J'ai d'abord essayé de le résoudre sur la base d'une approche gourmande, mais sur une deuxième pensée, j'ai trouvé un contre-exemple à l'algorithme gourmand. J'ai donc pensé qu'il valait la peine de le mentionner ici.

Considérons deux polynômes qui sont représentés par leurs arbres d'expression. Par exemple, et sont illustrés ci-dessous:$x^3-2x+1$$x^2 + 4$

Règles:

1. Chaque nœud est soit un nom de variable ( $x, y, z, \ldots$ ), un nombre ou une opération (+, -, ×).
2. La traversée dans l'ordre de l'arbre doit aboutir à un polynôme valide.
3. Les nœuds d'opération ont un degré 2. Les autres nœuds ont un degré 0. Tous les nœuds ont un degré extérieur 1 (sauf la racine, dont le degré extérieur est 0).

Sur un nœud N de l'arborescence, définissez l' opération de base comme suit:

1. Une opération de base peut modifier le libellé du nœud. Par exemple, peut être changé en 3, ou + peut être changé en .$x$$\times$
2. Une opération de base peut créer une arborescence d'expression au-dessus de N (voir l'exemple ci-dessous).

Le coût de l'opération de base du type 1 est 1. Le coût du type 2 est égal au nombre d'opérations {+, -, ×} dans l'arborescence d'expression nouvellement construite.

Exemple pour le type 2: le coût de l'opération de base suivante est de 2, car l'arborescence d'expression construite au-dessus du nœud N utilise deux opérations (- et ×).

Soit T1 et T2 deux arbres d'expression représentant des polynômes. Définissez la distance de T1 et T2 comme suit: le coût minimum des opérations de base pour convertir T1 en T2. Notez que nous n'avons pas besoin que l'arbre converti ait la même structure que T2. Nous voulons juste qu'il calcule le même polynôme que T2. (Voir les commentaires pour un exemple.)

Le problème: Étant donné T1 et T2, présenter un algorithme qui calcule leur distance.

Exemple 1: Soit T1 et T2 sont les deux arbres illustrés au début de ce post. Pour convertir l'arbre de droite en arbre de gauche, on peut construire un arbre de coût 3 au-dessus de ×, et changer 4 en 1 (le coût total est 4).

Exemple 2: Soit T1 = représenté par l'arborescence suivante. Pour convertir T1 en T2 = , il suffit d'ajouter 1 à chacun des nœuds, pour optain = T2. Cela peut être fait en ajoutant une arborescence d'expression cost-1 au-dessus de chaque nœud . Cet exemple montre que la conversion terme par terme (que j'ai appelée l' approche gourmande au début de cet article) n'est pas une approche optimale. Autrement dit, si l'on veut produire des termes en T2 qui ne sont pas présents dans T1 (c'est-à-dire , , et 1), le coût sera beaucoup plus élevé.$x^4$$x^4+4x^3+6x^2+4x+1$$x$$(x+1)^4$$x$4 x 3 6 x 2 4 x$4x^3$$6x^2$$4x$

Tree Edit Distance est une généralisation de la distance d'édition des chaînes. La distance entre deux arborescences est le nombre minimum d'insertions \ suppressions \ de nœuds et de réétiquettes nécessaires pour transformer une arborescence en l'autre. (lorsque nous supprimons le nœud v, les enfants de v deviennent les enfants du parent (v)). Le problème est NP-difficile lorsque les arbres ne sont pas ordonnés, mais lorsqu'ils sont ordonnés (c'est-à-dire qu'il y a un ordre de gauche à droite parmi les frères et sœurs), le problème est résoluble en temps O (n ^ 3) (comme dans le document qui Sadeq a mentionné). Une bonne enquête qui décrit cela: http://portal.acm.org/citation.cfm?id=1085283