בעיית סיפוק אילוצים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

הגדרות[עריכת קוד מקור | עריכה]

מרחב המצבים - כלל ההשמות האפשריות למשתנים. דומיין - דומיין של משתנה הוא הערכים האפשריים למשתנה זה.

אלגוריתם[עריכת קוד מקור | עריכה]

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

AC-3[עריכת קוד מקור | עריכה]

אלגוריתם AC-3 הוא אלגוריתם שבודק עבור כל ערך של משתנה A האם קיים ערך של משתנה בכל אחד מהמשתנים האחרים כך שהאילוץ בין שני המשתנים לא מופר, אם קיים משתנה לו אין ערך כזה ניתן להסיר את הערך מהמשתנה A.

אלגוריתם גישוש נסוג[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – גישוש נסוג

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

מצגת על בעיות סיפוק אילוצים, donal bren school