¿Determinar si esta d es una métrica?

Question

Supongamos que tenemos una función $d:\mathbb{Z}^{2}\times\mathbb{Z}^{2}\rightarrow\mathbb{R}$ donde $\forall(x_{0},y_{0}),(x_{1},y_{1})\in \mathbb{Z}^{2}$ , tenemos..

$d\left( \left( x_{0},y_{0} \right), \left( x_{1},y_{1} \right) \right)\;\;=\;\;\left| \left| x_{1}-x_{0} \right| - \left| y_{1}-y_{0} \right| \right|\;\;+\;\;\sqrt{2}\cdot \min \left \{ \left | x_{1}-x_{0} \right | , \left | y_{1}-y_{0} \right |\right \}$

Estoy tratando de determinar si $d$ es una métrica en $\mathbb{Z}^{2}$ y estoy un poco atascado en la desigualdad del triángulo.

Gráficamente, pienso en esta d como algo intermedio entre la distancia euclidiana y la de Manhattan;

He creado un modelo de esta función en geogebra:

El texto en negrita pasará a decir "Contraejemplo" una vez que la desigualdad falle cuando movamos los 3 puntos. El archivo de geogebra está cargado aquí (8kb). Hasta ahora, no se ha encontrado ningún contraejemplo.

---

Dejando de lado el problema algebraico, utilizaré este $d$ como heurística en un algoritmo de búsqueda A*, así que ¿cuál sería la importancia, si es que hay alguna, de $d$ siendo una métrica (si es que lo es) (a diferencia de una asignación arbitraria de números para una heurística, digamos)?

Answer 1

Sugerencia: deje que $d_1$ y $d_2$ sean dos métricas sobre el mismo espacio métrico $X$ con $\lambda>0$ .

Entonces

$$\lambda d_1, \lambda d_2\text{are both metrics }. $$ $$ d_1+d_2\text{is a metric }. $$

En particular, $d:=d_1+\lambda d_2$ es una métrica.

Answer 2

Reformulamos la función como sigue:
El primer término (la diferencia entre las 2 longitudes laterales del rectángulo formado por los 2 puntos) puede expresarse como la diferencia entre el máximo de las 2 longitudes laterales y el mínimo. $$d_{K}((x_{0},y_{0}),(x_{1},y_{1})) = \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} - \min \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + \sqrt{2} \cdot \min \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$$ $$d_{K} = \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + (\sqrt{2} - 1) \cdot \min \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$$ Utilizando $\min \{ a, b\} = a + b - \max \{ a ,b\}$ : $$= \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + (\sqrt{2} - 1) \cdot (|x_{1}-x_{0}| + |y_{1}-y_{0}| - \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \})$$ $$= (\sqrt{2} - 1) \cdot d_{M} + \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + (1 - \sqrt{2}) \cdot \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$$ $$= (\sqrt{2} - 1) \cdot d_{M} + (2 - \sqrt{2}) \cdot \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$$ donde $d_{M}$ es la métrica de Manhattan.
Nota $\sqrt{2} - 1 > 0$ y $2-\sqrt{2} > 0$
Basta con demostrar que $d((x_{0},y_{0}),(x_{1},y_{1})) := \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \}$ es una métrica.

---

La simetría y la definición positiva son fáciles.
Mostramos la desigualdad de los triángulos mediante el análisis de casos. Objetivo: $$d((x_{0},y_{0}),(x_{2},y_{2})) \leq d((x_{0},y_{0}),(x_{1},y_{1})) + d((x_{1},y_{1}),(x_{2},y_{2}))$$ $$\max \{ |x_{2}-x_{0}|,|y_{2}-y_{0}| \} \leq \max \{ |x_{1}-x_{0}|,|y_{1}-y_{0}| \} + \max \{ |x_{2}-x_{1}|,|y_{2}-y_{1}| \}$$ Primero demostramos que $\max \{ a+b, c+d \} \leq \max \{ a,c \} + \max \{ b,d \}$ para los no negativos $a,b,c,d$ . Este es el análisis del caso. Luego, el resto es fácil de entender.

.
Para cada $\max \{ .. \}$ , obtenemos 2 casos, por lo que lo anterior nos da $2^{3}$ casos.
2 resultará satisfecho con la igualdad
2 son contradicciones,
y el resto se conforma con $\leq$ .

---

Así que entonces $d_{K}$ es una combinación lineal de 2 métricas, por lo que es una métrica.