הבעיה היא כך:

נתונות n נקודות (x,y). צריך למצוא תת קבצוה מקסימלאית של נקודות שהמרחק בין הנקודות הוא לכל היותר d בשרשרת.

הכוונה בשרשרת: שהמרחק בין x1 ל x2 הוא לכל היותר d.

המרחק בין x2 ל x3 הוא לכל היותר d

המרחק בין x3 ל x4 הוא לכל היותר d. וכולה.

אך לא חייב שהמרחק בין כל שתי נקודות הוא לכל היותר d. יכול להיות שבמקרה הנ"ל המרחק בין x1 ל x3 הוא יותר מ d.

דבר נוסף הסימון x1,x2 וכולה, יכול להיות על כל נקודה. זה לא אומר ש x1 הוגדר מראש להיות x1. סימנתי זאת רק לגבי הנוחות. ואין חשיבות לסדר של x1,x2 וכולה.

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

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

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

דבר נוסף המרחקים לא נתונים צריך לחשב אותם כמו שמחשבים מרחק בין שתי נקודות.

תודה.

ניתן לתרגם את הבעיה שלך לבעיה בתורת הגרפים:

כל נקודה היא קודקוד, וכל שתי נקודות מחוברות בקשת אם המרחק ביניהן קטן מ-d.

הבעיה שקולה למציאת מסלול ארוך ביותר בגרף.

הבעיה כאן היא שאין באמת פתרון יעיל לבעיה הזו - היא NP-Complete (אפשר להראות שהיא שקולה לבעיית מסלול המילטון).

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

(ייתכן שדווקא יש פתרון יעיל, בלי לתרגם את הבעיה לתורת הגרפים, אבל אני עדיין לא בטוח)

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

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

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

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

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

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

בפתרון שהצעת ישנם שתי שלבים:

1. בניית הגרף

2. צריך לבחור קודקוד להפעיל עליו DFS וכך מוצאים את הרכיב קשירות הראשון. עוברים לשאר הקודקודים שלא נצבעו (כלומר לא עברנו עליהם ע"י אלגוריתם DFS) ומפעילים עליהם DFS עד אשר לא נשארים קוקודים צבועים בלבן. (כלומר שעברנו על כל הקדוקדים האפשריים).

הזמן ריצה עבור בניית הגרף הוא O(n^2) כיוון שצריך לעבור על כל זוג של קודקודים אפשריים על מנת לבנות את הגרף.

הזמן ריצה עבור הפעלת ה DFS הוא O(מספר הקשתות + הקודקודים).

אני חושב שניתן לצמצם עוד יותר את הזמן ריצה. תחשוב על זה שאני הולך לממש את זה ולארק בתיאוריה.

מה שחשבתי לעשות:

1. למיין את הקודקודים לפי ה X (ואם אני רוצה עוד ליייעל את זה אז למיין לאחר מכן את הקבוצות של הקדקודים שההפרש בין ה y -ים שלהם לא עולה על d).

המיון נועד לדבר הבא: אם יש לנו n קודקודים למה אני צריך לחשב (בבניית הגרף) מרחק בין כל שתי נקודות, הרי אם המרחק בין שני קוקודים ב X או ב Y גדול מ d כל שכן המרחק גדול מ d. ואם אני מסתכל על הקודוקוד הראשון (בעל ה x הכי קטן) והקודקוד ה 100 (במיון) רחוק ממנו מרחק מעל d אז אין טעם לבצע את החישוב של המרחק עבור הקודקוד ה 101 והלאה עם הקדוקוד הראשון. וכן על זה הדרך. ככה אני חוסך עוד פעולות. ובמיוחד בבניית הגרף שהבנייה תיקח זמן עבור 100 מיליון קודקודים ואפילו יותר.

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

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

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

ודרך אגב תודה על התשובות ועל מהירות התגובות.