otherside3
New member
מבוא לרשתות - בעיית שריפה ביער
הי, בוקר טוב.
אנסה את מזלי, אולי למישהו יהיה רעיון טוב.
בבעיה נתון לי גרף עם הרבה קודקודים (כמה עשרות אלפים...) המייצג יער (כמו זה שבו כיפה אדומה הלכה לסבתא שלה, לא יער של BFS ..) כאשר כל קודקוד מייצג עץ, וכל קשת מייצגת קשר בין 2 עצים (אולי היו יחד בגן, אנא עארף..
)
לכל קשת יש ערך מספרי המייצג את חוזק הקשר בין 2 העצים, ולכל עץ יש ערך מספרי המייצג את מידת חסינותו לדליקות. אם עץ דולק באיטרציה i, אז הסיכוי שלו להדליק שכן שלו באיטרציה i+1 הוא (חוזק הקשר) בחזקת (מידת חסינות), ולאחר איטרציה זו נניח שהעץ כבר לא דולק ונשאר שרוף..
העניין הוא כזה - ישנו אדם שבוחר 50 עצים שאותם הוא רוצה להצית, כך שהוא חושב שאותם עצים יצליחו בתורם (תוך פרק זמן כלשהוא, נניח 5 דקות) להצית כמה שיותר עצים אחרים (כלומר שיהיו כמה שיותר עצים שרופים לאחר 5 דקות).
בפועל הנתונים מראים כי תוצאות הבחירה שלו מצליחות לשרוף אחוזים יפים, משהו בסביבות 60%.
המטרה היא למצוא קבוצה של 100 קודקודים (מתוך כל היער) שאם *מראש* אני אכרות אותם (כלומר אמחק אותם מהגרף) אז בסופו של דבר אני אצליח להציל כמה שיותר עצים
(אפשר להניח שאני חשוף מראש לאלגוריתם שלו ויכול לדעת מהי קבוצת הקודקודים שהוא בחר בעבור הגרף המלא וכמה עצים +/- הוא שרף,אבל אז אני בוחר 100 קודקודים, מסיר אותם מהגרף ומריץ את האלגוריתם שלו שוב פעם לבחירת 50 קודקודי התחלה - והניסיון מראה שעצם זה שאני בוחר להסיר את 50 הקודקודים שהוא בחר בנקודת הפתיחה (+עוד 50 קודקודים לבחירתי) לאו דווקא מעיד על כך שמספר העצים השרופים בסופו של דבר אכן פחת, ואם פחת - אז בצורה משמעותית...)
ואחרי הרבה מאוד ניסיונות וקצת ייאוש, שאלת מליון הדולר - האם יש כיווןן/דרך מתוחכמת כלשהיא (שאינה תלויה, כמה שאפשר, באלגוריתם ספציפי של מישהו ספציפי, או בקבוצת קודקודים התחלתית ידועה כלשהיא) "לשבור" את הגרף הזה כך שאצליח להציל כמה שיותר עצים?
כי, בכנות, אמנם בחירת 50 קודקודים מביאה לתוצאות מרשימות מבחינת מספר השרופים, אבל אני לא ממש בטוח שבחירת 100 עצים מתוך משהו כמו 50,000 זה באמת משהו שיכול ליצור משמעות כלשהיא ברשת כ"כ גדולה....
אשמח לחוות דעת
תודה!
הי, בוקר טוב.
אנסה את מזלי, אולי למישהו יהיה רעיון טוב.
בבעיה נתון לי גרף עם הרבה קודקודים (כמה עשרות אלפים...) המייצג יער (כמו זה שבו כיפה אדומה הלכה לסבתא שלה, לא יער של BFS ..) כאשר כל קודקוד מייצג עץ, וכל קשת מייצגת קשר בין 2 עצים (אולי היו יחד בגן, אנא עארף..
לכל קשת יש ערך מספרי המייצג את חוזק הקשר בין 2 העצים, ולכל עץ יש ערך מספרי המייצג את מידת חסינותו לדליקות. אם עץ דולק באיטרציה i, אז הסיכוי שלו להדליק שכן שלו באיטרציה i+1 הוא (חוזק הקשר) בחזקת (מידת חסינות), ולאחר איטרציה זו נניח שהעץ כבר לא דולק ונשאר שרוף..
העניין הוא כזה - ישנו אדם שבוחר 50 עצים שאותם הוא רוצה להצית, כך שהוא חושב שאותם עצים יצליחו בתורם (תוך פרק זמן כלשהוא, נניח 5 דקות) להצית כמה שיותר עצים אחרים (כלומר שיהיו כמה שיותר עצים שרופים לאחר 5 דקות).
בפועל הנתונים מראים כי תוצאות הבחירה שלו מצליחות לשרוף אחוזים יפים, משהו בסביבות 60%.
המטרה היא למצוא קבוצה של 100 קודקודים (מתוך כל היער) שאם *מראש* אני אכרות אותם (כלומר אמחק אותם מהגרף) אז בסופו של דבר אני אצליח להציל כמה שיותר עצים
(אפשר להניח שאני חשוף מראש לאלגוריתם שלו ויכול לדעת מהי קבוצת הקודקודים שהוא בחר בעבור הגרף המלא וכמה עצים +/- הוא שרף,אבל אז אני בוחר 100 קודקודים, מסיר אותם מהגרף ומריץ את האלגוריתם שלו שוב פעם לבחירת 50 קודקודי התחלה - והניסיון מראה שעצם זה שאני בוחר להסיר את 50 הקודקודים שהוא בחר בנקודת הפתיחה (+עוד 50 קודקודים לבחירתי) לאו דווקא מעיד על כך שמספר העצים השרופים בסופו של דבר אכן פחת, ואם פחת - אז בצורה משמעותית...)
ואחרי הרבה מאוד ניסיונות וקצת ייאוש, שאלת מליון הדולר - האם יש כיווןן/דרך מתוחכמת כלשהיא (שאינה תלויה, כמה שאפשר, באלגוריתם ספציפי של מישהו ספציפי, או בקבוצת קודקודים התחלתית ידועה כלשהיא) "לשבור" את הגרף הזה כך שאצליח להציל כמה שיותר עצים?
כי, בכנות, אמנם בחירת 50 קודקודים מביאה לתוצאות מרשימות מבחינת מספר השרופים, אבל אני לא ממש בטוח שבחירת 100 עצים מתוך משהו כמו 50,000 זה באמת משהו שיכול ליצור משמעות כלשהיא ברשת כ"כ גדולה....
אשמח לחוות דעת
תודה!
