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:

Każdy węzeł jest albo nazwą zmiennej ( $x, y, z, \ldots$ ), liczbą , albo operacją (+, -, ×).
Przechodzenie drzewa w kolejności powinno skutkować prawidłowym wielomianem.
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:

Podstawowa operacja może zmienić etykietę węzła. Na przykład $x$ można zmienić na 3 lub + na $\times$ .
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$

— MS Dousti
źródło

Jeśli operacja „usuń” jest niedozwolona, odległość nie jest odległością. Na przykład: drzewa T1 = (x * x) +4 nie można przekształcić w T2 = x, ale T2 można przekształcić w T1 dodając (* x), a następnie (+4) na x. Czy to jest w porządku ? Lub należy zdefiniować odległość jako minimalną liczbę operacji wymaganych do konwersji T1 na T2 lub T2 na T1.

— Marzio De Biasi,

Koszt jest równy 0 wtedy i tylko wtedy, gdy dwie podane (bez dzielenia) formuły arytmetyczne reprezentują ten sam wielomian. Jeśli dobrze to pamiętam, jest to typowy problem w coRP (losowe przypisanie), o którym nie wiadomo, że jest w P.

— Tsuyoshi Ito

@Tsuyoshi: Oh, rozumiem. Wskazujesz na problem z testowaniem tożsamości wielomianowej . (Dobre referencje: [1 ] i [2 ]). Muszę o tym pomyśleć. Tymczasem wszelkie sugestie są mile widziane.

— MS Dousti,

Tak, to jest to. Wydaje się, że w typowej wersji problemu testowania tożsamości wielomianowej dwa wielomiany wejściowe podano jako obwody, a nie formuły. Więc moje sformułowanie, że wersja formuły jest „typowa”, było prawdopodobnie niedokładne. W każdym razie umieszczenie nawet wersji formuły w P wydaje się być otwartym problemem.

— Tsuyoshi Ito

@Vor: W obecnym sformułowaniu wejście T1 jest tak naprawdę drzewem, a wejście T2 jest wielomianem, który akurat podaje się jako drzewo, w następującym znaczeniu. Zmiana T1 na inne drzewo reprezentujące ten sam wielomian może ogólnie zmienić odpowiedź, podczas gdy zmiana T2 w podobny sposób nie.

— Tsuyoshi Ito,

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

— Aviv
źródło

Dzięki Aviv. Świetnie będzie, jeśli połączysz swoje odpowiedzi (myślę, że masz problemy z używaniem poprzedniego konta). Możesz skorzystać z porad zawartych w tym poście (specjalnie ten link ).

— MS Dousti

Jak to podejście obejmowałoby różne drzewa z równoważnymi wielomianami

— narek Bojikian