ערכתי לאחרונה בתאריך 11.06.09 בשעה 08:31 בברכה, DanGati
שלום יש לי פרוייקט בג'אווה שאני צריך להגיש והייתי מעוניין לקבל קצת עזרה
אני צריך לכתוב את האלוגריתם המצורף:
נתון J שזה מס' מכונה
ו tAJ זמן עיבוד במכונהנתונה הטבלה הבאה:
סכום 4 3 2 1 J
15 5 1 7 2 tAJ
12 1 2 5 4 tBJ
27 10 6 5 6 tCJ
צריך לחשב LB1, LB2, LB3
LB1 מחושב בצורה הבאה:
לוקחים את הסכום של tAJ ומוסיפים לו את הסכום המינימאלי של tBJ + tCJ לאותו J. לדוגמא: 23=(2+6)+15. 15 זה הסכום של tAJ ו 2+6 זה הסכום המינימאלי של tBJ + tCJ, וזה קורה ב J = 3.
LB2 מחושב בצורה הבאה:
לוקחים את הסכום של tBJ ומוסיפים לו את הסכום המינימאלי של tAJ + tCJ לא מאותו J. לדוגמא: 18=(1+5)+12. 12 זה הסכום של tBJ ו 1+5 זה הסכום המינימאלי של tAJ + tCJ כאשר 1 הוא ב J=3 ו 5 הוא ב J=2.
LB3 מחושב בצורה הבאה:
לוקחים את הסכום של tCJ ומוסיפים לו את הסכום המינימאלי של tAJ + tBJ לאותו J. לדוגמא: 30=(1+2)+27. 27 זה הסכום של tCJ ו 1+2 זה הסכום המינימאלי של tAJ + tBJ, וזה קורה ב J = 3.
חישוב LB:
המקסימום בין LB1,LB2,LB3.
לאחר חישוב LB צריך לבדוק האם tBJ נשלט ע"י tAJ או tCJ עושים זאת כך:
אם המספר המינימאלי בשורה של tAJ גדול או שווה למספר המקסימאלי בשורה של tBJ אז tAJ שולט על tBJ.
אם המספר המינימאלי בשורה של tCJ גדול או שווה למספר המקסימאלי בשורה של tBJ אז tCJ שולט על tBJ.
במקרה שלנו tCJ שולט על tBJ.המספר המינימאלי ב tCJ הוא 5 והוא גדול או שווה למספר המקסימאלי ב tBJ.
אם tBJ לא נשלטת יש לכתוב הפיתרון לא יהיה אופטימאלי.
אם כן צריך לאחד את tAJ,tBJ,tCJ ל-2 (tIJ,tIIJ) עושים זאת כך:
tIJ שווה ל tAJ + tBJ לכל J.
tIIJ שווה ל tBJ + tCJ לכל J.
יראה כך:
4 3 2 1 J
6 3 12 6 tIJ
11 8 10 10 tIIJ
לאחר השלב הזה מתחילים לחפש את ה J שהוא בעל הזמן הכי קטן אם הוא נמצא ב tIJ הוא הולך שמאלה, אם ב tIIJ הוא הולך ימינה. מוחקים כל J ששובץ.
לדוגמא:
המס' המינימאלי הוא 3, הוא נמצא ב tIJ והוא שייך ל J=3, לכן J=3 יפתח את הסידור (הולך שמאלה). המס' הבא בתור הוא 6, הוא נמצא ב tIJ והוא שייך גם ל J=1 וגם ל J=4, לכן יש ריבוי פתרונות, לא משנה מי קודם הולך שמאלה או 1 או 4.
המס' הבא בתור הוא 10,כי 8 נמחק כאשר שיבצנו כבר את J=3, הוא נמצא ב tIIJ, הוא שייך ל J=2 הוא ילך ימינה ז"א יסגור את הסידור (יהיה אחרון).
בסופו של דבר הסידור יראה כך:
2 1 4 3
או
2 4 1 3
לאחר שמצאנו את הסידור האופטימאלי צריך לחזור לצורה של 3 (tAJ,tBJ,tCJ) ע"פ הסידור החדש את הזמנים לכל J מעתיקים מהטבלה הראשונה.
2 1 4 3 J
7 2 5 1 tAJ
5 4 1 2 tBJ
5 6 10 6 tCJ
מחשבים את CAJ,CBJ,CCJ בצורה הבאה:
CAJ: מתחיל בערך של tAJ של ה J הראשון ומוסיפים לו את הערכים הבאים בתור בשורה של tAJ.
CBJ: לוקחים את המספר הראשון ב CAJ מוסיפים לו את המספר הראשון ב tBJ ומקבלים את המספר הראשון ב CBJ. לחישוב הערכים הבאים בשורה צריך לעשות את החישוב הבא:
המקסימום בין הערך הנוכחי של CBJ לערך הבא בתור ב CAJ. אם הערך ב CBJ יותר גדול מוסיפים לו את הערך של tBJ. אם הערך ב CAJ יותר גדול מוסיפים לו את הערך ב tBJ.
CCJ: מחושב בדיוק אותו הדבר כמו CBJ רק שבמקום CBJ מופיע CCJ ובמכום CAJ מופיע CBJ. והערך שמתווסף הוא מ tCJ.
לבסוף הטבלה ניראת כך:
2 1 4 3 J
7 2 5 1 tAJ
5 4 1 2 tBJ
5 6 10 6 tCJ
15 8 6 1 CAJ
20 12 7 3 CBJ
30 25 19 9 CCJ
בסופו של דבר צריך להיות פלט עם הסידור האופטימאלי ( אחד או יותר) ועם ה C המקסימאלי (במקרה שלנו C MAX = 30)
לדוגמא:
הסידור האופטימאלי 2 1 4 3 או 2 4 1 3
C MAX: 30
תודה מקרב לב לעוזרים