Document

離散数学
5. 距離
五島正裕
DATE
:
離散数学
距離空間
 距離 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(y, z) ≥ d(x, z)
d(x, y)
d(x, z)
 「寄り道すると遠い」
y
d(y, z)
z
離散数学
距離の例 (1/3)
y
 ユークリッド距離 (Euclidean distance)
x2  y2
O
x
離散数学
距離の例 (2/3)
 マンハッタン距離 (Manhattan
distance) ，街区距離
distance)
(cityblock
 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．
離散数学
3次元超立方体
z
111
1
y
1
110
100
O 000
x
1
4次元超立方体
1110
1111
1100
1000
0000
離散数学
離散数学
距離ではないもの
 距離の公理を満たさないものを「距離」とは呼ばない。
 ex) 「速さ一定で，x から y に行くまでにかかる時間」
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)
？一方通行とか
x
d(x, y)
？
d(x, z)
y
d(y, z)
z

Download Report