אלגוריתם חמדן GREEDY
- פותח הנושא yair24
- פורסם בתאריך
תשובה ( אלגוריתם בתקשורת )
חמדן היא אחת השיטות למצוא את הדרך הכי קצרה ממחשב אחד למחשב אחר ברשת מחשבים. תאר לעצמך מצב שבו יש רשת בא כמה מחשבים מחוברים אחד לשנית מחוברים ישירות ומחוברים דרך מחשבים אחרים. בשיטת חמדן אנו יכולים למצוא (למרות שהיא לא השיטה הכי טובה, אתה מבין אם למדת את האלגוריתם של דייקסטרה) את הדרך הכי קצרה ממחשב אחד לאחר. באלגוריתם זה על הקו המחבר כל שני מחשבים מסומן המשקל של המעבר ביניהם (משקל לוגי כמובן). האלגוריתם אומר כך: 1.סמן את נקודת המוצא. 2.אם אחד מן השכנים הוא היעד סיים. 3.אחרת עבור לשכן שהמשקל המחבר אותך אליו הוא הקטן ביותר 4.חזור ל-2
חמדן היא אחת השיטות למצוא את הדרך הכי קצרה ממחשב אחד למחשב אחר ברשת מחשבים. תאר לעצמך מצב שבו יש רשת בא כמה מחשבים מחוברים אחד לשנית מחוברים ישירות ומחוברים דרך מחשבים אחרים. בשיטת חמדן אנו יכולים למצוא (למרות שהיא לא השיטה הכי טובה, אתה מבין אם למדת את האלגוריתם של דייקסטרה) את הדרך הכי קצרה ממחשב אחד לאחר. באלגוריתם זה על הקו המחבר כל שני מחשבים מסומן המשקל של המעבר ביניהם (משקל לוגי כמובן). האלגוריתם אומר כך: 1.סמן את נקודת המוצא. 2.אם אחד מן השכנים הוא היעד סיים. 3.אחרת עבור לשכן שהמשקל המחבר אותך אליו הוא הקטן ביותר 4.חזור ל-2
שים לב... נתונים n קטעים על הישר
נתונים n קטעים פתוחים על הישר , יש למצוא קבוצה בגודל מקסימלי של קטעים זרים מתוך n הקטעים הנתונים. (הבעיה אנלוגית לשיבוץ קורסים במערכת שעות שבועית כאשר רוצים לשבץ מספר מקסימלי של קורסים בלי התיחסות לאורכי השיעורים של כל קורס , לדוגמא....) אם אתה שולט באלגוריתמים חמדניים אז זהו הפתרון..
נתונים n קטעים פתוחים על הישר , יש למצוא קבוצה בגודל מקסימלי של קטעים זרים מתוך n הקטעים הנתונים. (הבעיה אנלוגית לשיבוץ קורסים במערכת שעות שבועית כאשר רוצים לשבץ מספר מקסימלי של קורסים בלי התיחסות לאורכי השיעורים של כל קורס , לדוגמא....) אם אתה שולט באלגוריתמים חמדניים אז זהו הפתרון..
כמה הבהרות
אלגוריתם חמדן: אלגוריתם שבכל צעד בוחר באופציה הכי טובה מיידית, בלי להתחשב בכך שאולי זה לא נותן את התוצאה הטובה ביותר בסה"כ הכללי. לגבי גרפים - יקירי, כל דבר בעולם אפשר לייצג בעזרת גרף. כמו שאמרת על קוד הופמן - זה בעצם עץ, אבל כל דבר בעולם אפשר לייצג על ידי עץ. בתיאוריה של מדעי המחשב משתמשים בעצים כקלט שמייצג הכל - מספרים, תווים וכו´. ולגבי אלגוריתם מסוים, אתה יכול לראות בכל זאת ב - CLR את הדוגמה של האלגוריתם לתזמון (עמוד 350). זה לא משתמש בגרפים אלא בסטים.
אלגוריתם חמדן: אלגוריתם שבכל צעד בוחר באופציה הכי טובה מיידית, בלי להתחשב בכך שאולי זה לא נותן את התוצאה הטובה ביותר בסה"כ הכללי. לגבי גרפים - יקירי, כל דבר בעולם אפשר לייצג בעזרת גרף. כמו שאמרת על קוד הופמן - זה בעצם עץ, אבל כל דבר בעולם אפשר לייצג על ידי עץ. בתיאוריה של מדעי המחשב משתמשים בעצים כקלט שמייצג הכל - מספרים, תווים וכו´. ולגבי אלגוריתם מסוים, אתה יכול לראות בכל זאת ב - CLR את הדוגמה של האלגוריתם לתזמון (עמוד 350). זה לא משתמש בגרפים אלא בסטים.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.