מבוא לאלגוריתמים חמדניים עם Java

1. הקדמה

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

2. בעיה חמדנית

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

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

בהקשר זה, בהתחשב בבעיה מתחלקת, אסטרטגיה שבכל שלב בתהליך לוקחת את הבחירה האופטימלית המקומית או "בחירה חמדנית" נקראת אלגוריתם חמדני.

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

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

2.1. תַרחִישׁ

במדריך קצר זה, אנו נטמיע אסטרטגיה חמדנית לחילוץ נתונים מרשת חברתית באמצעות ה- API שלה.

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

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

2.2. קלאסי לעומת חמדן

אנו לוקחים בחשבון את המצב הבא: לחשבון שלנו יש ארבעה עוקבים, שלכל אחד מהם, כפי שמתואר בתמונה למטה, בהתאמה 2, 2, 1 ו -3 עוקבים, וכן הלאה:

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

באופן זה, אנו מגדירים נתיב העשוי ממשתמשים, המוביל אותנו לבסיס העוקבים הגדול ביותר מחשבוננו. אם נוכל לפנות אליהם תוכן כלשהו, ​​הם בוודאי יגיעו לדף שלנו.

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

באופן מפתיע, בסך הכל נבצע 25 שאילתות:

כאן מתעוררת בעיה: לדוגמה, ה- API של Twitter מגביל סוג זה של שאילתות ל 15 כל 15 דקות. אם ננסה לבצע יותר שיחות מהמותר, נקבל "מגבלת התעריף חרגה מקוד - 88“, או“הוחזר ב- API v1.1 כאשר לא ניתן להגיש בקשה מכיוון שמגבלת השיעור של היישום מוצתה עבור המשאב". איך נוכל להתגבר על גבול כזה?

ובכן, התשובה ממש לפנינו: אלגוריתם חמדני. אם נשתמש בגישה זו, בכל שלב, נוכל להניח שהמשתמש עם הכי הרבה עוקבים הוא היחיד שיש לקחת בחשבון: בסופו של דבר, אנו זקוקים לארבע שאילתות בלבד. די שיפור!

התוצאה של שתי הגישות הללו תהיה שונה. במקרה הראשון, אנו מקבלים 16, הפיתרון האופטימלי, בעוד שבאחרון המספר המרבי של העוקבים הנגישים הוא 12 בלבד.

האם ההבדל הזה יהיה כה יקר? נחליט בהמשך.

3. יישום

כדי ליישם את ההיגיון שלעיל, אנו מאתחלים תוכנית Java קטנה, בה נחקה את ה- API של Twitter. נשתמש גם בספריית לומבוק.

עכשיו, בואו נגדיר את המרכיב שלנו מחבר חברתי בו נבצע את ההיגיון שלנו. שים לב שאנחנו הולכים להעלות מונה כדי לדמות מגבלות שיחות, אבל נוריד אותו לארבע:

מחלקה ציבורית SocialConnector {בוליאני פרטי isCounterEnabled = נכון; מונה אינטימי פרטי = 4; משתמשים @ Getter @ רשימת משתמשים; SocialConnector ציבורי () {משתמשים = ArrayList חדש (); } switchCounter בוליאני ציבורי () {this.isCounterEnabled =! this.isCounterEnabled; החזר את this.isCounterEnabled; }} 

לאחר מכן אנו מוסיפים שיטה לאחזור רשימת העוקבים של חשבון ספציפי:

רשימת ציבורים getFollowers (חשבון מחרוזת) {if (counter <0) {throw new IllegalStateException ("הגבלת מגבלת ה- API"); } אחר {if (this.isCounterEnabled) {counter--; } עבור (משתמש משתמש: משתמש) {אם (user.getUsername (). שווה (חשבון)) {return user.getFollowers (); }}} להחזיר ArrayList חדש (); } 

כדי לתמוך בתהליך שלנו, אנו זקוקים לכמה שיעורים כדי לדגמן את ישות המשתמש שלנו:

מעמד ציבורי חברתי {@ Getter פרטי מחרוזת שם משתמש; חסידי רשימת @Getter פרטית; @Override בוליאני ציבורי שווה (Object obj) {return ((SocialUser) obj) .getUsername (). שווה (שם משתמש); } משתמש ציבורי חברתי (שם משתמש מחרוזת) {this.username = שם משתמש; this.followers = ArrayList חדש (); } ציבורי חברתי ציבורי (שם משתמש מחרוזת, רשימת עוקבים) {this.username = שם משתמש; this.followers = חסידים; } בטל ציבורי addFollowers (רשימת העוקבים) {this.followers.addAll (עוקבים); }}

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

