離散数学

離散数学
4. 距離
五島正裕
離散数学
距離空間
 距離 d
 「距離の公理」を満たす写像 d: X × X → R

X ：距離空間
 距離の公理
 任意の x, y, z ∈ X に対し
1.
d(x, y) = d(y, x)
2.
d(x, y) ≥ 0
3.
d(x, y) = 0 ⇔ x = y
4.
d(x, y) + d(y, z) ≥ d(x, z)
三角不等式
 同じ集合に異なる「距離」を定義することも可能
離散数学
三角不等式 (triangle inequality)
x
d(x, y)
 d(x, y) + d(y, z) ≥ d(x, z)
 「寄り道すると遠い」
d(x, z)
y
d(y, z)
z
離散数学
距離の例 (1/3)
y
 ユークリッド距離
distance)
(Euclidean
x2  y2
O
x
離散数学
距離の例 (2/3)
 マンハッタン距離 (Manhattan
distance) ，街区距離 (cityblock
distance)
 d(a, b) = |ax − bx| + |ay − by|

LSI上の直交配線の配線長
など
4
3
1
2
離散数学
距離の例 (3/3)
 ハミング距離 (Hamming distance)
 ふたつの等長の記号列
u = u1 … un
v = v1 … vn
に対し、対応する位置にある記号 (uk, vk) の対で異なるものの数
 例）

1100 と 0101 のハミング距離は 2．
離散数学
距離ではないもの
 距離の公理を満たさないものを「距離」とは呼ばない。
 「早さ一定で，x から y に行くまでにかかる時間」

Download Report