Čebyševova vzdálenost - Chebyshev distance

	A	b	C	d	E	F	G	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	A	b	C	d	E	F	G	h

Čebyševova vzdálenost mezi dvěma prostory na a šachy deska udává minimální počet tahů a král vyžaduje pohyb mezi nimi. Je to proto, že král se může pohybovat úhlopříčně, takže skoky k překonání menší vzdálenosti rovnoběžně s hodností nebo sloupem jsou účinně absorbovány do skoků pokrývajících větší. Nahoře jsou Chebyshevovy vzdálenosti každého čtverce od čtverce f6.

v matematika, Čebyševova vzdálenost (nebo Tchebychev vzdálenost), maximální metrikanebo L_∞ metrický^[1] je metrický definované na a vektorový prostor Kde vzdálenost mezi dvěma vektory je největší z jejich rozdílů v jakékoli dimenzi souřadnic.^[2] Je pojmenován po Pafnuty Čebyšev.

Je také známý jako vzdálenost šachovnice, protože ve hře šachy minimální počet tahů potřebný a král jít z jednoho čtverce na a šachovnice do jiné se rovná Čebyševova vzdálenost mezi středy čtverců, pokud mají čtverce boční délku jedna, jak je znázorněno v 2-D prostorových souřadnicích s osami zarovnanými k okrajům desky.^[3] Například vzdálenost Čebyševova mezi f6 a e2 se rovná 4.

Definice

Čebyševova vzdálenost mezi dvěma vektory nebo body X a yse standardními souřadnicemi ${ displaystyle x_ {i}}$ a ${ displaystyle y_ {i}}$, respektive je

${ displaystyle D _ { rm {Chebyshev}} (x, y): = max _ {i} (| x_ {i} -y_ {i} |). }$

To se rovná limitu L_str metriky:

${ displaystyle lim _ {p to infty} { bigg (} sum _ {i = 1} ^ {n} left | x_ {i} -y_ {i} right | ^ {p} { bigg)} ^ {1 / p},}$

proto je také známý jako L_∞ metrický.

Matematicky je Čebyševova vzdálenost a metrický vyvolané nadřazená norma nebo jednotná norma. Je to příklad injekční metrika.

Ve dvou rozměrech, tj. rovinná geometrie, pokud jsou body str a q mít Kartézské souřadnice${ displaystyle (x_ {1}, y_ {1})}$ a ${ displaystyle (x_ {2}, y_ {2})}$, jejich vzdálenost Čebyšev je

${ displaystyle D _ { rm {Chebyshev}} = max left ( left | x_ {2} -x_ {1} right |, left | y_ {2} -y_ {1} right | right ).}$

Podle této metriky a kruh z poloměr r, což je množina bodů s Čebyševovou vzdáleností r od středu je čtverec, jehož strany mají délku 2r a jsou rovnoběžné s osami souřadnic.

Na šachovnici, kde hráč používá a oddělený Čebyševova vzdálenost, spíše než souvislá, kruh o poloměru r je čtverec bočních délek 2r, měření od středů čtverců, a tedy každá strana obsahuje 2r+1 čtverce; například kruh o poloměru 1 na šachovnici je čtverec 3 × 3.

Vlastnosti

V jedné dimenzi všechny L_str metriky jsou stejné - jsou pouze absolutní hodnotou rozdílu.

Dvojrozměrný Vzdálenost na Manhattanu má „kruhy“, tj. sady úrovní ve formě čtverců se stranami délky √2r, orientovaný v úhlu π / 4 (45 °) k souřadným osám, takže rovinná Chebyshevova vzdálenost může být považována za ekvivalentní rotací a změnou měřítka na (tj. a lineární transformace of) planární vzdálenost na Manhattanu.

Tato geometrická ekvivalence mezi L₁ a L._∞ metriky nezobecňují na vyšší dimenze. A koule vytvořený pomocí Čebyševovy vzdálenosti jako metriky je a krychle přičemž každá plocha je kolmá na jednu z souřadnicových os, ale koule vytvořená pomocí Vzdálenost na Manhattanu je osmistěn: tyto jsou duální mnohostěn, ale mezi kostkami je pouze čtverec (a segment 1-rozměrné čáry) self-dual polytopes. Přesto je pravda, že ve všech konečných prostorech je L₁ a L._∞ metriky jsou navzájem matematicky dvojí.

Na mřížce (například na šachovnici) jsou body ve vzdálenosti Čebyševova bodu 1 Moore sousedství toho bodu.

Čebyševova vzdálenost je limitujícím případem objednávky -${ displaystyle p}$ Minkowského vzdálenost, když ${ displaystyle p}$ dosáhne nekonečno.

Aplikace

Čebyševova vzdálenost se někdy používá sklad logistika,^[4] protože účinně měří čas a mostový jeřáb trvá pohybem objektu (protože jeřáb se může pohybovat po ose xay současně, ale stejnou rychlostí podél každé osy).

Je také široce používán v elektronických CAM aplikacích, zejména v optimalizačních algoritmech pro tyto aplikace. Mnoho nástrojů, jako jsou plotrovací nebo vrtací stroje, fotoploter, atd. pracující v letadle, jsou obvykle ovládány dvěma motory ve směru x a y, podobně jako mostové jeřáby.^[5]

Viz také

• Kingův graf
• Jednotná norma
• Geometrie taxíku

Reference

externí odkazy