לבסוף הגיע הזמן ליישם את האסטרטגיה החמדנית שלנו, אז בואו נוסיף רכיב חדש - אלגוריתם חמדן - בו נבצע את הרקורסיה:

מעמד ציבורי GreedyAlgorithm {int currentLevel = 0; int final final maxLevel = 3; SocialConnector sc; חמדנות אלגוריתם ציבורית (SocialConnector sc) {this.sc = sc; }}

ואז עלינו להכניס שיטה findMostFollowersPath בו נמצא את המשתמש עם מרבית העוקבים, נספור אותם ונמשיך לשלב הבא:

ציבורי ארוך findMostFollowersPath (חשבון מחרוזת) {long max = 0; SocialUser toFollow = null; רשימת העוקבים = sc.getFollowers (חשבון); עבור (SocialUser el: followers) {long followersCount = el.getFollowersCount (); אם (followersCount> max) {toFollow = el; max = followersCount; }} אם (currentLevel <maxLevel - 1) {currentLevel ++; max + = findMostFollowersPath (toFollow.getUsername ()); } להחזיר מקסימום; }

זכור: כאן אנו מבצעים בחירה חמדנית. ככזה, בכל פעם שאנחנו קוראים לשיטה זו, אנו בוחרים אלמנט אחד ויחיד מהרשימה והמשיכו הלאה: לעולם לא נחזור להחלטות שלנו!

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

חלל ציבורי greedyAlgorithmTest () {GreedyAlgorithm ga = New GreedyAlgorithm (prepareNetwork ()); assertEquals (ga.findMostFollowersPath ("שורש"), 5); }

3.2. אלגוריתם שאינו חמדן

בואו ניצור שיטה לא חמדנית, רק כדי לבדוק בעיניים מה קורה. אז עלינו להתחיל בבניית א אלגוריתם NonGreedy מעמד:

מחלקה ציבורית NonGreedyAlgorithm {int currentLevel = 0; int final final maxLevel = 3; SocialConnector tc; ציבורי NonGreedyAlgorithm (SocialConnector tc, int רמת) {this.tc = tc; this.currentLevel = רמה; }}

בואו ניצור שיטה מקבילה לאחזור עוקבים:

ציבורי ארוך findMostFollowersPath (חשבון מחרוזת) {רשימה עוקבים = tc.getFollowers (חשבון); סך הכל = הנוכחי רמת> 0? followers.size (): 0; אם (currentLevel  0; i--) {if (count [i-1]> max) {max = count [i-1]; }} להחזיר סך הכל + מקסימום; } סך ההחזר; }

מכיוון שהשיעור שלנו מוכן, אנו יכולים להכין כמה בדיקות יחידה: אחת לאימות מגבלת השיחות חורגת ואחת נוספת לבדוק את הערך שהוחזר באסטרטגיה שאינה חמדנית:

חלל ציבורי nongreedyAlgorithmTest () {NonGreedyAlgorithm nga = new NonGreedyAlgorithm (prepareNetwork (), 0); Assertions.assertThrows (IllegalStateException.class, () -> {nga.findMostFollowersPath ("root");}); } חלל ציבורי nongreedyAlgorithmUnboundedTest () {SocialConnector sc = prepareNetwork (); sc.switchCounter (); NonGreedyAlgorithm nga = חדש NonGreedyAlgorithm (sc, 0); assertEquals (nga.findMostFollowersPath ("שורש"), 6); }

4. תוצאות

הגיע הזמן לסקור את העבודה שלנו!

ראשית, ניסינו את האסטרטגיה החמדנית שלנו ובדקנו את יעילותה. ואז אימתנו את המצב בחיפוש ממצה, עם ובלי מגבלת ה- API.

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

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

5. מסקנה

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

התגברות על מגבלות ואופטימיזציה של שיחות API זה די נושא, אך כפי שדנו, אסטרטגיות חמדניות יעילות. בחירה בגישה מסוג זה חוסכת לנו הרבה כאב, ומחזירה תוצאות יקרות בתמורה.

זכור שלא כל סיטואציה מתאימה: עלינו להעריך את נסיבותינו בכל פעם.

כמו תמיד, קוד הדוגמה ממדריך זה זמין ב- GitHub.


$config[zx-auto] not found$config[zx-overlay] not found