שיחה:חידת מסע הפרש
מתוך ויקיפדיה, האנציקלופדיה החופשית
"קיימים מספר מיליארדים של פתרונות שונים לבעיה, שמתוכם כ-122,000,000 הם מסלולים סגורים." - איך חישבו דבר כזה? --miniature 20:18, 17 בינואר 2007 (IST)
- סביר להניח שיש שיטות אלגנטיות יותר אבל אפשר פשוט לבדוק את כל המסלולים בעזרת תוכנית מחשב פשוטה (backtracking). לא מדובר במספרים גדולים עבור מחשב (של עשרים השנים האחרונות).יבחוש 23:15, 17 בינואר 2007 (IST)
- לא חושב. בבחרותי כתבתי תוכנית כזו, והרצתי אותה על VAX-750 ב-1984 (מישהו זוכר?) היא רצה 10 שעות מהפינה השמאלית העליונה, ובקושי מצאה פתרון אחד. למרות שעברו 23 שנים, קשה לי להאמין שתוכנית מחשב סרקה את כל מיליארדי האפשרויות. חגי אדלר 01:14, 18 בינואר 2007 (IST)
- אם כך איך בכל זאת אנו סבורים שהנתונים הכתובים בערך אכן נכונים? --miniature 14:47, 18 בינואר 2007 (IST)
- לא חושב. בבחרותי כתבתי תוכנית כזו, והרצתי אותה על VAX-750 ב-1984 (מישהו זוכר?) היא רצה 10 שעות מהפינה השמאלית העליונה, ובקושי מצאה פתרון אחד. למרות שעברו 23 שנים, קשה לי להאמין שתוכנית מחשב סרקה את כל מיליארדי האפשרויות. חגי אדלר 01:14, 18 בינואר 2007 (IST)
טעיתי, למרות שמעבר על מספר סביר של מליארדי אפשרויות היא באמת לא משימה קשה, מדובר פה על כמה מליארדי פתרונות - מרחב החיפוש גדול בהרבה. אתמול בלילה נסיתי להריץ קוד בדיקה ובאמת נרדמתי לפני שקבלתי תוצאה. טוב, אפשר לנסות להפעיל קצת את הראש או לחפש ברשת. עונג שבת של משהו?יבחוש 15:17, 18 בינואר 2007 (IST)
-
-
-
- תודות לעוזי! "באופן כללי ספירת מסלולים המילטוניים היא בעיה קשה; במקרה הזה, נראה ש- Brendon McKay פתר אותה. עבור לוחות גדולים יותר, ידוע שמספר המסלולים עולה על
: Kyek, Olaf; Parberry, Ian; Wegener, Ingo, Bounds on the number of knight's tours, Discrete Appl. Math. 74 (1997), no. 2, 171--181. עוזי ו. 18:50, 18 בינואר 2007 (IST)"
- תודות לעוזי! "באופן כללי ספירת מסלולים המילטוניים היא בעיה קשה; במקרה הזה, נראה ש- Brendon McKay פתר אותה. עבור לוחות גדולים יותר, ידוע שמספר המסלולים עולה על
-
-
