רוטר - חידה/שאלה מעניינת (עדיין פתוח !).

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"חידה/שאלה מעניינת (עדיין פתוח !)."

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15746	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 15746

Deuce
חבר מתאריך 1.9.08
6225 הודעות

10:29 02.03.10

חידה/שאלה מעניינת (עדיין פתוח !).

ערכתי לאחרונה בתאריך 13.03.10 בשעה 20:42 בברכה, Deuce

מי שמכיר את הפתרון, נא לא להגיב. מדובר שאלה יחסית אלמנטרית, אך יפה, בהשראת גיאומטריה חישובית.
דרגת הקושי סביר.
השאלה:
בהנתן אוסף S של נקודות במישור, יש להחזיר את המרחק הקצר ביותר בין 2 נקודות כלשהן.
(לא פתרון טריוויאלי ב-n^2)

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
אתה מתכוון לפתרון של O(n) ?	MiP	06.03.10 22:18	1
קשה לי להאמין שתצליח כל כך מהר.	Deuce	07.03.10 21:23	2
זאת הסיבוכיות של רוב הדברים בגיאומטריה חישובית ;)	Nokia	08.03.10 00:52	3
מאוד מעניין המקצוע, נכון?	Deuce	09.03.10 16:44	4
האמת אחד הקורסים היותר מעניינים שהיו לי השנה..	Nokia	11.03.10 02:31	14
אני חושב שפתרתי אבל אני אתן צ'אנס לאחרים	Net_Boy	09.03.10 21:43	5
הרמתי ידיים :\|	פאביו ג'וניור	09.03.10 23:40	6
לדעתי זה ממש חבל בשבילך.	Deuce	10.03.10 02:49	8
ברור אני מסכים איתך ב100% אני צריך לחזור לראש הזה...	פאביו ג'וניור	10.03.10 09:16	10
ד''א רק בשביל הפרוטוקול	פאביו ג'וניור	10.03.10 12:04	12
אני יודע שקיים פתרון ע''י הסבה לאלגוריתמים בתורת הגרפים	ldan192	09.03.10 23:49	7
מכתב	Deuce	10.03.10 03:00	9
אני אסתכל על זה אז בסופ''ש אם אף אחד לא יענה עד אז	ldan192	10.03.10 11:52	11
ניסיון לפיתרון	Net_Boy	11.03.10 01:26	13
היוריסטיקה פה מספיק טובה, אני מקבל את הפתרון.	Deuce	11.03.10 16:59	15
אם תוכל להביא הסבר יותר מסודר אני ישמח :)	פאביו ג'וניור	11.03.10 18:18	17
יפה, אהבתי =]	ronen333	11.03.10 17:20	16
אהבתי! בקיצור, יוצרים חתך במישור	ldan192	12.03.10 21:11	18
היוריסטיקה פה לא מספיק טובה.	Deuce	13.03.10 20:42	19
אני מאמין ש-sparse hypeplane יפתור בקלות את הנקודה	ldan192	14.03.10 11:51	20
מכתב	Deuce	15.03.10 03:15	21
אני מתכוון שע''י המרה לספארס אפשר ב-(O(nlogn	ldan192	15.03.10 11:43	22

MiP
חבר מתאריך 24.5.05
782 הודעות

22:18 06.03.10

1. אתה מתכוון לפתרון של O(n) ?
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

21:23 07.03.10

2. קשה לי להאמין שתצליח כל כך מהר.
בתגובה להודעה מספר 1

אני אישית יודע לפתור ב-nlog n.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Nokia
חבר מתאריך 1.7.02
538 הודעות

00:52 08.03.10

3. זאת הסיבוכיות של רוב הדברים בגיאומטריה חישובית ;)
בתגובה להודעה מספר 2

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

16:44 09.03.10

4. מאוד מעניין המקצוע, נכון?
בתגובה להודעה מספר 3

אגב - אתה בטח יודע איך לפתור, לא? זאת גם לא בעייה קשה נחשבת.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Nokia
חבר מתאריך 1.7.02
538 הודעות

02:31 11.03.10

14. האמת אחד הקורסים היותר מעניינים שהיו לי השנה..
בתגובה להודעה מספר 4

וכן אני יודע...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

21:43 09.03.10

5. אני חושב שפתרתי אבל אני אתן צ'אנס לאחרים
בתגובה להודעה מספר 0

אם לא יפרסמו פיתרון עד יום חמישי אני אפרסם את הפיתרון שלי

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

פאביו ג'וניור

23:40 09.03.10

6. הרמתי ידיים :|
בתגובה להודעה מספר 0

אני כבר לא בראש הזה... זה ממש מפריע לי שהראש שלי כבר רק בקטע של דיזיין ולא בזה :\

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

02:49 10.03.10

8. לדעתי זה ממש חבל בשבילך.
בתגובה להודעה מספר 6

סה"כ כמובן שאי אפשר להיות ספץ בכל תחום (או לפחות קשה מאוד), אבל אני נורא ממליץ למתכנת לדעת גם על מבני נתונים בסיסיים כמו עצים מאוזנים, ערימות, לדעת על גרפים בקצרה, מיונים וכד'. אני חושב שזה מקנה חשיבה טובה יותר למתכנת. אח"כ אתה מתכנת דברים אלמנטרים בצורה לא יעילה וזה פשוט לא מספיק טוב.
אני לא אומר שתעצב patterns בצורה מושלמת וסימולטנית תפתור בעיות מפוצצות בגיאומטריה חישובית (שמשלבות לכל הפחות מושגים כמו דיאגרמות וורונוי וקמור), אבל קח בחשבון ששווה לך שכשתתקל בבעייה כמו שהבאתי, יהיה לך כיוון כלשהו (או מספר כיוונים) - פתרון לא תמיד מגיע בקלות, אבל חשוב שיהיה כיוון כלשהו.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

פאביו ג'וניור

09:16 10.03.10

10. ברור אני מסכים איתך ב100% אני צריך לחזור לראש הזה...
בתגובה להודעה מספר 8

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

פאביו ג'וניור

12:04 10.03.10

12. ד''א רק בשביל הפרוטוקול
בתגובה להודעה מספר 10

את המבנים שאמרת אני מכיר..
פשוט לא עשיתי בהם שימוש תקופה ארוכה..
שוב זה מתיסכול שלא נגעתי בזה כי כמעט ולא יוצא לגעת בכאלה דברים :\

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

23:49 09.03.10

7. אני יודע שקיים פתרון ע''י הסבה לאלגוריתמים בתורת הגרפים
בתגובה להודעה מספר 0

אבל אני לא זוכר אותו.
מה שכן האינטואיציה אומרת לי זה פיתגורס, כלומר למיין לפי x^2+y^2,
ליצור מערך הפרשים (בין 2 תאים),
למיין אותו גם,
ואז התשובה המינימלית יתכן שהיא הפתרון.

אני סתם זרקתי את זה על רגל אחת.לא התעמקתי, אבל אני מאמין שזה יכול להיות כיוון לפתרון.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

03:00 10.03.10

9. מכתב
בתגובה להודעה מספר 7

קיים פתרון ע"י הסבה לגרפים? לא עולה לי לראש כיצד, אם כי אשמח לשמוע על אינטואיציה. קודם כל, המרת הבעייה לגרף תיקח n^2 אבל בוא נניח שהבעייה מיוצגת בגרף, גרף מלא לא מכוון אפילו כך שעל כל קשת בין 2 קודקודים מופיע המרחק בין 2 הקודקודים. כעת אנחנו רוצים למצוא את המרחק הקצר ביותר בין 2 נקודות. הרצת דייקסטרה או משהו בסגנון לא תעזור ממש (וגם העלות היא לפחות O של מספר הקשותות שבמקרה זה היא n^2). אני חושב שקיים פיתרון ע"י הסבה לדיאגרמת וורונוי אבל לא רוצה להכנס לזה.
לגבי פיתגורס - כבודו במקומו מונח, אבל פיתגורס זה פיתגורס; זה לא ממש עוזר פה. ומערך הפרשים יעלה לנו n^2 תאים (יש n בחר 2 זוגות).

בכל מקרה, אשמח לעוד רעיונות והצעות ממך

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

11:52 10.03.10

11. אני אסתכל על זה אז בסופ''ש אם אף אחד לא יענה עד אז
בתגובה להודעה מספר 9

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

01:26 11.03.10

13. ניסיון לפיתרון
בתגובה להודעה מספר 0

נמיין את הנקודות במישור לפי ציר ה X שלהן ע"י מיון אופטימלי (nlogn)
נגדיר פונקציה רקורסיבית שבכל שלב מחלקת את המישור ל-2 חלקים על פי ציר ה-x.
בכל שלב ברקורסיה נמצא את המרחק המינימלי בין הנקודות שבחלק השמאלי לבין הנקודות שבחלק הימני ע"י האלגוריתם הבא:
נגדיר 2 מצביעים אחד מצביע לאיבר האמצעי ואחד לאיבר לפניו (לצורך העניין והפשטות נניח שתמיד זה מתחלק ככה)
נחשב את המרחק.
נטייל עם המצביעים ימינה או שמאלה עד שנמצא מרחק גדול יותר מהמינימום או שנגיע לגבולות המערך.
בסופו של דבר המינימום יהיה המינימום מבין המספר שמצאנו ובין התוצאות של התת מערך הימני והתת מערך השמאלי.

הנוסחאת נסיגה תהיה T(n) = 2t(n/2) + O(n) ולכן על פי משפט האב אנחנו עומדים בדרישות התרגיל

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

16:59 11.03.10

15. היוריסטיקה פה מספיק טובה, אני מקבל את הפתרון.
בתגובה להודעה מספר 13

אם מישהו לא הבין את הפתרון, שיגיד ואני אבהר אותו קצת
בכל אופן, ח"ח לעומר

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

פאביו ג'וניור

18:18 11.03.10

17. אם תוכל להביא הסבר יותר מסודר אני ישמח :)
בתגובה להודעה מספר 15

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

