רוטר - צריך עזרה בבחירת אלגוריתם שמוצא את המסלול הקצר ביותר

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"צריך עזרה בבחירת אלגוריתם שמוצא את המסלול הקצר ביותר"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15783	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 15783

ronen333
חבר מתאריך 20.2.03
6069 הודעות

16:11 24.03.10

צריך עזרה בבחירת אלגוריתם שמוצא את המסלול הקצר ביותר

היי חבר'ה, זה שוב לגבי המשחק שלי :P.
אני צריך לעשות שהאויבים ימצאו את הדרך הקצרה ביותר ביותר לבסיס.
עכשיו יש לי מטריצה בעלת 1,296 תאים כשאר כל תא מציין למעשה משבצת במשחק שלי.
חשבתי בהתחלה להשתמש בBFS על מנת למצוא את המסלול הקצר ביותר(כאשר כל משבצת היא קודקוד) אבל זה לא יעיל כי אז הוא למעשה יסרוק כמליון תאים בכל זמן קצר מאוד של זמן.
(הרי אם יש לי X קודקודים אז יש לי X בריבוע קשתות מיפני שזהו לא גרף דליל והאלגוריתם רץ בסיבוכיות שלE+V).
אני למעשה צריך להריץ את האלגוריתם הזה בכל פעם שמניחים נשק/מכשול ככה שאני צריך אלגוריתם יעיל.

מה אתם מייעצים לעשות?

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
A*	Net_Boy	24.03.10 20:06	1
קח בחשבון שחשוב שהיוריסטיקה תהיה חסומה מלמטה בשביל שהיא תהיה קבילה	ldan192	24.03.10 22:33	2
כן רשום על זה בוויקיפדיה	ronen333	25.03.10 11:58	4
אם אתה רוצה להבטיח שהאלגוריתם יעצור ויתן גם את המסלול	ldan192	26.03.10 00:41	5
אמ כן לא יזיק =]	ronen333	26.03.10 12:03	7
אגב, עוד משהו ששכחתי בנוגע לקבילות. חובה ש-	ldan192	26.03.10 12:17	9
אווקי :)	ronen333	26.03.10 12:31	11
אם יש לך מצגת על זה או משהו	ronen333	26.03.10 12:31	10
יש, אבל הם שקפים דיי גרועים, מעבירים את רוב החומר בע''פ	ldan192	26.03.10 13:03	12
תודה רבה!!! :)	ronen333	26.03.10 13:22	13
שאלה:	ronen333	27.03.10 16:21	15
הכוונה למחסנית ממויינת לפי f=g+h. ככה אתה מוציא	ldan192	27.03.10 16:28	16
מכתב	ronen333	27.03.10 20:13	17
אה, כן, כנראה רפרפתי על התגובה. בכל מקרה, זה נורא תלוי	ldan192	28.03.10 21:24	18
נראה לי שסיימתי לממש את A STAR :)	ronen333	01.04.10 14:28	19
ד''א הפונקציה היורסטית שלי היא מרחק אוקלידי	ronen333	01.04.10 15:22	20
בכיף :) ול-A* בקטע הזה יש ביצועים בערך כמו דיאקסטרה...	ldan192	01.04.10 21:22	21
תודה רבה :)	ronen333	25.03.10 11:56	3
שאלה:	Zippo	26.03.10 01:25	6
תודה על התגובה אבל מה שהצעת נשמע לי כמו BACKTRACKING	ronen333	26.03.10 12:10	8
לגבי יעילות אני באמת לא בטוח, אבל לגבי מסלול קצר,	Zippo	26.03.10 13:25	14

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק

20:06 24.03.10

1. A*
בתגובה להודעה מספר 0

http://en.wikipedia.org/wiki/A*_search_algorithm

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

22:33 24.03.10

2. קח בחשבון שחשוב שהיוריסטיקה תהיה חסומה מלמטה בשביל שהיא תהיה קבילה
בתגובה להודעה מספר 1

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

11:58 25.03.10

4. כן רשום על זה בוויקיפדיה
בתגובה להודעה מספר 2

אבל אני לא בטוח מה הכוונה.. תוכל להרחיב קצת בבקשה?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

00:41 26.03.10

