רוטר - בניית גרף

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

"בניית גרף"

גירסת הדפסה

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

אשכול מספר 15790

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

14:06 02.04.10

בניית גרף

היי חבר'ה
מצטער עם הפצצת השאלות בנושא, הוא די חדש לי במימוש מכיוון שעד לא ממזמן הכל היה רק בתאוריה.
כזכור מהפרקים הקודמים ( ), יש לי מטריצה בעלת 1,296 תאים כשאר כל תא מציין למעשה משבצת במשחק שלי.
מטריצת BYTES.. ש0 מציין תא שאפשר ללכת בו וכל מספר אחר מציין שאי אפשר(קיים מכשול).
בהתחלה עשיתי את המטריצה הזאת במטרה שהיא תיהיה מטריצת שכנויות ולכל קשת יהיה אותו משקל מכיוון שלהגיע למשבצת אחת למעלה, אחת למטה, אחת אחורה, ואחת קדימה זה בדיוק אותו המרחק.
אבל מה התוכניות קצת השתנו, עכשיו הגרף שלי לפי הלאגוריתם הוא רשימת NODES שבכל NODE יש רשימת קשתות.
אני כבר לא יודע מה לעשות, אני צריך דרך יעילה לבנות את הקדקודים והקשתות.
מה מציעים לעשות?

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
אני אסביר את עצמי עוד קצת למקרה שמה שרשמתי לא ברור	ronen333	02.04.10 15:30	1
אווקי הצלחתי עם קצת חישובים לצמצם את זה	ronen333	02.04.10 16:17	2
בגדול, יש 2 דרכים לייצג גרף.	Deuce	02.04.10 17:17	3
כן, אני מכיר את השיטות יצוג האלה	ronen333	02.04.10 20:32	4
זה נשמע לא יעיל בעליל..	VeNom	02.04.10 20:58	5
אני יודע :)	ronen333	02.04.10 22:35	6
לא משנה, תודה לכם	ronen333	05.04.10 11:29	7
בדיוק. אני לא חושב שאתה צריך לחשוב על טבלאות	ldan192	05.04.10 11:31	8

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

15:30 02.04.10

1. אני אסביר את עצמי עוד קצת למקרה שמה שרשמתי לא ברור
בתגובה להודעה מספר 0

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

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

16:17 02.04.10

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

ערכתי לאחרונה בתאריך 02.04.10 בשעה 16:21 בברכה, ronen333

לסריקה של כ1000 במקום כ3000 (ע"י זה שהתייחסתי אל הרשימה כמטריצה מבחינת חישוב הגעה לחוליות-כמה טוב שיש C# ואפשר והתייחס לרשימה כאל מערך באמצעות INDEXERS ).
זה עדיין לא משהו לבנות כל פעם גרף אז אני מחכה להצעות

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

17:17 02.04.10

3. בגדול, יש 2 דרכים לייצג גרף.
בתגובה להודעה מספר 0

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

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

20:32 02.04.10

4. כן, אני מכיר את השיטות יצוג האלה
בתגובה להודעה מספר 3

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

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

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

VeNom

חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק, 2 נקודות

20:58 02.04.10

5. זה נשמע לא יעיל בעליל..
בתגובה להודעה מספר 4

60 גרפים בשניה זה לא קצת..
תנסה לחשוב על פתרון יעיל יותר..
יש דברים שעל הנייר נראים יפים עם O(n) וכדומה..אבל ברגע שיש ניתוח amortized רואים מה קורה בתכלס..

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

22:35 02.04.10

6. אני יודע :)
בתגובה להודעה מספר 5

לכן פניתי לפה ^^

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

11:29 05.04.10

7. לא משנה, תודה לכם
בתגובה להודעה מספר 0

אני בונה את האלגוריתם A STAR ככה שהוא יהיה מותאם יותר למטריצה הקיימת לי במשחק ככה שהיעילות תיהיה O(1) שהגרף משתנה .

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

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

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

11:31 05.04.10

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

אלא על עצי מצבי לוח חוקיים.

בברכה,
עידן

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

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