Есть ли классический алгоритм преобразования одного дерева (или графа) в другое за минимальное количество шагов? - PullRequest
Новая
       54

Есть ли классический алгоритм преобразования одного дерева (или графа) в другое за минимальное количество шагов?

0 голосов
/ 07 мая 2020

Допустим, у меня есть два графика (в данном случае деревья): 

graph 1:
    root
        child_1
            leaf_1, leaf_2, leaf_3
        child_2
            leaf_1, leaf_2, leaf_4

graph 2:
    root
        child_1
            leaf_2, leaf_4
        child_2
            leaf_2, leaf_3

И я хочу найти минимальную последовательность шагов для преобразования из graph 1 в graph 2.
I есть как минимум два варианта: 

  1.  child_1.delete(leaf_1)
 child_1.delete(leaf_3)
 child_1.add   (leaf_4)

 child_2.delete(leaf_1)
 child_2.delete(leaf_4)
 child_2.add   (leaf_3)

  2.  child_1.delete(leaf_1)

 child_2.delete(leaf_1)

 root  .delete(child_1)
 root  .append(child_1)

Итак, как мне найти минимальную последовательность в общем случае?

1 Ответ

1 голос
/ 04 августа 2020

Это связано с проблемой Graph Edit Distance (GED) ( 1 , 2 ).

Это NP- сложная задача ( 3 ): 

Therefore, graph edit distance can also be used to determine the subgraph isomorphism which is NP-Complete.
Then we can derive the following lemma.

Lemma 2.3. GED problem is NP-Hard.

Точные алгоритмы вычисления GED обычно основаны на алгоритме поиска A * ( 3 ):

Наиболее широко используемый метод вычисления точного расстояния редактирования графа основан на хорошо известном алгоритме A *

Существуют также полиномиальные приближенные / эвристические c алгоритмы ( 1 ):

Большинство из них имеют куб. c время вычислений

Для реализации алгоритмов я предлагаю искать «расстояние редактирования графа» at Github .

Ссылки:

...