נושא: פתרון בעזרת BFS

נשלח בתאריך: 31 March 2006 בשעה 01:53 | IP רשוּם

שלום,

יש מספר וריאציות של תרגיל שפותרים בעזרת טריקים שקשורים ל-BFS, למשל 2 בעיות

שנתקלתי בהן לאחרונה:

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

2) שאלה דומה היא למצוא אלגוריתם כל שבמסלול לא יהיו 2 קשתות מאותו הצבע, או למשל שבמסלול יהיו בדיוק 2 קשתות ירוקות וכו'...

כיצד מתמודדים עם בעיות מהסוג הזה, אשמח לעזרתכם,

בתודה,

יניב