החברים של החייזרים

שיטת עיצוב אלגוריתם סניף וקשר (המכונה גם הסתעפות ו Dimensioning) הינה נגזרת של Backtracking שיפרה בצורה משמעותית, והוא מיושם בעיקר לפתור שאלות או בעיות של אופטימיזציה.

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

הצגת הבעיה

מאת האלגוריתם הבא לפתרון המוצ 'ילה 0 / 1 דרך הסתעפות ו גיזום, אני יישמו תוכנית ב C # זה פותר בעיה זו עם האסטרטגיות הבאות:

• FIFO - (First In First Out) ראשון ב - First Out
• LIFO - (האחרון הראשון שיצא) האחרון הראשון החוצה. (PILA)
• LC - LIFO - לאחרונה במערך הראשון שיצא. (מערך של סוללות)
• LC - FIFO - First In Array הראשונה. (מערך של דבק)

רשימת צמתים לחיות (LNV) תוקם מחלקה של אובייקטים על ידי צומת, אשר מוגדר כדלקמן:

החלטה תהליך

1. ווקטורים מדורגות לפי משקל היתרון ואת היחס B / פ
2. ברגע זה הוא צומת שורש שנוצר לרשימה של צמתים בחיים.
3. בשלב זה נכנס ללולאה שהוא חזר עד LNV ריקה את הדברים הבאים:
4. אם הצומת חילוץ מבטיח כי האינטרס הטוב ביותר שאנחנו למד עד כה (גיזום הראשון) ז 'אנר ילדיהם בצומת י'
5. עבור כל ילד אם הוא מכיל אותו משקל> מאשר את המשקל המקסימלי המותר לא לנסות (אינני עושה שום דבר) כי עבור בנאי את הכיתה אני אותחל צמתים וגבהים לערכים מספרים קטנים מאוד.
6. אחרת הטיפול צומת מגדר הערכות בהתאם.
7. ואז זה בודק אם המצב הנוכחי הוא פתרון ואם כן עדכונים על הצומת פתרון.
8. אם לא הפתרון הוא לראות אם העליון כבול של הצומת שיש לנו עסק עם הוא גדול או שווה ל C כי אנחנו (גיזום 2) נוסף LNV אם לא.

המטרה:

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

הפתרון המוצע

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