 |
|
 |
||
|
||||
 |
הקדים ואומר תודה לכותב המאמר. רציתי לשתף בדוגמא מעניינת לתוכנית שכתבתי לפני כשלוש שנים בשפת c שגיליתי שעל קלטים קטנים היא רצה במהירות רבה(פחות משניה) ועל קלטים טיפה יותר גדולים היא צריכה יותר מגילו של העולם בשביל לפתור. התוכנית הייתה אמורה למצוא פיתרון יחיד(או את כל הפתרונות) של חידת המלכות. חידת המלכות : הגדרה של מלכה בשחמט - כלי שיכול לנוע באלכסון שמאלה ימינה למעלה ולמטה לכל אורך הלוח. המטרה היא לשים 8 מלכות על לוח שח מט(בגודל 8 על 8 משבצות כמובן) כך שאף מלכה לא תוכל במהלך אחד להגיע למלכה אחרת. נסו לבדכם את החידה, תראו שהיא לא כל כך קלה אך אחרי כמה נסיונות סיכוי גבוה שתמצאו פיתרון אחד מבין ה-80 ומשהו פתרונות אפשריים. בשביל לתאר כמה זמן לוקח לתוכנית אתאר איך פועלת התוכנית בכלליות: מכיוון שכל מלכה יכולה לזוז למעלה למטה אפשר להניח מראש כבר שכל תור יהיה בו מלכה אחת יחידה. התוכנית מתחילה מהמצב שכל שמונה המלכות נמצאות בשורה הראשונה כל אחת בתור שלה. כל פעם התוכנית מזיזה את המלכה הימנית ביותר שורה אחת קדימה. ברגע שהמלכה הימנית ביותר הגיעה לשורה האחרונה בתור הבא המלכה הימנית ביותר חוזרת לשורה הראשונה והמלכה משמאלה עוברת שורה קדימה. אם המלכה משמאל לימנית ביותר מגיעה לשורה האחרונה היא חוזרת לשורה הראשונה והמלכה משמאלה עוברת שורה אחת קדימה. וכך הלאה עד שכל המלכות נמצאות בשורה האחרונה. זה לא האלגוריתם האידאלי אך הוא התאים לי כשרציתי לפתור את הבעיה. בשביל להבין את הסיבוכיות של האלגוריתם יש לציין שכל מלכה יכולה להיות בכל שורה בתור שלה. ולכן לכל מלכה יש 8 אפשרויות איפה להיות. ויש 8 מלכות. ולכן יש 8 בחזקת 8 מצבים אפשריים שהאלגוריתם בודק. זהו מספר לא קטן בכלל. למעשה זהו מספר עם 7 ספרות. ניתן למצוא אלגוריתם יותר יעיל וכמובן שיש את האלגוריתם הכי פחות יעיל שכל מלכה יכולה להיות בכל מקום פנוי כלומר כמות האפשרויות היא 64*63*...* 57 שזהו מספר עם 14 ספרות. עכשיו התוכנה פתרה את הבעיה תוך זמן שלא ניתן להבחין בו(פחות מחצי שניה). ולכן ניסיתי לשנות את גודל הלוח ואת מספר המלכות(מספר המלכות הוא כמובן ביחס ישר לגודל הלוח). ופה מסתבר שעבור לוח בגודל 1-8(כלומר 1 על 1 עד 8 על 8 משצבות) זמן הריצה הוא אפסי. עבור לוח של 9 על 9 משבצות זמן הריצה הוא כמה שניות. עבור 10 אחרי הרבה דקות. בואו נניח שבדיקת מצב לוקחת פעולת מעבד בודדת. כלומר ב-8 על 8 יש 10 בחזקת 7 פעולות. המחשב עובד על 3 גיג'ה הרץ. כלומר 3*10 בחזקת 9 פעולות בשניה. כלומר זמן הריצה קטן מ-שניה. עכשיו עבור לוח של 12 על 12 יש 12 בחזקת 12 מצבים כלומר 9 כפול 10 בחזקת 12. נחלק את המספר במהירות שעון(3 גיג'ה) זה 3000 שניות. כלומר כמעט שעה. עבור לוח של 15 על 15 : 10 בחזקת 17 מצבים. לוקח לפי מהירות השעון הזאת 4.5 שנים. עבור 17 על 17: 10 בחזקת 20 פעולות. 8700 שנה. עבור 20 על 20 : 10 בחזקת 26. 1.1 מליארד שנה. עבור 25 על 25 : 10 בחזקת 34 מצבים. 938798431.1 מליארדי שנה. יש לזכור שהעולם קיים רק כמה מליארדי שנים בודדות. עכשיו נניח שמשפרים את יעילות האלגוריתם פי 10(וזה הרבה... אולי אפשרי אבל לא פשוט), ונניח שיש מחשב שבמקום לחשב 3*10 בחזקת 9 פעולות בשניה מחשב 10 בחזקת 20 פעולות בשניה(מדובר על עצום. פי מאה מליארד יותר מהר) עדיין עבור לוח של 25 על 25 הזמן שיקח לפתור את הבעיה הוא מליון שנים. ככה שכנראה לעולם לא נוכל לפתור את הבעיה של חידת המלכות עבור לוח של 25 על 25 ע"י האלגוריתם שתואר. בלי קשר להתפתחות הטכנולוגיה. ועם בטעות נוכל לפתור עבור לוח של 25 על 25 משבצות לא נוכל לעשות זאת על לוח של 35 על 35 משבצות. *נ.ב כמובן שבדיקת מצב אינה פעולה יחידת של המעבד, לצורך הדיון אפשר להתייחס לכל תהליך בדיקת המצב כפעולה יחידה. בפועל לא התפלא כלל אם בדיקת מצב יחיד לוקחת עשרות אלפי פעולות מעבד. |
 |
 |
 |
