תרגיל בJAVA

[Amit7289]

תרגיל בJAVA

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

כרגע יש לי תוכנית שמציגה עיגול אדום בכל הקלקה ושומרת את הקורדינטות בACCESS בעמודות של X ו Y.(דוגמא http://i50.tinypic.com/2rm7ds0.jpg )
נתקעתי בקטע שצריך למצוא מבין כל הנקודות הללו את שתי הנקודות בעלות המרחק הקצר ביותר.
חיפוש בגוגל העלה את האלגוריתם של דייקסטרה אבל לא הצלחתי ליישם את זה...

תודה לעוזרים

 

[BravoMan]

אלגוריתם של דייקסטרה קשור למציאת מסלול

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

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

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

 

[Netanel w]

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

חישוב הנורמה ומימוש האלגוריתם הנ"ל הוא טריוויאלי לחלוטין - (איך לדוגמא תמצא את הערך המינימלי במערך בגודל n?).

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

 

[Netanel w]

קבל לינק מצומצם מויקיפדיה

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

 

[Amit7289]

הצלחתי. תודה.