5. אם אתה רוצה להבטיח שהאלגוריתם יעצור ויתן גם את המסלול
בתגובה להודעה מספר 4

הקצר ביותר, אז אתה צריך שהיוריסטיקה תהיה חסומה מלמטה.
A* בנוי ככה שעלות כל צומת successor היא f=g+h כאשר g זה משקל המסלול ו-h זו היוריסטיקה להגיע לצומת המטרה...
מעבר לזה, האלגוריתם דיי טרוויאלי וקל. אני מסכים עם עומר שכדאי לך להתחיל ממנו.

אגב, אתה צריך עדיין את הקטע עם ספירת השורות?

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

12:03 26.03.10

7. אמ כן לא יזיק =]
בתגובה להודעה מספר 5

ובקשר לA STAR- יש מצב שאני אצטרך עזרה בקשר לזה נראה לי לא כזה פשוט ליישם אותו כמו שאתה מתאר :P.
אז בבקשה תהיו מוכנים ^^ אני בסוף פסח צריך להגיש את זה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

12:17 26.03.10

9. אגב, עוד משהו ששכחתי בנוגע לקבילות. חובה ש-
בתגובה להודעה מספר 7

0<=h(n)<=h*(n)

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

באמת אלגוריתם פשוט.. יותר פשוט מרוב המימושים שתחשוב עליהם.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

12:31 26.03.10

11. אווקי :)
בתגובה להודעה מספר 9

וראה בבקשה תגובה 10 ^^.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

12:31 26.03.10

10. אם יש לך מצגת על זה או משהו
בתגובה להודעה מספר 7

זה מאוד יעזור

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

13:03 26.03.10

12. יש, אבל הם שקפים דיי גרועים, מעבירים את רוב החומר בע''פ
בתגובה להודעה מספר 10

אבל קח:
הרצאה:
http://webcourse.cs.technion.ac.il/236501/Winter2009-2010/ho/WCFiles/optiimizing-search.pdf

תרגול ישן וישן מאוד :
http://webcourse.cs.technion.ac.il/236501/Winter2009-2010/ho/WCFiles/t4.pdf
http://webcourse.cs.technion.ac.il/236501/Winter2009-2010/ho/WCFiles/AStar.pdf

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

13:22 26.03.10

13. תודה רבה!!! :)
בתגובה להודעה מספר 12

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

16:21 27.03.10

15. שאלה:
בתגובה להודעה מספר 12

OPEN וCLOSE אמורות להיות תור קדימויות? כי לא רשום על זה וזה חשוב...
רשום POP אבל אני מניח שהם לא התכוונו למחסנית...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

16:28 27.03.10

16. הכוונה למחסנית ממויינת לפי f=g+h. ככה אתה מוציא
בתגובה להודעה מספר 15

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

אני הייתי ממש את ה-CLOSE עם hashtable ואת ה-OPEN עם ערימת מינימום.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

20:13 27.03.10

17. מכתב
בתגובה להודעה מספר 16

אווקי תודה , תור קדימויות זה שם נרדף לHEAP .
עכשיו הצעת לעשות את CLOSE עם HASHTABLE.. מה יהיה המפתח ומה יהיה הערך לא הבנתי X=

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

21:24 28.03.10

18. אה, כן, כנראה רפרפתי על התגובה. בכל מקרה, זה נורא תלוי
בתגובה להודעה מספר 17

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

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

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

14:28 01.04.10

19. נראה לי שסיימתי לממש את A STAR :)
בתגובה להודעה מספר 18

ערכתי לאחרונה בתאריך 01.04.10 בשעה 15:00 בברכה, ronen333

יש מצב אני שולח לך את מה שכתבתי ותאמת את זה בבקשה?

