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