Ulam距離 (Ulam distance)

順序 \(A{\succ}B{\succ}C{\succ}D\) を例に説明する.ここで,D を2番目に動かす.このとき,D を A と B の間に挿入すると,B や C は下に押し出されて \(A{\succ}D{\succ}B{\succ}C\) になる. 一方の順序を,この手続きによってもう一方の順序に変換するとき,その最小変換回数がUlam距離

Ulam距離は距離の公理をみたすmetric. 完全に一致するとき最小値 0,互いに逆順序のときに最大値をとる.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:26