6.5.5.3. פעולות בוליאניות על BDD (Apply)בהינתן שני BDD: נרצה לחשב את ה-BDD של כאשר הוא אחת מ-16 הפונקציות הבינאריות. סימונים: הם השורשים של בהתאמה. אם אינם צמתי קצה אז וכן . נסתמך על "הרחבת Shonon": Apply עובדת לפי ארבעה מקרים שונים: (חישוב ):
דוגמא: נחשב את : ואחרי צמצום:
דוגמא יהיו 2 פונקציות מעל המשתנים . נקבע את סדר המשתנים להיות . הפונקציות עצמן הינן: נרצה לחשב את הפונקציה . המקרה כאן הוא מקרה 3. ומכאן נקבל: אנו מקבלים כי: ניתן להגיע לאותו הפיתוח באמצעות שימוש בלוגיקה, לבדיקה: סיבוכיות פעולה APPLY טיפול פשטני נותן לנו פתרון
אקספוננציאלי בגודל ה-BDD. כדי לפתור את הבעיה ביעילות נשים לב כי כל צומת ב-BDD
מייצג פונקציה, ומספר הפונקציות השונות שמיוצגות הוא כמספר הצמתים נשתמש בטבלת HASH: לכל הפעלה של APPLY יש מצביעים לצמתים ב-BDD שמהם הפעולה הופעלה, וכן את הפעולה שהופעלה. לא נבצע את אותו חישוב פעמיים אלא נשתמש בתוצאות שכבר חישבנו. כעת הסיבוכיות תלויה בכמות פעולות ה-APPLY השונות שמבצעים במהלך תהליך APPLY על . נסמן ב- את מספר הצמתים ב-BDD של ומכאן: מספר הפעולות הוא .
אין תגובות!
|
תוכן העניינים:
קישורים רלוונטיים:שיתוף: |