|
|
עמוד:250
נשרטט על השטח סריג בין N * N משבצות . כל משבצת בסריג תהיה קדקוד בגרף . בגרף תהיה קשת בין משבצת אחת לאחרת רק אם הישר העובר מאחת לשנייה אינו נתקל במכשול . כתבו תכנית למציאת המסלול הקצר ביותר ( שעוקף מכשולים ) בין נקודת המקור לנקודת היעד . הריצו את התכנית מספר פעמים והכניסו בה נתונים של שטחים בגדלים שונים ופיזור וצפיפות מכשולים משתנה ואקראית . עבור כל ריצה התכנית תדפיס את י השטח , מיקום המכשולים , המקור והיעד וכן את אורך המסלול הקצר שנמצא . ליודעי גרפיקה ממוחשבת , רצוי גם ללוות את הפתרון בתיאור גרפי של הבעיה ושל הפתרון . שאלה 5 . 22 נתון הגרף G = ( V , E ) עם פונקציית המשקל . W : £ - >/? + נתונות שתי קבוצות זרות של הצמתים S ו-י 7 כךש ^ פ < 1 '' , 7 םז , . TnS = < fr ?) עליכם לפתח שיטה , הדומה לאלגוריתם דיקסטרה למציאת המסלול הקצר ביותר המחבר קדקוד כלשהו S-J לקדקוד כלשהו ב-ד כלומר , יש למצוא את המסלול הקצר ביותר מבין כל המסלולים המתחילים S-1 ומסתיימים ב-י . 7 5 . 5 סריקת גרף לרוחב ( BFS ) פעולה חשובה ושכיחה בגרף היא סריקה של קדקודיו . בעת הסריקה , נעבור על-פני הגרף כך שנבקר בכל קדקוד פעם אחת בלבד ונבצע בו עיבוד כלשהו . קיימות שתי שיטות סריקה שונות הנבדלות זו מזו בסדר שבו מתבצעת הסריקה . השיטות n סריקה לרוחב BFS ) ( Breadth-First Search - וסריקה לעומק . ( Depth-First Search - DFS ) בסעיף הזה נכיר את השיטה הראשונה - סריקה לרוחב , ובסעיף הבא את השיטה השנייה - סריקה לעומק . ( בהמשך נראה כיצד הן קשורות לבעיית המסלול הקצר ביותר ( . להלן תיאור שיטת הסריקה לרוחב : ( BFS )
|
|