Edycja odległości między dwoma wykresami

Question

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?

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

powinien zajrzeć na papierze A survey of graph edit distance