זז הצידה, בובי פישר.
הסר את כל הכלים מלוח שחמט מלבד אביר אחד. לאחר מכן נסה להעביר את האביר על פני כל 64 הריבועים של הלוח, לגעת בכל אחת מהן פעם אחת. (כתזכורת, אבירים זזים בצורת L, שני רווחים בכיוון אחד, ואז רווח אחד שמאלה או ימינה, או למעלה או למטה, בזווית של 90 מעלות.) מה שנקרא "אביר" סיור" קשה מאוד להשיג עבור אדם בודד, אבל מתמטיקאים חישבו שיש מספר מדהים של דרכים למשוך אותו כבוי. אם תגיע למקום בו התחלת, תסיים מה שנקרא "סיור סגור". יש יותר מ-26 טריליון דרכים כדי לעשות זאת. אם אתה רק נוגע בכל נקודה, מבלי לחזור לנקודת המוצא שלך, זה נקרא סיור פתוח. מספר הדרכים לעשות זאת כה גדול שמדענים לא חישבו אותו.
חיפוש אחר פתרונות חדשים לסיור האביר, בעיה שסקרנה מתמטיקאים מאות שנים, למדען המחשבים של אוניברסיטת נוטינגהאם, גרהם קנדל ועמית, פנו אליו נמלים מדומות. הם השתמשו ב אלגוריתם אופטימיזציה של מושבת נמלים, טכניקת מודיעין נחיל המבוססת על התנהגות של נמלים מחפשים למצוא נתיב בין המושבה שלהם למקור מזון. זה עובד ככה, כפי שמסבירה קנדל ב"השיחה".:
תוכנת מחשב משמשת כדי לדמות אוכלוסיית נמלים. על נמלים אלו מוטלת המשימה למצוא פתרון לבעיה. כאשר כל נמלה ממלאת את תפקידה, היא חותרת שובל פרומון - חומר מסריח שנמלים משתמשות בו כדי לתקשר זו עם זו. באלגוריתם המדומה, הנמלים המוצלחות ביותר (אלה שפותרות את הבעיה בצורה טובה יותר), שוכבות יותר פרומונים מאלה שביצועיהן גרועים.
תוכנית זו חוזרת על עצמה מאות אלפי פעמים, ומציבה יותר "פרומונים" בשבילים שמסיימים סיור. אבל יש לאזן בין חיזוק שבילים שעובדים, לבין שימת דגש על מציאת שבילים חדשים.
באמצעות התוכנית, קנדל ועמיתו מצאו כמעט 500,000 פתרונות חדשים לסיור של האביר. מי ידע שנמלים (מדומות) יכולות למצוא תשובות חדשות לשאלה שמסקרנת אנשים במשך מאות שנים?
השיחה