היי חבר'ה מצטער עם הפצצת השאלות בנושא, הוא די חדש לי במימוש מכיוון שעד לא ממזמן הכל היה רק בתאוריה. כזכור מהפרקים הקודמים ( ), יש לי מטריצה בעלת 1,296 תאים כשאר כל תא מציין למעשה משבצת במשחק שלי. מטריצת BYTES.. ש0 מציין תא שאפשר ללכת בו וכל מספר אחר מציין שאי אפשר(קיים מכשול). בהתחלה עשיתי את המטריצה הזאת במטרה שהיא תיהיה מטריצת שכנויות ולכל קשת יהיה אותו משקל מכיוון שלהגיע למשבצת אחת למעלה, אחת למטה, אחת אחורה, ואחת קדימה זה בדיוק אותו המרחק. אבל מה התוכניות קצת השתנו, עכשיו הגרף שלי לפי הלאגוריתם הוא רשימת NODES שבכל NODE יש רשימת קשתות. אני כבר לא יודע מה לעשות, אני צריך דרך יעילה לבנות את הקדקודים והקשתות. מה מציעים לעשות?
מה שאני שואל זה איך אני עושה גרף דינאמי? כי להתחיל לבנות גרף בהתאם למטריצה 60 פעם בשניה נראה לי קצת בזבזני ולא יעיל(אני צריך בשביל זה לעשות סריקה של כ3000 תאים).
ערכתי לאחרונה בתאריך 02.04.10 בשעה 16:21 בברכה, ronen333
לסריקה של כ1000 במקום כ3000 (ע"י זה שהתייחסתי אל הרשימה כמטריצה מבחינת חישוב הגעה לחוליות-כמה טוב שיש C# ואפשר והתייחס לרשימה כאל מערך באמצעות INDEXERS ). זה עדיין לא משהו לבנות כל פעם גרף אז אני מחכה להצעות
1. מטריצת שכנויות, מן הסתם עבור גרף דליל זאת לא אפשרות טובה. 2. רשימת שכנויות - לכל צומת v מחזיקים ברשימה מקושרת את כל הצמתים u אם יש קשת מכוונת מ-u ל-v. כמו כן יש רשימה שמתחזקת את רשימת הצמתים.
השאלה היא לא איך ליצור גרף. אלא איך ליצור גרף דינאמי. אני רוצה שהקשתות ישתנו במהלך המשחק בלי שתיהיה סיבוכיות גבוהה מידי. מה שאני עכשיו עושה זה לבנות גרף כל פעם מחדש (60 פעם בשניה) והסיבוכיות של זה זה O(N) ש N זה מספר הצמתים הכולל. מספר הצמתים הכולל במשחק שלי הוא 1000. השאלה אם זה יעיל.. לי נראה שלא. הייתי רוצה לעשות שאני בונה גרף פעם אחת בהתחלה, ואז פשוט לעדכן אותו בסיבוכיות ממש טובה כאשר האויבים שלי זזים במשחק לדוגמה.
60 גרפים בשניה זה לא קצת.. תנסה לחשוב על פתרון יעיל יותר.. יש דברים שעל הנייר נראים יפים עם O(n) וכדומה..אבל ברגע שיש ניתוח amortized רואים מה קורה בתכלס..