IOPanel

חזור   IOPanel > דבר חופשי > תוכנה ומערכות הפעלה > תיכנות
עמוד ראשי הירשם חיפוש הודעות מהיום סמן פורומים כנקראו

תיכנות פורום בנושאי תיכנות , פיתוח אתרים , שפות תיכנות , אפליקציות סלולר וטאבלטים.

תוכנה ומערכות הפעלה : תיכנות

מישהו מבין באלגוריתם ford fulkerson

יש לי שאלה בנושא אלגוריתמי זרימה עם אלגוריתם ford fulkerson החומר הזה גם ככה לא הכי מובן אבל אין לי ...
תגובה
 
קישור חוזר הגדרות אשכול אפשרויות הצגת נושא
ישן 21-06-12, 0:27   #1 (קישור ישיר)
IO Gadgets
 
סמל האישי של iakovl
 
תאריך הצטרפות: Jan 2007
הודעות: 13,202
ברירת מחדל מישהו מבין באלגוריתם ford fulkerson

יש לי שאלה בנושא אלגוריתמי זרימה עם אלגוריתם ford fulkerson
החומר הזה גם ככה לא הכי מובן אבל אין לי שמץ איך לענות
ציטוט:
נתונה רשת זרימה
הראו ששיטת Ford-Fulkerson פועלת מספר סופי של איטרציות במקרה של ערכי הקיבול הקשתות בגרף הינם מספרים שלימים.
__________________
Device: Gnote ROM: CM9 #7 Kernel: stock Modem:LB2
Main: E8400, Asus P5Q pro, 2*2gb G.skill PI DDR900, Perc 5/i HD103UJx4 RAID5 , wd3200aaks, HD4850, P180, VX450W, audigy 2 zs platinium pro, HD595, DELL 2709W
ביקורות: 7ZIP , Thermalright HR-5 , Arctic-Cooling Accelero S1 Rev.2 , Scythe Kaze Master 5.25, Cruzer Titanium ,Seagate FreeAgent USB 2.0 500gb, WD My Book Home Edition 500gb otterbox impact, Scythe Kamazo 2 eSata, iTwin
iakovl לא מחובר   הגב עם ציטוט
ישן 21-06-12, 14:46   #2 (קישור ישיר)
IO Member
 
סמל האישי של bamba12
 
תאריך הצטרפות: Apr 2007
הודעות: 893
ברירת מחדל

אני לא מבין גדול בנושא, אבל אני אנסה לעזור.

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

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

הוכחה:
נניח בשלילה שמספר האיטרציות הוא אינסופי.
בכל שלב אנו מוספים זרימה ששווה למינימום הקיבול הנותר במסלול, מכיוון שהקיבולים שלמים אנו מוסיפים כל פעם זרימה שלמה, ולכן היא בהכרח גדולה שווה ל-1.
הזרימה שהוספנו למערכת עד שלב N תהיה סכום מ-i=1 עד N של f_i, כאשר f_i היא הזרימה שהוספנו בשלב i.
כמו שאמרנו למעלה f_i גדול או שווה ל-1, ולכן הזרימה שהוספנו למערכת עד שלב N גדולה מסכום מ-1 עד N של -1- כלומר גדולה מ-N.
הנחנו בשלילה שמספר האיטרציות הוא אינוספי, ולכן N יכול להגיע לאינסוף, כלומר הזרימה האפשרית במערכת תהיה אינסופית- הגענו לסתירה.

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


הגדרות אשכול
אפשרויות הצגת נושא

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

vB code הינו פועל
סמיילים הינו פועל
קוד [IMG] הינו פועל
קוד HTML הינו כבוי
Trackbacksהינו פועל
Pingbacks הינו פועל
Refbacks הינו פועל

נושאים דומים
אשכול מפרסם האשכול פורום תגובות הודעה אחרונה
מישהו מבין באימייל ?? thekimg95 תמיכה טכנית 2 06-06-09 4:24
מישהו מבין פה באמצעים להשתקה? oR. דיבורים על הא ודא 9 06-05-09 16:43
מישהו מבין בכלבים? Shay דיבורים על הא ודא 10 23-03-09 22:27
מישהו מבין בחלומות ? rouvio דיבורים על הא ודא 27 28-07-08 10:41
מישהו מבין במדפסות? AgentSmith מדפסות, מקלדות, עכברים, ידיות משחק, הגאים 3 25-05-08 18:43


כל הזמנים הם GMT +3. השעה כרגע היא 16:18.





מופעל על ידי: vBulletin
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO
IOPanel.net © כל הזכויות שמורות