חידה נפוצה בשיעורי הבית של תלמידי קורסים לבינה מלאכותית היא:
בהנתן לוח בגודל NxN, יש לסדר N מלכות כך שאף אחת לא מאיימת על השניה.
כמובן שאני כותב על זה כי קיבלתי את השאלה הזו בשיעורי הבית שלי בקורס מבוא לבינה מלאכותית.
האלגוריתם שפותר את החידה בצורה יעילה הוא אלגוריתם אקראי חמדני:
מכיון שיש N עמודות, וN מלכות, ברור שיש מלכה בכל עמודה.
אז נשים בכל עמודה מלכה, אבל צריך לבחור גם את השורה.
הרעיון הוא להגריל את השורות בהתחלה, ואז בכל סיבוב להזיז מלכה אחת למקום שמקטין הכי הרבה את מספר המלכות המאויימות.
כך בכל סיבוב מספר המלכות המאויימות קטן, עד שמגיעים ל0, או שמגיעים למצב שבו אי אפשר לשפר יותר – כי התחלנו לא טוב, ואז מתחילים מחדש, מגרילים מספרים וחוזר חלילה, עד שהמלכות מסתדרות באורח פלא.
השאלה לא היתה שאלה אלגוריתמית אלא מימושית, האלגוריתם הוסבר בבהירות רבה בשאלה, ורק נשאר לבחור שפה ולממש.
בניגוד למטלה הקודמת, בה בחרתי בפרולוג לפתרון של סודוקו, מה שלמרבה הצער שרף הרבה זמן והביא לתוצאות מפוקפקות, הפעם החלטתי ללכת על שפת הבית – הרי היא ג'אווה.
תוך בערך שעה העסק היה די כתוב, חוץ מזה שהוא לא עבד – לפעמים האלגוריתם נתקע בלולאה אינסופית, ולפעמים פתר את הבעיה בקלות.
בהתחלה הדפסתי את הלוח למסוף הטקסט, אבל מהר מאוד הבנתי שככה לא נגיע רחוק:
מאוד קשה לזהות תבניות שחוזרות על עצמן כשהן מודפסות כטקסט, וגם קשה לראת אם המלכות מאיימות אחת על השניה באלכסון.
החלטתי לעשות את מה שאני עושה טוב, וכתבתי ממשק שמציג סימולציה של האלגוריתם בג'אווה, ובעזרתו מצאתי את הבאגים.
חשבתי לעצמי, אם כבר הגעתי לכאן, נשקיע עוד קצת ונהפוך את זה ליותר שימושי:
הפכתי את הישום לאפלט, מה שמאפשר להריץ אותו גם בדפדפן, והוספתי כמה כפתורים ששולטים על הסימולציה.
התוצאה לפניכם:
נסו לשחק עם זה, בכל פעם שהוא נתקע הרקע הופך לאדום והוא מגריל מחדש.
שימו לב שאפשר לפתור עם זה גם לוחות גדולים מאוד.
עוד דברים שכדאי לשים אליהם לב זה שיש בעיה עם לוחות קטנים (כמה קטנים?), ושכל פעם הוא נותן פתרון אחר כי ההתחלה אקראית.
האפלט כאן, הקוד כלול בפנים (מי שרוצה את הקוד, שישמור את הJAR ויפרוש אותו עם WinZip או תוכנת זיפ אחרת, הקוד בפנים).
יפה.
אני לא מבין משהו:
"
הרעיון הוא להגריל את השורות בהתחלה, ואז בכל סיבוב להזיז מלכה אחת למקום שמקטין הכי הרבה את מספר המלכות המאויימות.
כך בכל סיבוב מספר המלכות המאויימות קטן, עד שמגיעים ל0, או שמגיעים למצב שבו אי אפשר לשפר יותר – כי התחלנו לא טוב, ואז מתחילים מחדש, מגרילים מספרים וחוזר חלילה, עד שהמלכות מסתדרות באורח פלא.
"
למה ההגרלות ? האם אי אפשר להתחיל בזה שכל המלכות נמצאות בשורה הראשונה, למשל ? כך מתחילים מנקודת מוצא אחידה, והאלגוריתם יותר מעניין (לדעתי).
אבל זו כמובן הערה קטנה.
בנוסף, אני אשמח אם תוכל לעשות כפתור של "הסידור הבא", כך שאפשר יהיה לנחש את הצעדים. שים לב: לא החישוב הבא, אלא הסידור הבא.
בכל אופן, באמת יפה ומעניין.
אפשר לנסות, אבל הניחוש שלי הוא שהאלגוריתם יתקע עבור nים מסויימים, ויהיה פחות יעיל באופן כללי.
אתה יכול להסביר יותר טוב למה אתה מתכוון עם "הסידור הבא"?
טוב, עכשיו אני מבין למה הגרלה של המיקומים: אמרת שהאלגוריתם אקראי.
מה זה אומר "חמדני" ?
זה שאמרתי שהוא אקראי זה כי הוא מגריל.
הוא לא מגריל כי אמרתי שהוא אקראי.
אלגוריתם חמדני תמיד מחפש מקסימום מקומי למהלך הבא. הוא לא מתסכל קדימה, אלא רק על המהלך הבא.
דוגמא לאלגוריתם חמדני מוכר הוא האלגוריתם להחזרת עודף של מכונות שתיה:
בכל פעם הוא בוחר את היחידה (שטר/מטבע) הגדול ביותר שאפשר להחזיר לך (בלי להחזיר יותר מדי).
אלגוריתמים חמדניים הם מאוד יעילים בדרך כלל, אבל יש בעיות שאי אפשר לפתור בעזרת אלגוריתם חמדני.
אוקיי, אז אם עניין ההגרלה אינו משמעותי, אני חושב שכדאי לשים את כל המלכות בשורה הראשונה, כך ההתקדמות תהיה ברורה יותר. לדעתי אם אין תועלת בהגרלה, עדיף לא להשתמש בה, ולו רק מטעמי בהירות ודייקנות. זו דעה לא מקצועית.
אני אמרתי שהוא לא משמעותי?
הוא מאוד משמעותי, האלגוריתם יתקע עבור לוחות מסויימים, ובאופן כללי יהיה יותר איטי.
אתה מוזמן להוריד את הקוד ולשנות אותו ככה שהוא יעשה מה שאתה מציע, ולראות מה קורה.
אוקיי, תודה.
מה עם עץ החלטות?
1. שים מלכה במקום ראשון בשורה ראשונה
2. שים מלכה שניה במקום הראשון בשורה שניה כך שזה לא יתנגש עם הראשונה
3. תמשיך עד שתגיע לתוצאה טובה או ל DEAD END, במקרא זה תחזור אחד אחורה ותזיז את המלכה הקודמת למקום הבא אפשרי. תחזור יותר עמוק בעץ אם יש צורך.
אלגוריתם זה הוא אקספוננציאלי ביחס לכמות המלכות ולכן לא מתאים ללוחות ממש גדולים, אבל גם אלגוריתם שלך לא נשמע לי טוב יותר. פתרון זה כמובן מתאים מצויין לפרולוג, צריך רק להפוך אותו ל- tail recursive
אגב בעיה זו מתאימה מצויין לפתרון באלגוריתמים גנטיים, כמו כן נראה לי שאפשר לעשות לה רדוקציה לאחת הבעיות גרפים.
לילה טוב.
האלגוריתם "שלי" הוא לינארי למספר המלכות.
בדקתי את זה.
מה שלוקח זמן ריבועי זו הבדיקה עצמה, ואת זה אני יכול לשפר.
מספר האיטרציות בממוצע הוא מסביב לN
מה המצב עמרי?
יצא נחמד מאוד..
לויטאלי , כל הרעיון באלג זה הוא לקבל אלג יותר מהיר מעץ החלטה.
עץ החלטה הוא למעשה חיפוש (עיוור או יוריסטי), ספציפית למקרה הזה ייקח המון זמן בלוחות גדולים (כמו שאמרת אקפונינציאלי).
האלג' הנוכחי יהיה יחסית מהיר במקרה הממוצע (ייתכן שיהיו הרבה הגרלות על הפנים אבל לרוב זה לא רע)
הסיבה (לא פורמאלית…)היא שבעץ החלטה אתה מתחיל מכלום ומתקדם וספציפית במקרה הזה תצטרך המון המון חזרות אחורה והאלג לא יהיה מעשי בנניח לוח בגודל 60…
לעומת זאת באלג הנוכחי , מכיוון שיש המון מצבים אפשריים לסידור טוב אנחנו מתחילים ממצב כלשהו (כאשר ידוע לנו רק שאין בעיה באותה עמודה) ורק מנסים לתקן,
אם לא ניתן מתחילים מחדש.
ככה כל כמה הגרלות (ולא יותר מדי) נגיע למצב לא רע , שלאחר כמה תיקונים נקבל מצב טוב.
היי עומרי
אומנם ההודעה הזו מפני שנה אבל אשמח לקבל את תגובתך….
אני עושה את הקורס עכשיו וקראתי שרשמת "מספר האיטרציות בממוצע הוא מסביב לN " – האם יש הוכחה לכך/איך הגעת ל N ?
הלוואי שתענה 🙂
אשמח אם תיצור איתי קשר במייל
וכמובן תודה מראש, גיא
גיא, אין לי הוכחה, אבל בבדיקה זה המצב:
הרצתי את האלגוריתם מספר רק של פעמים על כל N עד איזה שהוא מספר די גדול ואכן מספר האיטרציות הממוצע קרוב לN.
עמרי שלום…
אם תוכל לפרסם את הקוד או לשלוח לי למייל הכתוב… ז"א את התיכנות עצמו אני אשמח
תודה…
רונית: יש קישור לקובץ JAR בפוסט, והוא מכיל את הקוד. תפתחי אותו עם תוכנת ZIP.
אשמח אם תשלחו אליי
עמרי שלום
אמשח לקבל את הקוד לא הבנתי מאיפה ניתן להוריד אותו ..
תודה
תוכל לפרוש את קובץ הJAR עם WINZIP, הקוד בפנים.