Algorithmus zum Vergleich der Ähnlichkeit von gerichteten Pfaden durch gerichtete Grafik

Question

Ich habe einen gerichteten Diagramm mit zwei gerichteten Pfaden darin.

Ich möchte einen Algorithmus, der die Ähnlichkeit zwischen den beiden Pfaden bestimmt.

Dieser Beitrag Erwähnungen mit dem Levenshtein -Entfernung eine ungefähre Ähnlichkeit zu bestimmen. Mir ist auch klar, dass die Hamming -Entfernung Verwendet eine ähnliche Metrik.

Meine Frage ist:

Wie gehen Sie mit dem Fall um, in dem zwei Pfade parallel zueinander laufen? Das ist, wenn die beiden Pfade keine ähnlichen Knoten haben, jedoch als „ähnlich“ angesehen werden, da ihre Wege sehr nahe beieinander in die gleiche Richtung gehen.

Vielen Dank

Answer 1

Die einfache Antwort lautet, dass dies eine sehr schwierige Frage ist und viel auf Ihre Definition dessen, was „ähnlich“ in einem Diagramm bedeutet, angewiesen ist. In den meisten Grafiken können Sie die Knoten von zwei disjunkten Pfaden planar neu ordnen, um "parallel" zu laufen.

Ein guter Ort, um sich mit fortgeschritteneren Ähnlichkeitsmetriken zu befassen Matrixähnlichkeit Algorithmen.

Bearbeiten: Beschränkung der Frage auf euklidische Grafiken

Es gibt zahlreiche aktive Untersuchungen zu dieser Frage, wenn die Domäne auf euklidische Grafiken einschränken, da dies ein anwendbares Thema für Bereiche wie GIS, maschinelles Lernen für Robotik und kollaborative Filterung in sozialen Netzwerken / künstlichen Netzwerken wie dem Web ist. Schauen Sie sich die Artikel an Google Scholar.