מרחק צ'בישב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

מרחק צ'בישב (או מטריקת מקסימום או מטריקת L) הוא מטריקה המוגדרת על מרחב וקטורי בו המרחק בין שני וקטורים הוא ההפרש המקסימלי המתקבל בין הקואורדינטות שלהם בממדים השונים. הוא קרוי על-שם פפנוטי צ'בישב.

מרחק צ'בישב גם ידוע כמרחק השחמט: הוא שווה למספר הצעדים המינימלי שהמלך עושה בלוח שחמט כדי להגיע למשבצת כלשהי (המלך יכול לנוע אופקית, אנכית ובאלכסון). למשל המרחק בין ו5 ל ו1 או ב1 הוא: 4.

8 Chess l44.png Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png
7 Chess d44.png Chess l44.png Chess d44.png ‏2 משבצות‏ ‏2 משבצות‏ ‏2 משבצות‏ ‏2 משבצות‏ ‏2 משבצות‏
6 Chess l44.png Chess d44.png Chess l44.png ‏2 משבצות‏ תבנית:שחמט/שם כלי/x1 תבנית:שחמט/שם כלי/x1 תבנית:שחמט/שם כלי/x1 ‏2 משבצות‏
5 Chess d44.png Chess l44.png Chess d44.png ‏2 משבצות‏ תבנית:שחמט/שם כלי/x1 מלך לבן תבנית:שחמט/שם כלי/x1 ‏2 משבצות‏
4 Chess l44.png Chess d44.png Chess l44.png ‏2 משבצות‏ תבנית:שחמט/שם כלי/x1 תבנית:שחמט/שם כלי/x1 תבנית:שחמט/שם כלי/x1 ‏2 משבצות‏
3 Chess d44.png Chess l44.png Chess d44.png ‏2 משבצות‏ ‏2 משבצות‏ ‏2 משבצות‏ ‏2 משבצות‏ ‏2 משבצות‏
2 Chess l44.png Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png Chess l44.png Chess d44.png
1 Chess d44.png תבנית:שחמט/שם כלי/x4 תבנית:שחמט/שם כלי/x4 Chess l44.png תבנית:שחמט/שם כלי/x4 תבנית:שחמט/שם כלי/x4 Chess d44.png Chess l44.png
א ב ג ד ה ו ז ח

במטריקה זו, מעגל ברדיוס r, הוא קבוצת הנקודות עם מרחק צ'בישב r מנקודת המרכז. צורת המעגל כאן היא ריבוע שצלעותיו באורך 2r והן מקבילות למערכת הצירים של הקואורדינטות. בלוח שחמט בו נעשה שימוש במרחק צ'בישב דיסקרטי ולא רציף, מעגל עם רדיוס r הוא ריבוע שצלעו 2r (יש למדוד ממרכז המשבצת למרכז המשבצת ולא את המשבצות עצמן). מספר המשבצות בכל צלע הוא 2r+1. למשל עיגול עם רדיוס 1 בלוח שחמט יהיה ריבוע עם 3×3 משבצות.

הגדרה[עריכת קוד מקור | עריכה]

מרחק צ'בישב בין שני וקטורים או נקודות p ו q עם קואורדינטות ו בהתאמה הוא:

בשני ממדים, כלומר בגאומטרית המישור, אם לנקודות p ו q יש קואורדינטות קרטזיות ו אז מרחק צ'בישב שלהן הוא:

השוואה בין מטריקות מרחק צ'בישב ומרחק מנהטן[עריכת קוד מקור | עריכה]

במימד אחד, כל המטריקות שווה היות שהן הערך המוחלט של ההפרש.

בשני ממדים קיימת שקילות בין מרחק צ'בישב למרחק מנהטן:

  • בשניהם צורת המעגל היא ריבוע.
  • במרחק צ'בישב הריבוע מקביל לצירי הקואורדינטות ובמרחק מנהטן הוא בזווית π/4 ‏ (45°) אליהן.
  • אורך הצלע שונה: במרחק צ'בישב הוא 2r ואילו במרחק מנהטן 2r√.

ניתן לראות את השקילות של שניהם במישור על ידי סיבוב והכפלה בקבוע.

אולם לא ניתן להכליל שקילות זו לשלושה ממדים ויותר: ספירה הנוצרת על ידי שימוש במרחק צ'בישב כמטריקה, תיצור קובייה שפאותיה ניצבות לאחד מצירי הקואורדינטות, בעוד שהספירה הנוצרת על ידי שימוש במרחק מנהטן יוצרת אוקטהדרון. אלה הם פאונים דואלים עם תכונות שונות.

שימושים[עריכת קוד מקור | עריכה]

מרחק צ'בישב משמש בלוגיסטיקה של מחסנים היות שהוא מודד היטב את הזמן הנדרש לעגורן גשר להעביר חפצים מנקודה לנקודה. העגורן יכול לנוע בציר ה x או ה y או באלכסון אך בכל המקרים מהירותו זהה.

על רשת (כמו לוח השחמט) הנקודות הנמצאות במרחק צ'בישב 1 מנקודה נתונה מהווים את סביבת מור של אותה נקודה.