|
|
|
||
|
||||
|
פתרון לגדלים שלא מתחלקים ב 2 או 3: --#-------- ----#------ ------#---- --------#-- ----------# -#--------- ---#------- -----#----- -------#--- ---------#- #---------- חסכנו מיליארד שנה עכשיו נותרו עוד שני שליש מהמקרים |
|
|
|
|
|
|
||
|
||||
|
האם יש הוכחה שלכל לוח (ריבועי) יש לפחות פיתרון אחד לבעיה? | |
|
|
|
|
|
||
|
||||
|
ללוח 2X2 אין פתרון | |
|
|
|
|
|
||
|
||||
|
צודק. וחוץ ממנו? | |
|
|
|
|
|
||
|
||||
|
בסדר, בסדר, התכוונתי האם יש מספר שהחל ממנו תמיד יש לפחות פיתרון אחד, והאם המספר הזה הוא ליד 8. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שזה מספק אינטואיציה, גם אם לא הוכחה ממשית: (מספר פתרונות לבעיה כפונ' של מספר המלכות) |
|
|
|
|
|
|
||
|
||||
|
תודה! יש הכללה למימדים גבוהים? | |
|
|
|
|
|
||
|
||||
|
אני לא יודע על הוכחה, אבל החל מ 4X4 (ארבע זה ליד 8?1) יש פתרון, שכמובן אינו יחיד, כי אתה תמיד יכול לסובב את הלוח ב 90° (ארבעה פתרונות "שונים") וגם להציב אותו מול מראה. ___ 1 כשהייתי שסין לאחרונה, שאלתי את אחד הסינים שעבדתי מולו, האם הוא במקורו משנחאי. הוא השיב שהוא מעיר ליד שנחאי. מה זה ליד? במכונית ארבע שעות נסיעה. |
|
|
|
|
|
|
||
|
||||
|
כאשר הרצתי את התוכנה למצוא את כל הפתרונות אז מ-5 ועד 10 או 12 כמות הפתרונות רק הלכה וגדלה. זה לא מוכיח כלום אבל זאת אינדקציה. כאשר הרצתי את התוכנה למציאת פיתרון יחיד נמצא פתרון לכל המספרים הגדולים מ-5 עד 20(מעבר לזה היו בעיות בתוכנה שנבעו בעיקר משום שהשתמשתי ב-dos לא משהו שאי אפשר לפתור). לפי דעתי יש הוכחה שיש פיתרון יחיד עבור כל n>5 (כאשר n מספר השורות והעמודות). וגם יש טכניקה למצוא פיתרון יחיד שכזה. אבל לא בטוח בקשר לעניין. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |