Znajdowanie odległości między dwoma wielomianami (przedstawionymi jako drzewa)

Kolega pracujący nad programowaniem genetycznym zadał mi następujące pytanie. Najpierw próbowałem go rozwiązać w oparciu o chciwe podejście, ale po drugiej myśli znalazłem kontrprzykład na algorytm chciwy. Pomyślałem więc, że warto tu wspomnieć.

Rozważ dwa wielomiany reprezentowane przez drzewa wyrażeń. Na przykład $x^3-2x+1$ i $x^2 + 4$ pokazano poniżej:

Zasady:

1. Każdy węzeł jest albo nazwą zmiennej ( $x, y, z, \ldots$ ), liczbą , albo operacją (+, -, ×).
2. Przechodzenie drzewa w kolejności powinno skutkować prawidłowym wielomianem.
3. Węzły operacyjne mają stopień 2. Inne węzły mają stopień 0. Wszystkie węzły mają stopień 1 (z wyjątkiem rdzenia, którego stopień wynosi 0).

W węźle N drzewa zdefiniuj podstawową operację w następujący sposób:

1. Podstawowa operacja może zmienić etykietę węzła. Na przykład $x$ można zmienić na 3 lub + na $\times$ .
2. Podstawowa operacja może zbudować drzewo wyrażeń na N (patrz przykład poniżej).

Koszt podstawowej operacji typu 1 wynosi 1. Koszt typu 2 jest równy liczbie operacji {+, -, ×} w nowo zbudowanym drzewie wyrażeń.

Przykład dla typu 2: Koszt następującej podstawowej operacji wynosi 2, ponieważ drzewo wyrażeń zbudowane na węźle N używa dwóch operacji (- i ×).

Niech T1 i T2 będą dwoma drzewami ekspresyjnymi reprezentującymi wielomiany. Zdefiniuj odległość T1 i T2 w następujący sposób: minimalny koszt podstawowych operacji konwersji T1 na T2. Zauważ, że nie wymagamy, aby przekonwertowane drzewo miało taką samą strukturę jak T2. Chcemy tylko, aby obliczał ten sam wielomian jak T2. (Zobacz komentarze dla przykładu.)

Problem: Biorąc pod uwagę T1 i T2, przedstawiamy algorytm obliczający ich odległość.

Przykład 1: Niech T1 i T2 to dwa drzewa przedstawione na początku tego postu. Aby przekonwertować prawe drzewo na lewe, można zbudować drzewo o koszcie 3 na górze × i zmienić 4 na 1 (całkowity koszt to 4).

$x^4$$x^4+4x^3+6x^2+4x+1$$x$$(x+1)^4$$x$$4x^3$$6x^2$$4x$

Odległość edycji drzewa jest uogólnieniem odległości edycji łańcucha. Odległość między dwoma drzewami to minimalna liczba wstawień węzłów \ delecji \ i etykiet wymaganych do przekształcenia jednego drzewa w drugie. (kiedy usuwamy węzeł v, dzieci v stają się dziećmi rodzica (v)). Problem jest trudny NP, gdy drzewa są nieuporządkowane, ale kiedy są uporządkowane (tzn. Między rodzeństwem istnieje kolejność od lewej do prawej), problem można rozwiązać w czasie O (n ^ 3) (jak w artykule, w którym Wspomniany Sadeq). Dobra ankieta, która opisuje to: http://portal.acm.org/citation.cfm?id=1085283