רוטר - בעיה אלגוריתמית שנתקעתי איתה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"בעיה אלגוריתמית שנתקעתי איתה"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #7133	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 7133

liranr

דרג אמינות חבר זה

14:50 10.10.03

בעיה אלגוריתמית שנתקעתי איתה

יכול להיות שזה טריויאלי ואז אני אצא טיפש, אבל שיהיה:
נניח שבמדינה מסויימת יש מטבעות רק בערכים (a(1),a(2),a(3)...a(N.
(כאשר a(1)=1 כדי להבטיח שנוכל ליצור את כל הערכים השלמים).
יהי M המחיר של מוצר מסויים במדינה.
אני רוצה פונקציה שתקבל את M ואת המערך a ותחזיר את המספר המינימלי
של מטבעות שצריך כדי לשלם על המוצר.
מצאתי פיתרון רקורסיבי שעובד, אבל למספרים קטנים מאוד (לפי ניתוח זריז
הוא עובד ב (O(N^M - ממש לא ריאלי)
למישהו יש פיתרון טוב יותר? (ניקח גם פיתרון היוריסטי בתנאי שהוא מדוייק,
כי אני צריך את התשובה ממש, לא קירוב עם טעות של 5% או משהו כזה)

המספרים שאני עובד איתם לא מאוד גדולים (בואו נגביל לM<500 לצורך
העניין), אם זה משנה למשהו

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
אני חושד שמדובר בבעיית ריצוף, NP קשה.	dryice	10.10.03 17:27	1
אז ככה	liranr	10.10.03 18:00	2
כמה כיוונים.	dryice	10.10.03 21:29	3
במחשבה שניה, אולי אפשר לעשות מזה	dryice	10.10.03 21:33	4
אני כמעט משוכנע שזה פתיר פולינומית.	dryice	10.10.03 22:06	5
ואני מכיר את זה אפילו פחות ממך	liranr	10.10.03 22:17	6
אני בעצמי נתקלתי בזה ממש לאחרונה	dryice	11.10.03 00:53	7
שוב אני מודה לבושתי	liranr	11.10.03 20:41	8
פותרים את זה עם לאגראנג'יאן	dryice	11.10.03 22:00	9
תודה בכל מקרה	liranr	11.10.03 22:30	10

dryice

דרג אמינות חבר זה

17:27 10.10.03

1. אני חושד שמדובר בבעיית ריצוף, NP קשה.
בתגובה להודעה מספר 0

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

דרג אמינות חבר זה

18:00 10.10.03

2. אז ככה
בתגובה להודעה מספר 1

ערכתי לאחרונה בתאריך 10.10.03 בשעה 18:02 בברכה, liranr

כמו שאמרתי, אני לא עובד עם מספרים גדולים במיוחד.
רשמתי בהודעה M<500, אבל שאני חושב על זה אני יכול לרדת יותר - בוא
נגיד גבולות של M=100 ו- N=5 יהיו בערך ריאלים. יש לך איזהשהו מימוש יעיל
בשבילי?

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

דרג אמינות חבר זה

21:29 10.10.03

3. כמה כיוונים.
בתגובה להודעה מספר 2

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

דרג אמינות חבר זה

21:33 10.10.03

4. במחשבה שניה, אולי אפשר לעשות מזה
בתגובה להודעה מספר 0

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

דרג אמינות חבר זה

22:06 10.10.03

5. אני כמעט משוכנע שזה פתיר פולינומית.
בתגובה להודעה מספר 4

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

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

דרג אמינות חבר זה

22:17 10.10.03

6. ואני מכיר את זה אפילו פחות ממך
בתגובה להודעה מספר 5

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

תודה רבה בכל מקרה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

דרג אמינות חבר זה

00:53 11.10.03

7. אני בעצמי נתקלתי בזה ממש לאחרונה
בתגובה להודעה מספר 6

בבעיה אחרת ותפסתי מישהוא בטכניון שעשה אלגוריתמים 2 שהסביר
לי בזמנו כמה דברים.
בכל מקרה אפשר לנסות להסתכל על הבעיה גם כבעיה של תכנות
בשלמים. במקרה הכללי תכנות בשלמים הוא קשה, במקרה שלנו
אני חושב שלא.
אם יהיו לנו משתנים X מ1 עד N שיצינו כמה מטבעות מכל סוג
אנו בוחרים. אז אנו צריכים למזער את הסכום של X,
תחת האילוצים הלינארים: <X,A> שווה לM
וX(i)>=0 לכל i.
במקרה השלם זה קשה, אבל אם אני מרשה לX לקבל גם ערכים לא שלמים
אז זה סתם בעיה אלגברית(אם הרבה משתנים),
אני חושד שבמקרה שלנו הפתרון של המקרה הממשי הוא בעצמו שלם.
(אם אני טועה והוא לא שלם, אפשר לעגל ולקבל קירוב טוב)

DRYICE

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

דרג אמינות חבר זה

20:41 11.10.03

8. שוב אני מודה לבושתי
בתגובה להודעה מספר 7

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

נ.ב: אני מניח ש-<X,A> זה המכפלה הסקלרית של הוקטורים, נכון?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

dryice

דרג אמינות חבר זה

22:00 11.10.03

9. פותרים את זה עם לאגראנג'יאן
בתגובה להודעה מספר 8

ערכתי לאחרונה בתאריך 11.10.03 בשעה 22:04 בברכה, dryice

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

liranr

דרג אמינות חבר זה

22:30 11.10.03

10. תודה בכל מקרה
בתגובה להודעה מספר 9

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד