Um colega que trabalha em programação genética me fez a seguinte pergunta. Primeiro tentei resolvê-lo com base em uma abordagem gananciosa, mas, pensando bem, encontrei um contraexemplo do algoritmo ganancioso. Então, pensei que vale a pena mencionar aqui.
Considere dois polinômios que são representados por suas árvores de expressão. Por exemplo, e são ilustrados abaixo:
Regras:
- Cada nó é um nome de variável ( ), um número ou uma operação (+, -, ×).
- A travessia em ordem da árvore deve resultar em um polinômio válido.
- Os nós de operação possuem grau 2. Outros nós possuem grau 0. Todos os nós possuem grau 1 (exceto raiz, cuja graduação é 0).
Em um nó N da árvore, defina a operação básica da seguinte maneira:
- Uma operação básica pode construir uma árvore de expressão em cima de N (veja o exemplo abaixo).
O custo da operação básica do tipo 1 é 1. O custo do tipo 2 é igual ao número de operações {+, -, ×} na árvore de expressão recém-criada.
Exemplo para o tipo 2: O custo da operação básica a seguir é 2, pois a árvore de expressão criada no topo do nó N usa duas operações (- e ×).
Seja T1 e T2 duas árvores de expressão representando polinômios. Defina a distância de T1 e T2 da seguinte forma: o custo mínimo das operações básicas para converter T1 em T2. Observe que não exigimos que a árvore convertida tenha a mesma estrutura que T2. Nós apenas queremos que ele calcule o mesmo polinômio que T2. (Veja os comentários para um exemplo.)
O problema: dados T1 e T2, apresentam um algoritmo que calcula sua distância.
Exemplo 1: Seja T1 e T2 as duas árvores ilustradas no início deste post. Para converter a árvore direita para a esquerda, é possível construir uma árvore de custo 3 em cima de × e alterar 4 para 1 (o custo total é 4).
Respostas:
Distância de Edição em Árvore é uma generalização da distância de edição de sequência. A distância entre duas árvores é o número mínimo de inserções de nó \ exclusões \ e novas etiquetas necessárias para transformar uma árvore na outra. (quando excluímos o nó v, os filhos de v se tornam filhos do pai (v)). O problema é NP-difícil quando as árvores não são ordenadas, mas quando são ordenadas (ou seja, existe uma ordem da esquerda para a direita entre os irmãos), o problema é solucionável em O (n ^ 3) (como no artigo que Sadeq mencionado). Uma boa pesquisa que descreve isso: http://portal.acm.org/citation.cfm?id=1085283
fonte