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

20

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:x32x+1x2+4

Règles:

  1. Chaque nœud est soit un nom de variable ( x,y,z, ), 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×
  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é.x4x4+4x3+6x2+4x+1x(x+1)4x4 x 3 6 x 2 4 x4x36x24x

MS Dousti
la source
2
Si l'opération de «suppression» n'est pas autorisée, la distance n'est pas une distance. Par exemple: un arbre T1 = (x * x) +4 ne peut pas être transformé en T2 = x, mais T2 peut être transformé en T1 en ajoutant (* x) puis (+4) au-dessus de x. Est-ce que c'est bon ? Ou vous devez définir la distance comme les opérations minimales requises pour convertir T1 en T2 ou T2 en T1.
Marzio De Biasi
4
Le coût est égal à 0 si et seulement si les deux formules arithmétiques données (sans division) représentent le même polynôme. Si je me souviens bien, c'est un problème typique en coRP (par assignation aléatoire) qui n'est pas connu pour être en P.
Tsuyoshi Ito
4
@Tsuyoshi: Oh, je vois. Vous pointez le problème du test d'identité polynomiale . (Bonnes références: [1 ] et [2 ]). Je dois y penser. En attendant, toute suggestion est la bienvenue.
MS Dousti
4
Oui c'est ça. Il semble que dans la version typique du problème de test d'identité polynomiale, deux polynômes d'entrée sont donnés sous forme de circuits et non de formules. Donc, ma formulation selon laquelle la version de la formule est «typique» était probablement inexacte. Quoi qu'il en soit, même la version de formule en P semble être un problème ouvert.
Tsuyoshi Ito
2
@Vor: Dans la formulation actuelle, l'entrée T1 est vraiment un arbre et l'entrée T2 est un polynôme qui se trouve juste être donné comme un arbre, dans le sens suivant. Changer T1 en un arbre différent qui représente le même polynôme peut changer la réponse en général, alors que changer T2 d'une manière similaire ne change pas.
Tsuyoshi Ito

Réponses:

10

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

Aviv
la source
1
Merci Aviv. Ce sera génial si vous fusionnez vos réponses (je pense que vous avez des problèmes avec votre compte précédent). Vous pouvez utiliser les conseils de ce post (en particulier, ce lien ).
MS Dousti
Comment cette approche couvrirait-elle différents arbres avec des polynômes
équivalents