אילוצים: למה הפתרון הטוב ביותר הוא לפעמים פתרון שאסור להשתמש בו

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

אבל במציאות, הבעיה האמיתית אינה למצוא את הפתרון הזול ביותר.

הבעיה היא למצוא את הפתרון הזול ביותר שמותר לבצע.

כאן נכנסים לתמונה האילוצים.

מהו אילוץ?

אילוץ (Constraint) הוא כלל שהפתרון חייב לקיים.

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

לדוגמה, בתכנון הסעות תלמידים:

• רכב אינו יכול להסיע יותר תלמידים מהקיבולת שלו.

• תלמידים של מוסדות שונים אינם יכולים לנסוע יחד.

• תלמיד אינו יכול להגיע לאחר שעת תחילת הלימודים.

• נהג אינו יכול לעבוד יותר ממספר שעות מסוים.

• תלמיד מסוים חייב לנסוע עם מלווה.

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

אילוצים קשים ואילוצים רכים

לא כל האילוצים זהים.

אילוצים קשים (Hard Constraints)

אלו כללים שאסור להפר בשום מצב.

לדוגמה:

• חריגה מקיבולת הרכב.

• הגעה לאחר תחילת הלימודים.

• שימוש ברכב שאינו מתאים לכיסא גלגלים.

פתרון שמפר אילוץ קשה נפסל מיד.

אילוצים רכים (Soft Constraints)

אלו כללים שרצוי לעמוד בהם, אך אפשר להפר אותם במחיר מסוים.

לדוגמה:

• העדפת נהג קבוע.

• הגבלת זמן נסיעה מומלץ.

• איזון עומס בין נהגים.

במקרים אלו אפשר להוסיף "קנס" לפונקציית המטרה.

למה אילוצים מסבכים את הבעיה?

ללא אילוצים, האלגוריתם יכול לבחור כל פתרון.

עם אילוצים, חלק גדול ממרחב הפתרונות נעלם.

לפעמים נשארים מעט מאוד פתרונות חוקיים.

ולעיתים אין בכלל פתרון שעומד בכל הדרישות.

במקרים כאלה צריך להחליט:

• האם להגדיל את מספר הרכבים?

• האם לאפשר חריגה מזמן הנסיעה?

• האם לשנות אילוצים מסוימים?

האופטימיזציה הופכת לתהליך של איזון בין מגבלות שונות.

שתי גישות לטיפול באילוצים

יצירת פתרונות חוקיים בלבד

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

היתרון:

• אין צורך לבדוק חוקיות בהמשך.

החיסרון:

• קשה לייצר פתרונות חדשים.

מתן קנסות על הפרות

מאפשרים גם פתרונות לא חוקיים.

אבל מוסיפים להם עלות גבוהה.

לדוגמה:

• חריגה של תלמיד אחד מקיבולת → קנס של 10,000 נקודות.

• איחור של דקה → קנס של 100 נקודות.

כך האלגוריתם יכול לעבור דרך פתרונות זמניים שאינם מושלמים, ולהשתפר בהמשך.

מחשבה לסיום

רבים חושבים שאופטימיזציה היא למצוא את הפתרון הזול ביותר.

בפועל, אופטימיזציה היא לעיתים קרובות:

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

והחלק המאתגר ביותר אינו האלגוריתם.

הוא להבין מהם הכללים שאסור לשבור.