romhayh/algo-1-task

מטלה להגשה אלגוריתמים רום חי חממה

https://github.com/romhayh/algo-1-task/tree/main

טבלאות זמני ריצה

פאזל 15 - 10 מהלכי ערבוב:

פאזל 1:

1	2	3	4
5	6	8
9	10	7	15
13	14	12	11

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
836	9	9.12ms	BFS
629	9	3.2ms	Dijkstra
14	9	0.13ms	Manhattan
1480	9	4.69ms	Incompatible

פאזל 2:

1	2	3	4
5	6	7	8
9	10	11	12
13		14	15

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
9	3	0.03ms	BFS
6	3	0.02ms	Dijkstra
3	3	0.02ms	Manhattan
163	3	0.44ms	Incompatible

פאזל 3:

	1	3	4
5	2	11	7
9	6	10	8
13	14	15	12

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
666	9	1.54ms	BFS
779	9	1.89ms	Dijkstra
9	9	0.05ms	Manhattan
7021	9	20.03ms	Incompatible

פאזל 4:

1	2	3	4
5	6	7	8
9	15		11
13	10	14	12

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
278	7	0.67ms	BFS
212	7	0.45ms	Dijkstra
9	7	0.05ms	Manhattan
1304	11	2.9ms	Incompatible

פאזל 5:

1	2	3	4
5	6	7
9	10	11	8
13	14	15	12

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
5	3	0.07ms	BFS
10	3	0.13ms	Dijkstra
3	3	0.04ms	Manhattan
7	3	0.08ms	Incompatible

---

פאזל 24 - 10 מהלכי ערבוב:

פאזל 1:

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16		17	18	20
21	22	23	19	24

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
78	5	0.27ms	BFS
60	5	0.2ms	Dijkstra
5	5	0.06ms	Manhattan
147	5	0.49ms	Incompatible

פאזל 2:

1	2		3	4
6	7	8	9	5
11	12	13	14	10
16	17	18	19	15
21	22	23	24	20

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
340	7	2.24ms	BFS
281	7	0.65ms	Dijkstra
7	7	0.04ms	Manhattan
2412	7	5.47ms	Incompatible

פאזל 3:

1	2	3	4	5
6	7	8	9	10
11	12		13	15
16	17	18	14	24
21	22	23	20	19

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
2449	9	5.93ms	BFS
2337	9	4.04ms	Dijkstra
14	9	0.17ms	Manhattan
1020	9	1.96ms	Incompatible

פאזל 4:

1	2	3	4	5
6	7	8	9	10
11	12		14	15
16	17	13	18	20
21	22	23	19	24

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
54	5	0.11ms	BFS
90	5	0.12ms	Dijkstra
5	5	0.01ms	Manhattan
591	5	1.15ms	Incompatible

פאזל 5:

1	2	3	4	5
6	7	8	9	10
11	12	13	19	14
16	17	18		15
21	22	23	24	20

מצבים שנבדקו במהלך הרצת האלגוריתם	כמות הצעדים של הפתרון	זמן ריצה	אלגוריתם
52	5	0.09ms	BFS
82	5	0.11ms	Dijkstra
5	5	0.01ms	Manhattan
12	5	0.03ms	Incompatible

---

4X4

מצבים שנבדקו במהלך הרצת האלגוריתם בממוצע	כמות הצעדים הממוצעת של הפתרון	זמן ריצה ממוצע	אלגוריתם
213.9	5.44	0.42ms	BFS
266.6	5.44	0.4ms	Dijkstra
5.68	5.44	0.01ms	Manhattan
1132.98	5.44	2.04ms	Incompatible

5X5

מצבים שנבדקו במהלך הרצת האלגוריתם בממוצע	כמות הצעדים הממוצעת של הפתרון	זמן ריצה ממוצע	אלגוריתם
530.16	5.6	0.89ms	BFS
500.96	5.6	0.82ms	Dijkstra
5.82	5.6	0.01ms	Manhattan
2190.04	5.72	4.7ms	Incompatible

מסקנות מהעבודה

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

עוד נקודה שאפשר להוסיף היא שbfs ודייאקסטרא מתנהגים כמעט אותו הדבר ברוב המקרים. המצב קורה בגלל ששני האלגוריתמים עושים את אותה פעולה באופן שונה. הם סורקים את גרף הקלט עד למציאת פתרון, לא באופן חכם. BFS וגם Dijakstra לא מותאמים לעשות את המשימה באופן יעיל, אך הם כן מתאימים למציאת פתרון. BFS מותאם לחישוב המסלול הקצר ביותר ולא הקל ביותר, ולכן אינו מתאים למשימה. Dijakstra בגלל חמדנותו, עובר על כל המהלכים הקרובים ביותר לפי סדר מנקודת ההתחלה, ובשל היותו חמדן הוא לא מצליח לייעל את התהליך של מציאת פתרון ומגיע לתוצאה בכמות מצבים שנבדקו שדומה לBFS, שלפי הגדרה יסרוק את כל הגרף. הוא נכשל פה מכיוון שהלוחות נכנסים לתור העדיפויות לפי כמות המהלכים להגיע אליהם מלוח המקור, מה שאומר שהוא סורק את הגרף לרוחב, כל פעם מנסה לעבור על ה"דרגה" של מהלכים עד למציאת פתרון, ואם הוא לא מצא בדרגה הנוכחית, יעבור ל"דרגה הנוגחית + 1" של מהלכים מלוח המקור. ככה עובר הדייאקסטא על גרף הקלט, סורק שכבה שכבה, שלכל שכבה דרגה שונה.

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

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

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