יש תיעוד מלא והכל
נ.ב-מטודות כמו REMOVE,FIND וCONTAINS אני לא יכול לעשות יותר טוב מטטא של N נכון? (כאשר אני צריך למצוא בתור קדימויות חוליה ספציפית לדוג')
עוד שאלה:
המשחק שלי יריץ את האלגוריתם כל פעם עכשיו שנוצר אויב או שנוצר נשק (ביגלל שזה מקוקדקוד ספציפי לקודקוד ספציפי אחר) לעומת נניח אם הייתי משתמש בדיאקסטרה זה מחשב את המסלול הקצר מכל קודקוד לכל קודקוד ואז הייתי צריך להריץ את זה רק כאשר מניחים נשק. חבל שרק עכשיו אני חושב על זה, אבל יתכן שדיאקסטרה יהיה יותר יעיל במקרה הזה? כי כל כמה שניות יווצר אויב חדש, וכל פעם שנוצר אויב חדש אני אמור להריץ את האלגוריתם על כל אחד מהאויבים... FUCK.
או שA* יעיל כל כך בהרבה מדיאקסטרה שA* עדיין יותר טוב?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

15:22 01.04.10

20. ד''א הפונקציה היורסטית שלי היא מרחק אוקלידי
בתגובה להודעה מספר 19

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

21:22 01.04.10

21. בכיף :) ול-A* בקטע הזה יש ביצועים בערך כמו דיאקסטרה...
בתגובה להודעה מספר 19

ואני לא בטוח איך אתה יכול לממש דיאקסטרה בלי יוריסטיקות.
אבל יכול להיות שפספסתי משהו באיך המשחק עובד.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

11:56 25.03.10

3. תודה רבה :)
בתגובה להודעה מספר 1

ערכתי לאחרונה בתאריך 25.03.10 בשעה 11:59 בברכה, ronen333

שמעתי על האלגוריתם ובאמת חשבתי עליו כאופציה (המרצה שלי המליץ לי בתור זריקת מחשבות על BFS [שאותו למדנו] או A STAR [שאותו לא למדנו])..
אשמח אם תוכלו להסביר עליו קצת בפשטות

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zippo
חבר מתאריך 26.5.02
7921 הודעות

01:25 26.03.10

6. שאלה:
בתגובה להודעה מספר 0

מכיוון שמדובר בלוח משבצות, ולא בשטח חופשי, אז צעד חיובי, בין אם על ציר ה-X או על ציר ה-Y "יעלה" מבחינת מרחק אותו דבר בדיוק.
כלומר, מספר המהלכים הכי קצרים, יהיו בוודאות מספר האפשרויות לנוע בצעדים חיוביים בלבד על שטח מסוים.
כמובן שאם תשים מכשול, זה יפריע, אבל אלא אם כן תחסום את כל היציאות מאותו segment זה לא ישפיע על המרחק שצריך לעבור.
מה שאני אומר בגדול:
תחלק את השטח שהיחידה צריכה לעבור ל-segment-ים מלבניים.
בכל שטח מלבני שכזה, מספר הדרכים להגיע מפינה אחת לנגדית במהלכים חיוביים בלבד הוא בדיוק 2*(n-1) מעל (n-1)
כאשר n = width + height
מכיוון שכל המהלכים האלה שווים באורכם, אין צורך לחשב מההתחלה כמה יקח כל אחד מהם.
אז שלב ראשון, תפרק את כל השטח שצריך לעבור לשטחים מלבניים קטנים שחופפים בפינות.
ובכל שטח כזה, כשאתה מגיע אליו, תעשה את החישוב, שכמובן לא יעבור על הכל, אלא ילך על הנתיב הראשון שפנוי לו.
זמן החישוב ממש לא נורא, והבעיה היחידה שאני לא יודע איך לפתור עדיין, היא מה קורה במצב שאין אפשרות להגיע במהלכים חיוביים בלבד.
האם הנקודה הראשונה שממנה כן יהיה אפשר להגיע במהלכים חיוביים בלבד תהיה היעד החדש, שאליו אני צריך להגיע בצעדים חיוביים, וגם אל הנקודה הזאת אין אפשרות אז שתהיה מן רקורסיה כזאת שכל פעם תהיה נקודת מוצא אחרת...?
לא יודע עד כמה זה יעיל...

בכל אופן, אם בודקים מהלכים חיוביים בלבד, הפיתרון הנאיבי לא נורא.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות

12:10 26.03.10

8. תודה על התגובה אבל מה שהצעת נשמע לי כמו BACKTRACKING
בתגובה להודעה מספר 6

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Zippo
חבר מתאריך 26.5.02
7921 הודעות

13:25 26.03.10

14. לגבי יעילות אני באמת לא בטוח, אבל לגבי מסלול קצר,
בתגובה להודעה מספר 8

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד