בעיית סיפוק אילוצים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
טיפה יותר הבהרה תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
←הגדרות: הוספת דוגמא תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
||
שורה 2:
==הגדרות==
משתנים - אחד או יותר משתנים.
מרחב המצבים - כלל ההשמות האפשריות למשתנים.
דומיין - דומיין של משתנה הוא הערכים האפשריים למשתנה זה.
אילוצים - פונקציות שהערכים של המשתנים צריכים לקיים. כל פונקציה יכולה להכיל ערך אחד או יותר.
==דוגמאות==
===חידת שמונה המלכות===
ניתן להציג את [[חידת שמונה המלכות]] כבעיית סיפוק אילוצים בו יש שמונה משתנים, הדומיין הוא הצבה של כל הקומבינציות האפשריות של השמה של כלל מקומות ה[[לוח שחמט|לוח]] לכל אחד מהמשתנים, ועבור כל זוג משתנים יש אילוץ שהם לא באותה שורה/טור/אלכסון.
מדוגמה זו ניתן לראות את חשיבותו של בחירת הדומיין, אם ייבחר הדומיין של כל הקומבינציות האפשריות כאשר לכל משתנה i מותר להיות רק על השורה מספר i אזי גודל הדומיין יקטן משמעותית וכן מספר הערכים האפשריים לכל משתנה.
==אלגוריתם==
| |||