Niedawno przeczytałem to podsumowanie zagadnień związanych z różnicowaniem między drzewami i zainteresowało mnie poznanie najnowocześniejszych rozwiązań tego problemu.
Załóżmy również, że między dozwolonymi operacjami edycji jest tradycyjny węzeł dodawania / usuwania, edytuj zawartość, którą dodajesz rozszerzonymi operacjami poddrzewa kopiuj / przenieś, czy to sprawia, że problem (znalezienie optymalnej różnicy) jest łatwiejszy czy trudniejszy?
Odpowiedzi:
Poniższy artykuł opisuje nieco bardziej wydajny algorytm obliczania odległości edycji drzewa niż Zhang-Shasha, wraz z dowodem, że ich algorytm jest optymalny (w ramach pewnej szerokiej klasy algorytmów):
Przydatna ankieta na ten temat, nieco nieaktualna:
Philip Bille. Ankieta na temat odległości edycji drzewa i powiązanych problemów . Theoretical Computer Science, tom 337, numery 1–3, strony 217–239, 2005.
Ostatni artykuł na temat jednej z wersji problemu:
Tatsuya Akutsu i in. Dokładne algorytmy do obliczania odległości edycji drzewa między nieuporządkowanymi drzewami . Theoretical Computer Science, tom 412, wydania 4–5, strony 352–364, 2011.