השיטה החמדנית היא אחת מהאסטרטגיות כמו Divide and conquer המשמשות לפתרון הבעיות. שיטה זו משמשת לפתרון בעיות אופטימיזציה. בעיית אופטימיזציה היא בעיה הדורשת מקסימום או מינימום תוצאות. בואו נבין דרך כמה מונחים.
שיטת Greedy היא הגישה הפשוטה והישרה ביותר. זה לא אלגוריתם, אבל זו טכניקה. תפקידה העיקרי של גישה זו הוא שההחלטה מתקבלת על בסיס המידע הקיים כיום. לא משנה מה המידע הנוכחי קיים, ההחלטה מתקבלת מבלי לדאוג להשפעה של ההחלטה הנוכחית בעתיד.
c# datetime
טכניקה זו משמשת בעצם כדי לקבוע את הפתרון האפשרי שעשוי להיות אופטימלי או לא. הפתרון האפשרי הוא תת-קבוצה שעונה על הקריטריונים הנתונים. הפתרון האופטימלי הוא הפתרון שהוא הפתרון הטוב והנוח ביותר בתת-הקבוצה. במקרה של ריאלי, אם יותר מפתרון אחד עומד בקריטריונים הנתונים אז פתרונות אלה ייחשבו כאפשריים, בעוד שהפתרון האופטימלי הוא הפתרון הטוב ביותר מבין כל הפתרונות.
מאפייני שיטת Greedy
להלן המאפיינים של שיטה חמדנית:
- כדי לבנות את הפתרון בצורה אופטימלית, אלגוריתם זה יוצר שני סטים שבהם סט אחד מכיל את כל הפריטים שנבחרו, וקבוצה אחרת מכילה את הפריטים שנדחו.
- אלגוריתם חמדן עושה בחירות מקומיות טובות בתקווה שהפתרון יהיה בר-ביצוע או אופטימלי.
מרכיבי האלגוריתם החמדני
הרכיבים שניתן להשתמש בהם באלגוריתם החמדני הם:
java המרת מחרוזת למספר שלם
יישומים של אלגוריתם חמדן
- הוא משמש למציאת הנתיב הקצר ביותר.
- הוא משמש כדי למצוא את העץ המשתרע המינימלי באמצעות האלגוריתם של הפרים או האלגוריתם של Kruskal.
- הוא משמש ברצף עבודה עם מועד אחרון.
- אלגוריתם זה משמש גם לפתרון בעיית התרמיל השברירי.
קוד פסאודו של אלגוריתם חמדן
Algorithm Greedy (a, n) { Solution : = 0; for i = 0 to n do { x: = select(a); if feasible(solution, x) { Solution: = union(solution , x) } return solution; } } האמור לעיל הוא האלגוריתם החמדן. בתחילה, הפתרון מוקצה עם ערך אפס. אנו מעבירים את המערך ומספר האלמנטים באלגוריתם החמדני. בתוך לולאת for, אנו בוחרים את האלמנט אחד אחד ובודקים אם הפתרון אפשרי או לא. אם הפתרון אפשרי, אז אנחנו מבצעים את האיחוד.
בואו נבין דרך דוגמה.
נניח שיש בעיה 'P'. אני רוצה לנסוע מ-A ל-B המוצג להלן:
P : A → B
הבעיה היא שאנחנו צריכים לעבור את המסע הזה מ-A ל-B. יש פתרונות שונים לעבור מ-A ל-B. אנחנו יכולים לעבור מ-A ל-B על ידי הליכה, מכונית, אופניים, רכבת, מטוס וכו' יש מגבלה במסע שעלינו לנסוע את המסע הזה תוך 12 שעות. אם אני נוסע ברכבת או במטוס בלבד, אוכל לעבור את המרחק הזה תוך 12 שעות. ישנם פתרונות רבים לבעיה זו אך ישנם רק שני פתרונות העונים על האילוץ.
אם נגיד שעלינו לכסות את המסע בעלות המינימלית. המשמעות היא שעלינו לעבור את המרחק הזה כמה שיותר מינימלי, ולכן בעיה זו ידועה כבעיית מזעור. עד עכשיו, יש לנו שני פתרונות אפשריים, כלומר, אחד ברכבת ועוד אחד באוויר. מכיוון שנסיעה ברכבת תוביל לעלות המינימלית אז זה פתרון אופטימלי. פתרון אופטימלי הוא גם הפתרון האפשרי, אך מתן התוצאה הטובה ביותר כך שהפתרון הוא הפתרון האופטימלי במינימום עלות. יהיה רק פתרון אופטימלי אחד.
הבעיה שדורשת תוצאה מינימלית או מקסימלית אז הבעיה הזו ידועה כבעיית אופטימיזציה. שיטה חמדנית היא אחת האסטרטגיות המשמשות לפתרון בעיות האופטימיזציה.
קרא מקובץ csv ב-java
חסרונות השימוש באלגוריתם Greedy
אלגוריתם חמדן מקבל החלטות על סמך המידע הזמין בכל שלב מבלי להתחשב בבעיה הרחבה יותר. אז אולי יש אפשרות שהפתרון החמדני לא נותן את הפתרון הטוב ביותר לכל בעיה.
הוא עוקב אחר הבחירה האופטימלית המקומית בכל שלב מתוך כוונה למצוא את האופטימום הגלובלי. בואו נבין דרך דוגמה.
שקול את הגרף המופיע להלן:
עלינו לנסוע מהמקור ליעד בעלות המינימלית. מכיוון שיש לנו שלושה פתרונות אפשריים עם נתיבי עלות כמו 10, 20 ו-5. 5 הוא מסלול העלות המינימלי ולכן הוא הפתרון האופטימלי. זהו האופטימום המקומי, ובדרך זו אנו מוצאים את האופטימום המקומי בכל שלב על מנת לחשב את הפתרון האופטימלי הגלובלי.
אורך מחרוזת java