algorithm - online - levenshtein distance python




Изменить расстояние между двумя графиками (3)

Вы должны посмотреть на статью . Обзор расстояния редактирования графа

Мне просто интересно, как, например, для строк, где у нас есть расстояние Левенштейна (или расстояние редактирования) между двумя строками, есть ли что-то подобное для графиков?

Я имею в виду скалярную меру, которая идентифицирует количество атомных операций (вставка и удаление узлов и ребер), чтобы преобразовать граф G1 в граф G2 .


Для общего графика это NP-полная проблема, как упоминалось в их ответе. Но для древовидного графика существуют хорошо известные полиномиальные алгоритмы. Может быть, самым известным из них является алгоритм «Чжан Шаша», который был опубликован в 1989 году.


Я думаю, что расстояние редактирования графика - это мера, которую вы искали.

Расстояние редактирования графика измеряет минимальное количество операций редактирования графа для преобразования одного графика в другой, а разрешенные операции редактирования графа включают в себя:

  • Вставка / удаление изолированной вершины
  • Вставить / удалить ребро
  • Измените метку вершины / ребра (если обозначены графы)

Однако вычисление расстояния редактирования графика между двумя графиками NP-hard. Наиболее эффективным алгоритмом для вычисления этого является алгоритм, основанный на A *, и существуют другие субоптимальные алгоритмы.







edit-distance