Encontrar a distância entre dois polinômios (representados como árvores)

20

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, x32x+1 e x2+4 são ilustrados abaixo:

Regras:

  1. Cada nó é um nome de variável ( x,y,z, ), um número ou uma operação (+, -, ×).
  2. A travessia em ordem da árvore deve resultar em um polinômio válido.
  3. 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:

  1. x×
  2. 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).

x4x4+4x3+6x2+4x+1x(x+1)4x4x36x24x

MS Dousti
fonte
2
Se a operação "excluir" não for permitida, a distância não será uma distância. Por exemplo: uma árvore T1 = (x * x) +4 não pode ser transformada em T2 = x, mas T2 pode ser transformada em T1 adicionando (* x) e depois (+4) em cima de x. Tudo bem? Ou você deve definir a distância como as operações mínimas necessárias para converter T1 em T2 ou T2 em T1.
Marzio De Biasi
4
O custo é igual a 0 se e somente se as duas fórmulas aritméticas fornecidas (sem divisão) representam o mesmo polinômio. Se bem me lembro, esse é um problema típico no coRP (por atribuição aleatória) que não é conhecido por P.
Tsuyoshi Ito
4
@ Tsuyoshi: Ah, entendo. Você está apontando para o problema do teste de identidade polinomial . (Boas referências: [1 ] e [2 ]). Eu devo pensar sobre isso. Enquanto isso, qualquer sugestão é bem-vinda.
MS Dousti
4
Sim é isso. Parece que na versão típica do problema de teste de identidade polinomial, dois polinômios de entrada são dados como circuitos, não como fórmulas. Portanto, minha redação de que a versão da fórmula é "típica" provavelmente foi imprecisa. De qualquer forma, colocar até a versão da fórmula em P parece ser um problema em aberto.
Tsuyoshi Ito
2
@Vor: Na formulação atual, a entrada T1 é realmente uma árvore e a entrada T2 é um polinômio que, por acaso, é dado como árvore, no sentido a seguir. Alterar T1 para uma árvore diferente que representa o mesmo polinômio pode alterar a resposta em geral, enquanto alterar T2 de maneira semelhante não.
Tsuyoshi Ito

Respostas:

10

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

Aviv
fonte
1
Graças Aviv. Será ótimo se você mesclar suas respostas (acho que você tem problemas ao usar sua conta anterior). Você pode usar os conselhos nesta publicação (Especialmente neste link ).
MS Dousti
Como é que esta capa abordagem diferentes árvores com polinômios eqivalent
narek Bojikian