Sari la conținut

Distanță Cebîșev

De la Wikipedia, enciclopedia liberă
abcdefgh
8
a8 five
b8 four
c8 three
d8 two
e8 two
f8 two
g8 two
h8 two
a7 five
b7 four
c7 three
d7 two
e7 one
f7 one
g7 one
h7 two
a6 five
b6 four
c6 three
d6 two
e6 one
f6 white king
g6 one
h6 two
a5 five
b5 four
c5 three
d5 two
e5 one
f5 one
g5 one
h5 two
a4 five
b4 four
c4 three
d4 two
e4 two
f4 two
g4 two
h4 two
a3 five
b3 four
c3 three
d3 three
e3 three
f3 three
g3 three
h3 three
a2 five
b2 four
c2 four
d2 four
e2 four
f2 four
g2 four
h2 four
a1 five
b1 five
c1 five
d1 five
e1 five
f1 five
g1 five
h1 five
8
77
66
55
44
33
22
11
abcdefgh
Distanța Cebîșev dintre două câmpuri (pătrate) de pe o tablă de șah dă numărul minim de mișcări de care are nevoie un rege pentru a se deplasa de la unul la celălalt. Acest lucru se datorează faptului că un rege se poate mișca în diagonală, astfel încât unele mișcări paralele cu rândurile sau coloanele, pe o distanță mai mică, să fie comasate efectiv în mișcările pe diagonală, mai lungi. În imagine sunt distanțele Cebîșev ale fiecărui câmp față de câmpul f6.

În matematică, distanța Cebîșev, metrică maximă sau metrică L[1] este o metrică definită într-un spațiu vectorial unde distanța dintre doi vectori este valoarea cea mai mare dintre diferențele dintre ei de-a lungul oricărei coordonate.[2] Este numită astfel după Pafnuti Cebîșev.

Este cunoscută și ca distanța pe tabla de șah, deoarece în jocul de șah numărul minim de mutări necesare unui rege pentru a se deplasa de pe un câmp (pătrat) al tablei de șah pe altul este echivalent cu distanța Cebîșev dintre centrele acestor câmpuri, considerate ca având latura egală cu unitatea, iar coordonatele sunt pentru două dimensiuni și sunt aliniate cu laturile tablei.[3] De exemplu, distanța Cebîșev dintre câmpurile f6 și e2 este 4 (v. figura de alături).

Distanța Cebîșev între două puncte x and y, cu coordonatele standard și respectiv este

Aceasta este egală cu limita metricii spațiului Lp:

prin urmare este cunoscută și ca metrica L.

Matematic, distanța Cebîșev este o metrică generată de norma uniformă (norma supremum). Este un exemplu de metrică injectivă.

În două dimensiuni, adică în geometria plană, dacă punctele p și q au coordonatele carteziene și , distanța lor Cebîșev este

În această metrică, un cerc cu raza r, care este mulțimea punctelor cu distanța Cebîșev r față de centru, este pătratul ale cărui laturi au lungimea 2r și sunt paralele cu axele de coordonate.

Pe o tablă de șah, unde se folosește o distanță Cebîșev „discretă” în loc de una continuă, cercul de rază "r" este un pătrat cu lungimea laturilor 2r, măsurată între centrele câmpurilor de pe tablă, astfel fiecare parte conține 2r + 1 câmpuri; de exemplu, cercul de rază 1 pe o tablă de șah este un pătrat de 3×3 câmpuri.

Proprietăți

[modificare | modificare sursă]

Într-o singură dimensiune, toate metricile Lp sunt egale — ele sunt valorile absolute ale diferențelor.

Distanța Manhattan bidimensională are „cercuri” adică linii de nivel sub formă de pătrate, cu laturile de lungime 2r, orientate la unghiul de (45°) față de axele de coordonate, astfel încât distanța Cebîșev din plan poate fi privită ca echivalentă prin rotație și scalare (adică printr-o transformare liniară) cu distanța Manhattan din plan.

Totuși, această echivalență geometrică între valorile L1 și L nu se generalizează pentru dimensiuni superioare. O sferă formată folosind ca metrică distanța Cebîșev este un cub cu fiecare față perpendiculară pe una dintre axele de coordonate, dar o sferă formată folosind distanța Manhattan este un octaedru: acestea sunt poliedre duale, dar dintre cuburi, numai pătratul (și segmentul de dreaptă, unidimensional) sunt politopuri autoduale. Însă este adevărat că în toate spațiile cu dimensiuni finite metricile L1 și L sunt matematic duale între ele.

Pe o grilă (cum ar fi o tablă de șah), punctele aflate la o distanță Cebîșev de 1 de un punct sunt vecinătatea Moore al acelui punct.

Distanța Cebîșev este cazul limită al distanței Minkowski de ordinul p când p tinde la infinit.

Distanța Cebîșev este uneori folosită în logistica depozitelor,[4] întrucât măsoară efectiv timpul necesar unei macarale pentru a muta un obiect (deoarece macaraua se poate deplasa pe axele x și y în același timp, dar cu aceeași viteză de-a lungul fiecărei axe).

Este, de asemenea, utilizat pe scară largă în aplicațiile privind fabricația asistată de calculator (în engleză Computer-aided manufacturing – CAM), în special în algoritmii de optimizare a acestora. Multe mașini-unelte, cum ar fi mașinile de trasat sau găurit, plottere etc., care funcționează în plan, sunt de obicei acționate de două motoare în direcțiile x și y, asemănător cu podurile rulante.[5]

  1. ^ en Cyrus. D. Cantrell (). Modern Mathematical Methods for Physicists and EngineersNecesită înregistrare gratuită. Cambridge University Press. ISBN 0-521-59827-3. 
  2. ^ en James M. Abello, Panos M. Pardalos, and Mauricio G. C. Resende (editors) (). Handbook of Massive Data Sets. Springer. ISBN 1-4020-0489-3. 
  3. ^ en David M. J. Tax; Robert Duin; Dick De Ridder (). Classification, Parameter Estimation and State Estimation: An Engineering Approach Using MATLAB. John Wiley and Sons. ISBN 0-470-09013-8. 
  4. ^ en André Langevin; Diane Riopel (). Logistics Systems. Springer. ISBN 0-387-24971-0. 
  5. ^ en Seitz, Charles L. (). Advanced Research in VLSI: Proceedings of the Decennial Caltech Conference on VLSI, March 1989. ISBN 9780262192828.