- This topic has 5 תגובות, 2 משתתפים, and was last updated לפני 17 שנים, 11 חודשים by
.
-
תגובות
-
נגדיר מרחק-1 של נקודה מהישר כערך המוחלט של הפרש בציר האנכי. ז"א לכל נקודה
x1,y1
ולכל ישר
y=a*x+b
מרחק-1 הוא
| a*x1+b – y1 |
בהנתן שלוש נקודות במישור, מצא באופן יעיל את הישר הממזער את סכום מרחקי-1 של שלוש הנקודות ממנו.
דרך כל שלוש נקודות עובר קו ישר אחד – אם הנקודות מספיק עבות
אני טוען שמספיק להסתכל על שלושת הישרים העוברים דרך שתי נקודות כלשהן מבין השלוש, ולבדוק – מה המרחק-1 בין כל ישר לבין הנקודה שאינה עליו (בהנחה שיש כזו).
ההוכחה פשוטה ומסתמכת על אנליזה וקטורית – מסתכלים על הפונקציה הוקטורית
f(a,b) = | a x1 + b – y1 | + | a x2 + b – y2 | + | a x 3 + b – y3|
לפי משפט, אם יש מינימום שמתקבל בנק' בעלת סביבה גזירה חלקית לפי כל המשתנים, אז הגראדיאנט חייב להתאפס. ובכן:
grad f = ( x1 * sign | a x 1 + b – y1| + x2 * sign | … | + x3 * sign | … | , 1 * sign |…| + 1 * sign | … | + 1 * sign |….|) = (0,0)
ברור שהשני לא מתאפס (שכן פונקציית הסימן לא מקבלת 0 באף נקודה בה הפונקציה המדוברת גזירה).
מכאן שהמינימום חייב להתקבל באזור בו הפונקציה לא גזירה, כלומר שהישר חותך את אחת הנקודות. נניח לדוגמה שהישר חותך את הנקודה הראשונה. אז מתקיים
a x1 + b = y1
b = y1 – ax1
ונתבונן בפונקציה
g(a) = | a x2 + y1 – ax1 – y2 | + | a x3 + y1 – a x1 – y3|
שוב – הנגזרת חייבת להתאפס אם יש מינימום.
(x2-x1) sign | … | + (x3 – x2) sign |…| = 0
נשים לב כאן שהנקודות קבועות כרגע, ולכן אם הנגזרת מתאפסת מדובר בקשר מוזר של הנקודות, וזהו מקרה פרטי של הנקודות – לא מתקיים לכל a, ואם נחקור בטח נגלה שיוצא שהנקודות על ישר אחד או שפונקציית המרחק קבועה ביחס לa משהו מהסוג הזה, בכל אופן מקרים פרטיים הם למהנדסים ולא מעניינים רגע.
המינימום אם כך מתקבל בנקודות לא גזירות – כלומר שוב הישר חותך את אחת הנקודות, ובזה נסתיים נפנוף הידיים.הנימוק נכון אבל
א. יש הסבר יותר פשוט
ב. לא פתרת עד הסוף – הצעת אחד משלושה ישרים – אפשר לדעת מהו הישר הנכון.
מה רע בלבדוק מאיזה ישר המרחק מינימלי ולבחור אותו? סה"כ להציב במשוואה שלוש פעמים… נראה די פשוט.
לגבי ההסבר היותר פשוט, אתה מתכוון לזה שאם הוא בין שתי נקודות כלשהן, המרחק-1 מתקזז בין הנקודות? כלומר בהנתן שיפוע כלשהוא, סכום מרחקי-1 מכל שתי נקודות הוא שווה ללא תלות בהיסט של הישר (כל עוד הישר עובר בין שתי הנקודות), ולכן עדיף לבחור בהיסט שמעביר את הישר דרך הנקודה השלישית. אם יוצא שהישר לא עובר בין 2 הנקודות, אז מן הסתם יש שיפוע יותר טוב.לא בדקתי את זה, אבל יתכן שהישר הכי טוב עובר בין שתי הנקודות שההפרש בין ערכי האיקס שלהם הכי גדול בערך מוחלט?
פתרון שלם ונכון – אפשר להראות בסדרת צעדים פשוטה שהפתרון הוא הישר שמחבר את שתי הנקודות המרוחקות ביותר על ציר האיקס:
נתחיל בכך שכל ישר אפשר להזיז מעלה או מטה עד אשר יעבור דרך אחת הנקודות והדבר רק יקטין את המרחק-1;
נמשיך בסיבוב הישר כשהנקודה דרכה הוא עובר משמשת כציר (יש כיוון בו המרחק-1 לא גדל) עד אשר הישר עובר דרך שתי נקודות;
ונסיים בסיבוב כשהנקודה הקיצונית משמשת כציר (שוב – יש כיוון המקטין את מרחק-1 – ונקבל את הישר העובר דרך שתי הנקודות הקיצוניות.
ולכבוד פתירת החידה – נשלח חידה חדשה.
- יש להתחבר למערכת על מנת להגיב.