17:20 11.03.10

16. יפה, אהבתי =]
בתגובה להודעה מספר 13

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

21:11 12.03.10

18. אהבתי! בקיצור, יוצרים חתך במישור
בתגובה להודעה מספר 13

ומשווים את המרחקים משמאל לאלו שמימין
ואז ממשיכים רקורסיבית לכל חתך עם חתכים שלו והאיברים באותו החתך.

רעיון באמת פשוט ואלגנטי.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

20:42 13.03.10

19. היוריסטיקה פה לא מספיק טובה.
בתגובה להודעה מספר 13

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

האתגר נשאר פתוח. אם אף אחד לא יצליח, אני אציג לכם 2 פתרונות שונים.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

11:51 14.03.10

20. אני מאמין ש-sparse hypeplane יפתור בקלות את הנקודה
בתגובה להודעה מספר 19

הבעייתית שאתה מצביע עליה.
בכל מקרה, אני עדיין בטוח שיש אלגוריתם קצת שונה (אבל לא בהרבה) ממש שעומר הזכיר, שמחלק את המישור לקוביות רקורסיבית (לתתי קבוצות), מגיע לגודל קוביה שהוא קבוע, מבצע חישוב מרחק קצר שהוא קבוע ואז מזה בונים גרף מהרכיבים האלה (אני חושב שאפשר גם ע"י איחוד תתי הקבוצות במקום), כך שהגרף הוא בעצם גרף כוכב ומשם כבר לא בעיה למצוא את המרחק הקטן ביותר.

אם אזכר בשם של האלגוריתם פה אני אציין אותו פה בהמשך.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות

03:15 15.03.10

21. מכתב
בתגובה להודעה מספר 20

לא ממש מבין למה התכוונת כשאמרת sparse hyperplane - זה קצת מושג גדול פשוט לבעייה.

באשר לאלגוריתם השונה - אכן יש ואתה בכיוון נכון. השאלה איך בידיוק עושים את זה. אני אתן את 2 הפתרונות בהמשך.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

11:43 15.03.10

22. אני מתכוון שע''י המרה לספארס אפשר ב-(O(nlogn
בתגובה להודעה מספר 21

למצוא את הנקודה הכי קרובה לנקודה מסויימת ברדיוס מסויים (אם אני זוכר את כל הפרטים הקטנים נכון) שהרדיוס הזה יהיה בדיוק ממוצע גאוגרפי לאיברים בחתך, ואז אפשר, לפי משפט המאסטר, להגיע לסיבוכיות (O(n*logn

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד