18

Zastanawiam się tylko, czy podobnie jak w przypadku ciągów, w których mamy odległość Levenshteina (lub odległość edycji) między dwoma ciągami, czy jest coś podobnego do wykresów?Edycja odległości między dwoma wykresami

Mam na myśli miarę skalarną, która identyfikuje liczbę operacji atomowych (wstawianie/usuwanie węzłów i krawędzi), aby przekształcić wykres G1 na wykres G2.

Odpowiedz

3

Uwaga:

Odległość Levenshteina (lub edytować odległość) wynosi od dwóch ciągów

Ale na wykresie należy szukać między co najmniej n! pozycja, w której znajduje się Tożsamość każdej krawędzi i wierzchołka. Możesz łatwo porównać dwa wykresy według unikalnego indeksu, ale Głównym pytaniem jest zdefiniowanie tożsamości dla każdego wierzchołka i krawędzi. To pytanie (znaleźć tożsamość dla każdego wierzchołka i krawędzi na dwóch wykresach, które można przekształcić) jest bardzo trudne i nazywany problemem izomorfizmu (NP-Complete). Możesz wyszukiwać wykres izomorfizmu.

4

Dla ogólnego wykresu jest to problem NP-zupełny, o którym inni wspomnieli w swojej odpowiedzi. Ale dla wykresu drzewa są dobrze znane algorytmy wielomianowe. Najbardziej znany z nich jest algorytm "Zhang Shasha", który został opublikowany w 1989 roku.

18

Myślę, że odległość edycji wykresu jest miarą, której szukałeś.

zmieniać wykres odległość ta minimalna liczba modyfikacji, wykres czynności przekształcenie jednego wykres do drugiego, i pozwoliły operacji zmieniać wykres zawiera

  • wkładania/usuwania wyizolowaną wierzchołek
  • wkładania/usuwania krawędzi
  • zmienić etykiety na wierzchołek/EDGE (jeśli jest znakowana wykresy)

jednak obliczanie odległości edycji wykres pomiędzy dwa wykresy NP-trudne. Najskuteczniejszym algorytmem do obliczenia tego jest algorytm oparty na algorytmie A * i istnieją inne nieoptymalne algorytmy.

+2

referencje zadowolić – ivotron

+0

@ivotro te slajdy wprowadzenie podstawowych pojęć GED, http://orion.math.iastate.edu/rymartin/talks/EditDist/editIITcolloq.pdf –

+0

@ Jason.Z te dokumenty/PPT mówi o teorii GED, czy istnieje jakieś wdrożenie oparte na najnowszych sugestiach w GED? – Vishrant