Русская Википедия:Расстояние редактирования графа

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Расстояние редактирования графа — это коэффициент сходства (или несходства) между двумя графами. Концепцию расстояния редактирования графа впервые сформулировали математически Альберто Санфелиу и Кинг-Сан Фу в 1983Шаблон:Sfn. Главное приложение расстояния редактирования графа — в Шаблон:Нп5, таких как устойчивое распознавание образов в машинном обученииШаблон:Sfn.

Расстояние редактирования графа между двумя графами связано с Шаблон:Нп5 между строками. При интерпретации сток как связных направленных ациклических графов с максимальной степенью два, классические определения расстояния редактирования, такие как расстояние ЛевенштейнаШаблон:Sfn, расстояние ХэммингаШаблон:Sfn и расстояние Джаро — Винклера, могут интерпретироваться как расстояния редактирования графов между подходящими графами. Подобным образом, расстояние редактирования графа является обобщением расстояния редактирования дерева между деревьями с корнямиШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.

Формальные определения и свойства

Математическое определение расстояния редактирования графа зависит от определения графов, для которых расстояние определяется. Например, оно зависит от того, размечены ли и как размечены вершины и рёбра графа, а также от того, является ли граф ориентированным. В общем случае, если дан набор операций редактирования графа (известных также как элементарные операции над графами), расстояние редактирования графа между двумя графами <math>g_{1}</math> и <math>g_{2}</math>, записываемое как <math>GED(g_{1},g_{2})</math>, можно определить как

<math> GED(g_{1},g_{2}) = \min_{(e_{1},...,e_{k}) \in \mathcal{P}(g_{1},g_{2})} \sum_{i=1}^{k} c(e_{i})</math>,

где <math>\mathcal{P}(g_{1},g_{2})</math> означает набор путей преобразования <math>g_{1}</math> в (изоморфный графу) <math>g_{2}</math>, а <math>c(e) \geqslant 0</math> равна стоимости каждой операции редактирования <math>e</math>.

Набор элементарных операций над графом обычно включает:

вставку вершины — в граф вставляется одна новая помеченная вершина.
удаление вершины — из графа удаляется одна (зачастую не связанная с другими) вершина.
подстановка вершины — изменение метки (или цвета) данной вершины.
вставка ребра — в граф вставляется новое цветное ребро между парой вершин.
удаление ребра — удаление одного ребра между парой вершин.
подстановка ребра — изменение метки (или цвета) данного ребра.

Кроме этого, но более редко, включаются такие операции, как разбиение ребра, при котором вставляется новая вершина в ребро (что приводит к образованию двух рёбер), и стягивание ребра, которое удаляет вершину степени два между рёбрами (одного цвета) с объединением двух рёбер в одно. Хотя такие сложные операции можно определить в терминах более простых преобразований, их использование позволяет лучше параметризовать функцию цены <math>c</math>, когда оператор дешевле, чем сумма его составляющих.

Приложения

Расстояние редактирования графа находит применение в распознавании рукописного вводаШаблон:Sfn, распознавании отпечатков пальцевШаблон:Sfn и хемоинформатикеШаблон:Sfn.

Алгоритмы и сложность

Точные алгоритмы вычисления расстояния редактирования графа между парой графов обычно преобразуют проблему в задачу поиска минимального пути преобразований между двумя графами. Вычисление оптимального пути редактирования сводится к поиску пути или задаче о кратчайшем пути, часто реализуемой как алгоритм поиска A*.

Кроме точных алгоритмов, известно много эффективных аппроксимационных алгоритмовШаблон:SfnШаблон:Sfn.

Несмотря на то, что вышеупомянутые алгоритмы работают на практике иногда хорошо, в общем случае задача вычисления расстояния редактирования графа является NP-полнойШаблон:Sfn (доказательство этого доступно в разделе 2 на сайте Zeng et al.) и даже трудна для аппроксимации (формально, она APX-труднаШаблон:Sfn).

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Расстояние_редактирования_графа&oldid=10682664