שאלה...

[the html man]

שאלה...

המטרה היא לפתור קובייה הונגרית. יש לי קובייה - שמיוצגת ע"י 3 שכבות (מחלקות) שיש בתוכן את מס' הקוביות שצריך. יש לי את כל הפרטים על כל 'קוביתייה' (קובייה קטנה). אני לבד יודע לפתור קובייה (בדקה וחצי

), אבל נראה לי קצת מסובך (בלתי אפשרי?) שהמחשב ייפתור. האם למישהו יש רעיון או קצה חוט לאלגוריתם? אני עושה את זה ב-Managed DirectX (זאת אומרת C#), לכן אם זה לא המקום אנא הפנו אותי

תודה!

 

[vinney]

אני לא בטוח שמחשב יכול "לפתור"

אני יורה באפילה, אבל לדעתי מה שצריך זה מניית כל האפשרויות+מעברים. זה יצור לך גרף שבסופו של דבר כל מה שאתה צריך זה מסלול מהמצב הנוכחי שלך למצב הסופי. אם יש כזה מסלול => יש פתרון, אם אין מסלול=> אין פתרון. ואם יש מסלול, אז אתה פשוט מצייר אחד אחרי השני את כל אחד מהמצבים שאתה עובר בדרך

 

[the html man]

מחשב

יכול לעמוד בכ"כ הרבה חישובים? כי יש 42,000,000,000,000,000 מצבים לקובייה (בערך)

 

[vinney]

כנראה שלא ../images/Emo13.gif

 

[ahab]

ודאי שמחשב יכול

קיימים אלגוריתמים לפתרון. ובמקרה הגרוע, תמיד אפשר לבצע חיפוש בגרף, כפי שויני הציע, לפי היוריסטיקה מסוימת. להזכירך, מחשבים מסוגלים להתמודד כיום עם בעיות בעלות מספר מצבים הרבה יותר גדול. השיטה, כמובן, היא לא ליצור את כל הגרף בו-זמנית, אלא לפתח צמתים בגרף לפי כיוון ההתקדמות.

 

[the html man]

הלינק שהבאת

חמוד ביותר

תודה!

 

[vinney]

וואלה, מאגניב, הייתי בכיוון ../images/Emo13.gif

אני חשבתי על לעשות רשימת כל הצבים מהם אפשר להגיע למצב הפתרון (שזה הרבה פחות מכל המצבים האפשריים), ואז פשוט הבעיה מצטמצמת למינימום - לבדוק אם המצב הנתון ברשימה או לא, ואם כן - לקחת כל פעם את המצב הבא (לא חייבים שיהיה הכל בזכרון, ועל דיסק אפשר להכיל הרבה מאוד דברים), ולצייר. תכל'ס - מספר המצבים הוא סופי, כך שזה לא בעיה. אבל בטוח שיוריסטיקות יכולות לצמצם את זה הרבה יותר, רק שאין לי כוח להתעסק עם ניחושים

אגב, לבנות רובוט מלגו זה חמוד

 

[the html man]

עכשיו שאני חושב על זה

גם ככה פותרים את הקובייה בשלבים (כל אחד איך שהוא רוצה - אני למשל מתחיל מצלב בשכבה העליונה, לסיים את שכבה העליונה, פינות שכבה תחתונה, שאר שכבה תחתונה ושכבה אמצעית

) אז בעצם אני כל פעם רק צריך לבדוק איך מגיעים למצב הבא... שזה ממש לא הרבה חישובים... תודה לכולם!