אלגוריתם חמדן GREEDY

yair24

New member
אלגוריתם חמדן GREEDY

שלום, אני מריך לעשות הרצאה קצרה על משהו שעובד עם אלגוריתם חמדן כלשהו אבל אבל שלא קשור לתורת הגרפים. מישהו מכיר איזשהו יישום של אלגוריתמים חמדניים שלא קשורים לגרפים? יאיר
 

TheEladm

New member
תשובה ( אלגוריתם בתקשורת )

חמדן היא אחת השיטות למצוא את הדרך הכי קצרה ממחשב אחד למחשב אחר ברשת מחשבים. תאר לעצמך מצב שבו יש רשת בא כמה מחשבים מחוברים אחד לשנית מחוברים ישירות ומחוברים דרך מחשבים אחרים. בשיטת חמדן אנו יכולים למצוא (למרות שהיא לא השיטה הכי טובה, אתה מבין אם למדת את האלגוריתם של דייקסטרה) את הדרך הכי קצרה ממחשב אחד לאחר. באלגוריתם זה על הקו המחבר כל שני מחשבים מסומן המשקל של המעבר ביניהם (משקל לוגי כמובן). האלגוריתם אומר כך: 1.סמן את נקודת המוצא. 2.אם אחד מן השכנים הוא היעד סיים. 3.אחרת עבור לשכן שהמשקל המחבר אותך אליו הוא הקטן ביותר 4.חזור ל-2
 

linuxius

New member
אני עניתי לך התשובה

אם זה לא ברור אני יכול לעזור עוד
 

yair24

New member
תודה אבל...

רשת מחשבים היא בעצם גרף... ואני צריך אלגוריתם חמדן שלא קשור לגרפים בשום צורה יאיר
 

ke

New member
תסתכל ב CLR

אפשר להסתכל בספר של מבוא לאלגוריתמים של Cormen,Leisurson and Rivest, בחלק א. דוגמא אפשרית זה קוד הפמן.
 

yair24

New member
תודה אבל קוד הופמן הוא גרף גם כן.

אני צריך משהו שלא קשור לגרפים... למשל מישהו אצלנו עשה הרצאה על אלגוריתם חמדן כלשהו שדוחס תמונת וידאו. יאיר
 

yairamir

New member
שים לב... נתונים n קטעים על הישר

נתונים n קטעים פתוחים על הישר , יש למצוא קבוצה בגודל מקסימלי של קטעים זרים מתוך n הקטעים הנתונים. (הבעיה אנלוגית לשיבוץ קורסים במערכת שעות שבועית כאשר רוצים לשבץ מספר מקסימלי של קורסים בלי התיחסות לאורכי השיעורים של כל קורס , לדוגמא....) אם אתה שולט באלגוריתמים חמדניים אז זהו הפתרון..
 

אלדד26

New member
כמה הבהרות

אלגוריתם חמדן: אלגוריתם שבכל צעד בוחר באופציה הכי טובה מיידית, בלי להתחשב בכך שאולי זה לא נותן את התוצאה הטובה ביותר בסה"כ הכללי. לגבי גרפים - יקירי, כל דבר בעולם אפשר לייצג בעזרת גרף. כמו שאמרת על קוד הופמן - זה בעצם עץ, אבל כל דבר בעולם אפשר לייצג על ידי עץ. בתיאוריה של מדעי המחשב משתמשים בעצים כקלט שמייצג הכל - מספרים, תווים וכו´. ולגבי אלגוריתם מסוים, אתה יכול לראות בכל זאת ב - CLR את הדוגמה של האלגוריתם לתזמון (עמוד 350). זה לא משתמש בגרפים אלא בסטים.
 

yair24

New member
הספר הזה...

זה הספר שהסטודנטים מכנים אותו הספר של קורמן? (ספר גדול כזה עם שני חלקים)? יאיר
 

אלדד26

New member
כן,

למרות שאני לא מכיר שני חלקים
 
למעלה