אלגוריתמים והיוריסטיקות
מתוך WikiBook
מושגי האלגוריתם והיוריסטי [כללים המשמשים בפתרון בעיה אך אינם מבטיחים פתרון מלא או פתרון בכל פעם. אלו כללי אצבע או "מרשמים" לא פורמאליים למציאת פיתרון בדרך קלה או קצרה. ההיוריסטים מאופיינים בכך שאינם בהכרח מדויקים, סופיים או סטנדרטים. במקרים רבים אנו עושים שימוש בהיוריסטים לפתרון בעיות שאין לנו עבורם אלגוריתם מסודר]
אחת ההבחנות בין סוגי החלטות היא ההבחנה בין אלגוריתמים והיוריסטים. אלגוריתם (Algorithm) הוא אוסף סדור של הוראות לפעולות סטנדרטיות, המבטיחות פתרון לבעיה מסויימת במספר סופי של צעדים. במלים אחרות, אלגוריתם הוא מרשם לקבלת החלטה, המנוסח בצורה פורמאלית, והוא מדויק וסופי. דוגמא לאלגוריתם הוא האופן בו ניתן לברר אם מספר שלם מתחלק ל-9 בלי שארית. אלגוריתם לפתרון בעיה זאת הוא:
- סכם את כל הספרות של המספר.
- אם התוצאה מכילה יותר מספרה אחת, חזור לבצע את שלב 1 עבור התוצאה. אם התוצאה היא בת ספרה אחת, עבור לשלב 3.
- אם התוצאה היא 9, המספר מתחלק ב 9. אחרת, תהיה שארית לא שלמה לחלוקה.
כפי שאפשר לראות, האלגוריתם מצביע על הדרך המדויקת לקבלת החלטה. שימוש נכון באלגוריתם יביא להחלטה חד משמעית. אם האלגוריתם מדויק, ההחלטה תהיה מדויקת. בעיה מעניינת נוספת היא בעיית "מגדלי הנוי". לפירוט והדגמה גלשו אל http://alefefes.macam98.ac.il/games/game.asp?n=6
סוג מעניין של אלגוריתמים הוא אלגוריתמים רקורסיביים-נסיגה. עקרון הרקורסיה (נסיגה) הוא עקרון מתמטי, שעיקרו: כדי לפתור בעיה, נתבסס על פתרון של בעיה דומה אך פשוטה יותר. דוגמא רקורסיבית ידועה היא בעיית חישוב עצרת של מספר. כדי לחשב עצרת של מספר n כלשהו, אם נדע לחשב את העצרת של המספר n-1, או אז נוכל להכפיל תוצאה זו במספר n ולקבל את מבוקשנו. וכדי לחשב עצרת של מספר n-1, נחשב את העצרת של המספר n-2 ונכפיל תוצאה זו במספר n-1 וכך הלאה. לכל פתרון רקורסיבי יש "בסיס רקורסיה". זהו מהלך מפורש, בו האלגוריתם מבצע פעולה מוגדרת במדויק, ללא הישענות על תת-בעיה דומה. בדוגמא שלנו, בסיס הרקורסיה הוא המקרה בו הגענו לחישוב עצרת המספר 1 (מייד אחרי שבאחד השלבים הגענו לצורך לחשב את עצרת המספר 2). במהלך זה, תת-הבעיה התגמדה לחישוב עצרת המספר 1, שהיא כמובן שווה 1. בשלב זה, מגיעה "התקפלות" הרקורסיה, בה חוזרים לכל שלב שהיינו קודם, בסדר הפוך. בכל שלב כזה יש בידנו תוצאה מוחלטת. זאת עד להגעה לשלב הראשון, ממנו נחזור עם התוצאה הסופית.
היוריסטיקות (Heuristics) הם כללי אצבע, או "מרשמים" לא פורמאליים, למציאת פתרון בדרך קלה או קצרה. היוריסטים מתאפיינים בכך שאינם בהכרח מדויקים, סופיים, או סטנדרטיים. במקרים רבים אנו עושים שימוש בהיוריסטים לפתרון בעיות שאין לנו עבורן אלגוריתם[אוסף לוגי מוגדר היטב ומדורג של הוראות המאפשרות לבצע פעולה מסוימת. ] מסודר. כך, למשל, ההיוריסטי למהלך מוקדם במשחק שש-בש, גורס שיש לנסות לבנות "בית" ברבעון המטרה של לוח המשחק. אם תוצאות זריקת הקוביות הן שתי ספרות בהפרש של 2 זו מזו, כדאי להשתמש בכלים שנמצאים בשני הבתים (בעלי 3 ו 5 קוביות) שנמצאים במחצית הקרובה של הלוח. היוריסטי זה, (כמו כל היוריסטי), אינו פותר את כל המצבים האפשריים בהם יכול להימצא שחקן השש-בש, והוא "נכון" או מיטבי רק לפעמים. ההיוריסטי אינו מבטיח פתרון, אבל הוא חוסך זמן, ורבים נשענים עליו. למעשה, בכל בעייה שבה נכנס מאפיין של אי-ודאות, כדוגמת רנדומאליות (זריקת קוביות), הפתרון משלב היוריסטיקה.
דוגמא ידועה לשילוב היוריסטיקות, היא מחשב-שח, כדוגמת מחשב "כחול עמוק", אשר ניצח בזמנו את אלוף העולם בשח, גארי קאספרוב. העיקרון הבסיסי עליו מבוסס מחשב-שח הוא עקרון המינימום מקסימום בעץ מצבים. עץ מצבים הוא דיאגראמת כל האפשרויות במשחק, החל ממצב נתון של הלוח ועד למצב הלוח אחרי מספר מסויים של מהלכים. עקרון המינימום מקסימום, מניח כי בכל תור של היריב, היריב יבחר במהלך הכי טוב עבורו (עבור היריב), שהוא הכי גרוע לשחקן, ועל השחקן לבחור בצעד הכי טוב עבורו (עבור השחקן). עקרון זה הוא טבעי ומשמעותו האופרטיבית: כשתורנו לשחק, נבחן את האפשרויות למהלך. נבחר במהלך, שאחריו, גם אם היריב יבחר בצעד הכי טוב עבורו, עדיין סיכויינו לנצח יהיו טובים יותר ממהלכים אחרים אותם יכולנו לבחור. אז מה הבעיה? יקום מישהו ויאמר, בוא נבנה את עץ כל האפשרויות במשחק, החל מראשיתו ועד לכל הסיומות האפשריות לו, ואז, מובטח הניצחון במשחק. אלא שמספר האפשריות בשח הוא כמחצית ממספר האטומים ביקום. למעשה, אפילו עץ משחק המכיל את עשרת המהלכים הבאים הוא עצום. עם זאת, שימוש בהיוריסטיקה של עקרון המינימום מקסימום, מגדיל, אם כי לא מבטיח, ניצחון. והסיכוי גדל כלל שעץ המשחק ארוך יותר.
ישנו קוריוז לפיו, אלוף העולם גארי קאספרוב ידע, בשלב מסוים, מהו אורכו של עץ המשחק הנבדק אצל המחשב. הוא תכננן מהלכים, שאת תוצאותם ניתן לראות רק כמה מהלכים יותר ממה שרואה המחשב בעץ, ובכך למד לנצח לבסוף את המחשב. עוד על מחשב "כחול עמוק" ב- http://www.research.ibm.com/deepblue/
פקודות או הוראות קבע (פק"לים), נושאים בדרך כלל אופי של אוסף אלגוריתמים [אוסף לוגי מוגדר היטב ומדורג של הוראות המאפשרות לבצע פעולה מסוימת. ]ו/או היוריסטים. במלים אחרות, כאשר לפנינו בעיה מובנית, עלינו לנסח עבורה אלגוריתם או היוריסטי. לאחר שנוסח אלגוריתם או היוריסטי המתאים לפתרון בעיה כזאת או אחרת, קל יחסית למחשב את הביצוע של ההחלטה. מכאן שאלגוריתמים והיוריסטים שייכים שניהם לתחום ההחלטה המובנית. הם מהווים שני סוגים שונים של פתרון לבעיה מסוג זה.
|
שאלות:
תן דוגמאות לשלוש החלטות שמנהל עשוי להידרש לקבל. הגדר כל החלטה מבחינת התדירות, החשיבות, והמבניות היחסיים שלה.
חווה דעתך: עד כמה יהיה קל למחשב החלטה זאת? מדוע?
