Avståndsfunktionen

Avståndsfunktionen är en funktion som tilldelar två element x och y från en mängd X ett icke-negativt tal som beskriver hur långt ifrån varandra dessa två element är. Vanligtvis betecknas den d(x, y) och d är definierad på X × X med värden i [0, ∞). Om d uppfyller de standardiserade axiomen för ett avstånd, säger man att X är ett metriskt rum.

Axiomen för ett avstånd (för alla x, y, z i X): 1) d(x, y) ≥ 0; 2) d(x, y) = 0 om och endast om x = y; 3) d(x, y) = d(y, x); 4) d(x, z) ≤ d(x, y) + d(y, z) (triangelolikheten). Om något av dessa villkor inte uppfylls kan man tala om pseudometrik eller semimetri.

Exempel: Den mest använda avståndsfunktionen i ℝⁿ är det euklidiska avståndet d(x, y) = ||x − y||₂ = sqrt(∑ (xi − yi)²). Andra vanliga avstånd är L1-avståndet d₁(x, y) = ∑ |xi − yi| och L∞-avståndet d∞(x, y) = max_i |xi − yi|. I grafteori definieras avståndet mellan två hörn som längden av kortaste vägen mellan dem, med icke-negativa kantvikter.

Följdvarianter inkluderar avstånd som härrör från en norm: d(x, y) = ||x − y||ₚ för p-normar; ultrametrik där d(x, z) ≤ max(d(x, y), d(y, z)) används i vissa hierarkiska sammanhang; pseudometrik där d(x, y) = 0 även om x ≠ y.

Användningar: avståndsfunktionen används inom klustring, närhetsberäkningar, närmaste grannar-sökning, geodesi på ytor, grafanalys och multidimensionell skalning. Den är grundläggande för konstruktioner som Voronoi-diagram och effektiva söksstrukturer.