מה שמתכנתים עושים
מעין משחקת כל מיני משחקי פזלים שונים ומשונים, מחיפוש חפצים רגיל ועד פזלים קלאסיים של מתגים שמשפיעים אחד על השני. לפעמים היא גם מבקשת עזרה ממני אם הפאזל לוקח יותר מכמה דקות.
לפני כמה ימים היא נתקלה בפאזל וביקשה ממני לעזור. אחרי שהסבירה לי את הבעיה, אמרתי “ובכן, זאת בדיוק בעיה של מציאת מסלול המילטוני בגרף מכוון” (מסלול המילטוני הוא מסלול שעובר דרך כל צומת בדיוק פעם אחת).
אפשר לפתור את זה בניסוי וטעייה, עם קצת רישום והרבה השקעה אבל אנחנו מתכנתים. אחרי שבנינו את הגרף וניסינו לראות אם יש בו איזה שהוא נתיב ברור ללא הצלחה, הצעתי לכתוב תוכנה שתפתור את זה.
כן, למצוא מסלול המילטוני זאת לא בעיה פשוטה. היא NP-Complete. הפתרון הכללי הטוב לוקח (O(n^2*2^n ולא ציפיתי שאפילו נגיע לזה כי כל מה שרציתי זה חיפוש פשוט עם BackTracking. אבל לא נורא, המחשב שלי סבבה ואלו רק 25 צמתים.
אז עבדנו על זה ביחד כשעה וחצי-שעתיים והוצאנו תוכנה קטנה שמוצאת את הפתרון. היא עדיין בעייתית אבל הצלחנו לפתור איתה את הפאזל.
אני חושב שזה היה שווה את הזמן. :)
Posted in IT, Maayan, No Category, Programming by Eran with 1 comment.
if you had as much fun writing the program as trying to solve the puzzle with pen and paper than it did it job and you also got extra skill points for programming on the side.yay.