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