שיחה:חידת מסע הפרש

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

"קיימים מספר מיליארדים של פתרונות שונים לבעיה, שמתוכם כ-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)

טעיתי, למרות שמעבר על מספר סביר של מליארדי אפשרויות היא באמת לא משימה קשה, מדובר פה על כמה מליארדי פתרונות - מרחב החיפוש גדול בהרבה. אתמול בלילה נסיתי להריץ קוד בדיקה ובאמת נרדמתי לפני שקבלתי תוצאה. טוב, אפשר לנסות להפעיל קצת את הראש או לחפש ברשת. עונג שבת של משהו?יבחוש 15:17, 18 בינואר 2007 (IST)

תודות לעוזי! "באופן כללי ספירת מסלולים המילטוניים היא בעיה קשה; במקרה הזה, נראה ש- Brendon McKay פתר אותה. עבור לוחות גדולים יותר, ידוע שמספר המסלולים עולה על $\ (1.3535)^{n^2}$ : 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)"

בקשר לנוסחה, אתה יכול להסביר בבקשה איך היא עובדת ומאיפה אתה מסיק שהיא נכונה? --miniature 22:20, 18 בינואר 2007 (IST)

הכנס להסבר בערך, של זה שכתב אותה. אני לא הצלחתי להכנס. עוזי, אפשר לקשר לקובץ בפורמט אחר? חגי אדלר 22:27, 18 בינואר 2007 (IST)

מקור: http://he.wikipedia.org../../../%D7%97/%D7%99/%D7%93/%D7%A9%D7%99%D7%97%D7%94%7E%D7%97%D7%99%D7%93%D7%AA_%D7%9E%D7%A1%D7%A2_%D7%94%D7%A4%D7%A8%D7%A9.html

שיחה:חידת מסע הפרש

מתוך ויקיפדיה, האנציקלופדיה החופשית

Views

ניווט

קהילה

חיפוש