פונקציה בוליאנית חמקנית

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

פונקציה בוליאנית \ f על \ n משתנים, נקראת חמקנית (evasive) אם זמן הריצה של כל אלגוריתם עץ הכרעה עבורה הוא בדיוק \ n. או במילים אחרות, כל אלגוריתם שמחשב את \ f, צריך להעריך את כל \ n ביטי הקלט במקרה הגרוע ביותר.

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

לא כל פונקציה בוליאנית היא חמקנית. נבחן לדוגמה את הפונקציה הבאה: \ (x_0\and x_2)\lor (\bar{x_0} \and x_1) הפונקציה תלויה בשלושת המשתנים שלה: \ x_0,x_1,x_2, אבל מספיק לשאול רק שתי שאלות כדי להעריך אותה: נגלה תחילה את הערך של \ x_0. אם \ x_0 הוא אמת, נברר את הערך של \ x_2 ונחזיר אותו כערך כל הפונקציה, ואם הערך של \ x_0 הוא שקר, נברר את הערך של \ x_1 ונחזיר אותו כערך כלל הפונקציה.

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

נבחן מקרה פרטי של עצי משחק, בו הערכים האפשריים לקודקודים הם 0 ו-1.

במקרה כזה, שחקן ה \ max מחשב למעשה \ \lor על הבנים שלו, ושחקן ה \ \min מחשב \ \and עליהם.

משפט: עבור עץ משחק כפי שתואר, בעל \ n עלים, פונקציית ההערכה שלו היא חמקנית.

הוכחה:

נוכיח באינדוקציה על \ n שישנו יריב אופטימלי שגורר עומק \ n לעץ ההכרעה.

עבור \ n=1 עלים, האלגוריתם יהיה חייב לברר את ערכו של העלה היחיד, ובמקרה זה לא משנה מה היריב יענה.

נניח כי קיים יריב אופטימלי עבור עצים בעלי \ n-1 עלים ונוכיח קיום גם בעבור עצים בעלי \ n עלים.

עבור \ n כללי, האלגוריתם מתחיל ומברר ערך של \ x_i כלשהו. היריב יענה 0 אם הקודקוד אליו מחובר העלה הוא קודקוד \ \lor (כלומר אם השחקן הוא שחקן \ max), ו- 1 אם זהו קודקוד \ \and (כלומר שחקן \ min).

הערך שהיריב ענה לא גרם לתשובה חד-משמעית בעבור הקודקוד - במקרה של קודקוד \ \lor העובדה שאחד הערכים הוא 0 לא קובעת את ערך הקודקוד וכך גם בעבור קודקוד \ \and בו ידוע שאחד הערכים הוא 1. בכל מקרה השחקן שמשחק את הקודקוד יאלץ לברר את ערכי שאר הבנים.

מכאן, היריב ימשיך כמו היריב האופטימלי לפונקציה המושרה בלי \ x_i (שהיא בעלת \ n-1 עלים). ומכאן באינדוקציה, היריב גרר עומק \ n לעץ.

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