החברים של Alien

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

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

בעיה

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

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

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

החלטה תהליך

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

המטרה:

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

הצעת פתרון

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