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