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

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

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

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

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

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

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

במקרה כזה, שחקן ה מחשב למעשה על הבנים שלו, ושחקן ה מחשב עליהם.

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

הוכחה:

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

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

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

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

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

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

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