圖編輯距離

喺數學同電腦科學裡邊，圖編輯距離（英文：graph edit distance，GED）係用嚟量度兩幅圖有幾相似，係 1983年由Alberto Sanfeliu同傅京孫首先將呢個概念用數學表達出嚟。一個主要嘅功用係做非精確圖配對（inexact graph matching），例如機械學習入邊嘅容錯規律辨識。 圖編輯距離同字串編輯距離有啲關係。如果將字串睇做連通、有向無環、最大度一嘅圖嘅話，各種經典嘅距離例如Levenshtein距離、漢明距離、Jaro-Winkler距離都可以睇做某一類圖嘅圖編輯距離，另外，圖編輯距離亦都係樹編輯距離嘅廣義化。

定義同性質

圖編輯距離嘅定義好取決於用緊邊一種圖，例如圖嘅邊、頂點有無標號，點樣標號，啲邊有無方向等等。一般嚟講，畀一柞圖編輯操作（graph edit operation，又叫基礎圖操作elementary graph operation），兩幅圖$g_{1}$同$g_{2}$之間嘅圖編輯距離$GED(g_{1},g_{2})$定義係

$GED(g_{1},g_{2})=\min _{(e_{1},\ldots ,e_{k})\in {\mathcal {P}}(g_{1},g_{2})}\sum _{i=1}^{k}c(e_{i})$

呢度${\mathcal {P}}(g_{1},g_{2})$裝住所有由圖$g_{1}$去圖$g_{2}$嘅編輯路徑，$c(e)\geq 0$係圖編輯操作 $e$ 嘅成本。

基本圖操作一般包括頂點同邊嘅加插（insertion）、刪除（deletion）同改標號（substitution）。另外仲可能包埋加插一粒頂點落一條邊中間嘅裂邊（edge splitting）同移除一粒度二嘅頂點嘅合邊（edge contraction）。雖然好多複雜嘅操作都可以用簡單嘅嘅操作複合而成，不過包埋呢啲複雜操作嘅話，如果佢嘅成本比啲簡單操作加埋仲少，就會有一個精細啲嘅成本函數。

基礎圖編輯操作嘅深入研究可以喺（Serratosa, Cortés 2015）、（Serratosa 2019）、（Serratosa 2021）到搵到。

有一啲方法可以自動計算呢啲基礎圖編輯操作，甚至有啲係喺網上邊學。

應用

圖編輯距離可以用喺手寫辨識、指紋辨識同化學資訊學。

演算法同複雜度

計算圖編輯距離嘅精確演算法通常係將條問題睇做「去搵最短嘅編輯路徑」，即係諗做一條最短路徑問題，之後用A* 搜尋演算法做。

精確演算法以外，有一啲高效嘅估算演算法，大部份都係行立方時間 。甚至有行綫性時間嘅。

雖然以上講嘅演算法喺實際用途嚟講係行得到，但其實搵圖編輯距離呢個問題係NP-難嘅（網上證明，睇Zeng et al.嘅第二節），甚至係難以估算嘅（APX-難）。