בתשובה לרן, 21/01/08 16:28
 |
|
 |
||
|
||||
 |
אם אתה רוצה לדבר בחידות, בבקשה, אבל אין סיבה שמישהו יתייחס אלייך ברצינות. תספר מה הבעיה ומה הפתרון, וחסל. אגב, חשוב לזכור שהרדוקציה מ-SAT לבעיה שלך צריכה להיות ניתנת לחישוב בזמן פולינומי. רדוקציה לא פולינומית מ-SAT יש לכל דבר שבעולם (כמעט). |
 |
 |
 |
|
|
|
||
|
||||
|
אפשר דוגמא (לרדוקציה לא פולינומית מSAT או מבעיה NP-שלמה אחרת לבעיה פולינומית)? | |
|
|
|
|
|
||
|
||||
|
בטח. למשל, הבעיה של "האם x הוא 1?" כש-x הוא בתחום 0 או 1. הרדוקציה היא כזו: בהינתן פסוק בתחשיב הפסוקים, בדוק (בזמן אקספוננציאלי, בצורה הנאיבית) אם הוא ספיק. אם כן, העתק אותו ל-1. אם לא, העתק אותו ל-0. מה קיבלנו? שפסוק הוא ספיק אם ורק אם הוא מועתק ל-x שעליו האלגוריתם שפותר את הבעיה הפשוטה עונה "כן". |
|
|
|
|
|
|
||
|
||||
|
ועוד דבר, את החלק של רדוקציה מ SAT לבעית סידור ההזמנות לא הצלחתי להראות בכלל. כלומר אין לי שום אלגוריתם שהופך את SAT לבעית סידור ההזמנות. כך שבוודאי שהוא לא פולינומי. יש לכם משהו? |
|
|
|
|
|
|
||
|
||||
|
זו הפעם הראשונה שבה אני שומע אותך אומר משהו על "סידור הזמנות", אז עדיין לא ברור על מה אתה מדבר. בכל אופן, הצעד הראשון לפני שמתקלים את P=NP הוא לבדוק שניתן לבצע רדוקציה פולינומית מ-SAT (או בעיה NP-שלמה אחרת) אל הבעיה שיש לך ביד . אם אין לך משהו כזה, אין לך בעצם כלום (כלומר, יש לך בעיה שאתה יודע או לא יודע לפתור, אבל אין לה קשר ממשי לשאלת P=NP). |
|
|
|
|
|
|
||
|
||||
|
אני כתבתי תאור ארוך של בעיית סידור ההזמנות, חשבתי שתראה את התגובה ההיא לפני זאת ולכן כבר התיחסתי אליה כאל בעיה שאתה מכיר... תיכף אני אתאר אותה שוב. משום מה היא לא עלתה למערכת (תגיד, צריך ללחוץ על "אישור"? :-)) מלבד זאת, אני לא תוקף את P=NP אני רק רוצה לשייך את בעיית סידור ההזמנות למחלקה הנכונה. בשלב ראשון זה מה שאני לא יודע. אח"כ כבר יהיה יותר קל: אם היא שייכת ל P אזי נוכל להניח שהאלגורתם שמסדר הוא נכון תמיד. אם הבעיה שייכת ל NP אזי נצטרך לעבוד קצת יותר קשה ולהראות שיש לפחות קלט אחד שעבורו האלגוריתם רץ בזמן לא סביר. להלן (שוב) תיאור הבעיה: נתון צי רכבים N. לכל רכב בצי יש מספר תכונות המאפיינות אותו: מספר מקומות, סוג הילוכים, רשיון נדרש, צבע וכד'. נתונה רשימת הזמנות R. כל הזמנה מכילה: 1. מאיזו שעה ועד איזו שעה הרכב נדרש. 2. מאפיינים של הרכב הנדרש. הרשימה יכולה להיות ריקה, כלומר כל רכב מתאים. השאלה: האם קיים סידור ל R ב N? או בגרסה המלאה: מהו הסידור של R ב N? כל מי שהיה פעם חבר קיבוץ מכיר את הבעיה. יש לי גם תאור פורמלי יותר של הבעיה, יותר מאוחר אני אעלה אותו. |
|
|
|
|
|
|
||
|
||||
|
בלי לחשוב על הבעיה יותר מדי, היא נראית לי הרחבה של http://en.wikipedia.org/wiki/Knapsack_problem שהיא בעיה NP שלמה. | |
|
|
|
|
|
||
|
||||
|
במבט חטוף, אני לא מצליח להבין אם יש קשר בין שתי הבעיות. אולי, אם כל פריט הוא הזמנה: משקלו הוא השעות וערכו הוא התיקים אליהם הוא יכול להכנס?... לא נשמע טוב, צריך לבדוק. ודווקא הרחבה יכולה ליצור הקלה בתנאים ולהפוך את הבעיה לפשוטה יותר.... | |
|
|
|
|
|
||
|
||||
|
הנה תיאור של רדוקציה מבעיה דמוית-תרמיל לבעית סידור ההזמנות. הבעיה (דמוית התרמיל): נתונות n משקולות, במשקל כולל N, וצריך למצוא תת קבוצה שלהן כך שסכום המשקולות בתת הקבוצה הוא *בדיוק* K. בנוסף אני דורש ש- 2K>N. רדוקציה: בצי הרכבים יש שני רכבים, 1 ו- 2. אורך ה"יממה" הוא K שעות. כל משקולת הופכת להזמנה של רכב למספר שעות השווה לגודל המשקולת, כאשר ההזמנה היא לרכב 1 או לרכב 2. בנוסף, יש הזמנה של 2K-N שעות לרכב 2 בלבד. סכום השעות בכל ההזמנות הוא בדיוק 2K, וכך גם סכום השעות הזמינות. לכן אם יש פתרון, הוא יהיה חייב לקיים שסכום ההזמנות של רכב 1 הוא בדיוק K, כנדרש. עכשיו, כדי לצמצם את "הפער" בין הבעיה דמוית התרמיל שהצגתי לבין בעית התרמיל המקורית ניתן לפעול בשתי דרכים: או למצוא רדוקציה מבעית התרמיל לבעיה דמוית התרמיל, או לפתח את הרדוקציה הזאת כך שתפתור בעיה יותר כללית. הנה כמה מחשבות על הדרך השניה: הדרישה ש- 2K>N היא דרישה טכנית, שלדעתי אפשר להיפטר ממנה. מה שבטוח הוא שבאופן טריביאלי אפשר לשים כל קבוע אחר במקום ה- 2. לגבי העובדה שאנחנו מוצאים פתרון רק אם הסכום הוא בדיוק K - את זה אפשר היה לפתור אילו בבעית ההזמנות היתה איזושהי "עדיפות" (כלומר, כל כותב הזמנה היה כותב באיזה עדיפות הוא רוצה אילו רכבים, והיינו יכולים להכניס garbage collector נוסף - רכב 3 - שהיה אוסף את כל מי שלא קיבל את הזמנתו). זה גם היה מאפשר להכניס פנימה את עניין הערך לעומת גודל המשקולת לדעתי (אם כי לפי זכרוני המעומעם כבר יש רדוקציה לבעיה שבה הערך הוא המשקולת). זאת בקצרה ובלי לחשוב יותר מדי, והתחושה שלי (בדומה ל- easy) היא שעם נעבוד קצת יותר נגיע לרדוקציה. |
|
|
|
|
|
|
||
|
||||
|
שים לב שכחלק מההזמנה צריך לציין מאיזו שעה עד איזו שעה הרכב נדרש. התכונה הזו מקלה מכיוון שהיא מורידה באופן משמעותי את דרגות החופש של הפתרון. | |
|
|
|
|
|
||
|
||||
|
מצד אחד היא מקלה כי היא מצמצמת את החופש אך מצד שני היא מקשה על האלגוריתם למצוא סידור. חופש בהזזת עשות ההזמנה היה מקל על האלגוריתם, ויתכן אפילו שאחד חמדן היה מוצא פתרון טוב. אגב, האלגוריתם הנאיבי שפותר את הבעיה הוא: 1. כל עוד אין התנגשות שבץ את ההזמנה הנוכחית במקום שמתאים לה. 2. אם אין מקום להזמנה הנוכחית, חזור להזמנה הקודמת ומקם אותה במקום אחר שמתאים לה ושהיא עוד לא היתה בו אף פעם. 3. חזור ל 1. נאיבי, אקספוננציאלי אבל עובד. |
|
|
|
|
|
|
||
|
||||
|
צודק, פספסתי את זה (דרישה הגיונית כשמדובר בהזמנת מכוניות...). ברור שהתכונה הזאת מקלה. אני אחשוב על הבעיה עם ההגבלה הזאת. | |
|
|
|
|
|
||
|
||||
|
הערה טכנית: אלגוריתם דטרמיניסטי לא "עובד תמיד נכון", הוא או עובד נכון (תמיד), או לא נכון (מספיק שבמקרה אחד). עוד הערה טכנית: את הבעיה לא הסברת "שוב", הסברת אותה לראשונה. אם אתה מתכתב בנושא בכמה פורומים, מן הנימוס שתזכור עם מי דיברת על מה, או לפחות לא תנזוף באף אחד על שכחה. |
|
|
|
|
|
|
||
|
||||
|
הוא הסביר אותה "שוב", בפעם הראשונה "משום מה היא לא עלתה למערכת" תגובה 468939 (אם אתה נוזף באחרים כדאי שתבדוק שאתה לא נוזף בהם בטעות). | |
|
|
|
|
|
||
|
||||
|
לא הבנתי שכשהוא אומר שהוא ''תיכף יתאר אותה שוב'', הוא מתכוון באותה הודעה ממש. חשבתי שהוא מתכוון עוד שעתיים, כשיגיע זמן הפסקת הצהריים. תודה על התיקון, וסליחה לרן. | |
|
|
|
|
|
||
|
||||
|
עוד לא העליתי את התאור הפורמלי של בעיית סידור ההזמנות, פשוט זה בבית ועוד לא היה לי את הפנאי. אם זה ידרבן מישהו מהקוראים להתעסק עם זה, אני אעלה גם את האלגוריתם. שאלה: מה המשתנה, n, שעליו ניתן לומר שהאלגוריתם עובד ב O כלשהו של n? האם זה צי הרכבים N, האם מספר ההזמנות R? ועוד שאלה: האם טווח השעות בבעיה משנה לשייכותה למחלקה זו או אחרת? כלומר, אם הזמן בו ניתן לבקש רכב הוא סופי, למשל 24 שעות. או אם הזמן הוא לאינסוף. |
|
|
|
|
|
|
||
|
||||
|
לרוב נהוג כשעוסקים בהיבטים תיאורטיים כמו P מול NP לדבר על גודל הייצוג של הקלט. לכן לא סופרים כמה רכבים והזמנות יש, אלא האם כמה מקום לוקח לייצג אותם (בדומה לצורה שבה פונקציות על מספרים נמדדות בסיבוכיות שלהם לא ביחס לגודל המספרים, אלא לגודל הייצוג שלהם, שהוא לוגריתמי בגודל המספר כשאנחנו בבסיס ספירה גדול מ-1). | |
|
|
|
|
|
||
|
||||
|
למעשה אתה טוען שזה שקלול של השניים. זה בסדר, אין לי בעיה עם זה. ומה לגבי מהותו של עניין - לאיזו מחלקה הבעיה שייכת? |
|
|
|
|
|
|
||
|
||||
|
הבעיה שאתה מציג היא מסוג בעיית תזמון משאבים בגרף אינטרוולים. הבעיות האלה מעניינות בהקשר של P/NP כיוון ששינוי מאוד קטן בהגדרת הבעיה מעביר אותה מ- P ל- NPC. ספציפית נראה לי שהבעיה שאתה מתאר נמצאת ב- P אבל אני לא יודע להציג לה אלגוריתם ובפרט אני לא רואה אלגוריתם "סטנדרטי" שעובד בזמן ליניארי (אני חושב שצריך זמן ריבועי או משהו כזה). | |
|
|
|
|
|
||
|
||||
|
כמו שאמרו כאן, זו בעייה בסגנון "Interval Graph". אני לא מבין כלום בנושא, אבל אני מכיר מישהו שמבין ואשאל אותו. | |
|
|
|
|
|
||
|
||||
|
זה מאד יעזור, תודה. | |
|
|
|
|
|
||
|
||||
|
טוב, אין לי תשובה חד משמעית. בבירור זו בעיית צביעה של גרף אינטרוולים. הבעיה ה"כללית" (נתונה כמות צבעים מסויימת והשאלה היא האם את גרף האינטרוולים אפשר לצבוע באמצעותה כך שלא יהיו שני צמתים סמוכים בעלי אותו צבע) אפשר לפתור ביעילות בגלל התכונות הנחמדות של גרף האינטרוולים (משהו בסגנון "תמיד קיימת צומת שהשכנים שלה הם קליק"). אתה לעומת זאת מגביל את הצבעים שיכולים להיות בכל צומת, וזה ככל הנראה מקשה על הבעיה - אבל לא ברור אם עד לרמה של NP-שלמות. (אם הקשר לא ברור - "צבע" מתאים לרכב כלשהו; הצמתים בגרף מסמנים משימות; יש קשת בין שני צמתים אם ורק אם אלו משימות ש"עולות" אחת על השנייה; הצבעים החוקיים לצביעת צומת ספציפית הם צבעי כל הרכבים שהפרמטרים שלהם מתאימים למשימה שהצומת מייצגת). |
|
|
|
|
|
|
||
|
||||
|
טוב, גם לי אין תשובה חד משמעית... :-) כנראה שזה ישאר פתוח. היתה לי איזו תקווה שמישהו מהקוראים ירים את הכפפה, יקח את הבעיה ואת הפתרון ויוכיח משהו. לא נורא. אני אעשה עוד נסיון אחד, להעלות את הניסוח הפורמלי, הן של הבעיה והן של האלגוריתם, אולי זה יעיר מישהו. :-| רן. |
|
|
|
|
|
|
||
|
||||
|
אולי הוא מתכוון ל-PCP? אמנם זו בעיה בלתי-כריעה, לא ב-NP, אבל... מכך שזה לא נכון, לא הייתי קופץ למסקנה שלא לכך הוא התכוון. | |
|
|
|
|
|
||
|
||||
|
לא, לפי המשך השרשור, לא לכך הוא התכוון. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שהבעיה נקראת staff scheduling ונהוג לפתור אותה עם integer programming. | |
|
|
|
|
|
||
|
||||
|
http://en.wikipedia.org/wiki/Linear_programming#Inte... היא בכלל בעיה NP קשה (כך שלא ממש נהוג לפתור אותה). | |
|
|
|
|
|
||
|
||||
|
מה זאת אומרת "לא ממש נהוג לפתור אותה"? | |
|
|
|
|
|
||
|
||||
|
לבעיות שמצריכות תכנון בשלמים, במקרה הכללי, אין פתרון ישים. | |
|
|
|
|
|
||
|
||||
|
מה זאת אומרת אין פיתרון ישים? ברור שיש פיתרונות, רק שלא תמיד הם אופטימליים. | |
|
|
|
|
|
||
|
||||
|
נדמה לי, ותקן אותי אם אני טועה, שהבעיה שהוצגה כאן היא בעיית אופטימיזציה. | |
|
|
|
|
|
||
|
||||
|
אכן. לבעיות אופטימיזציה שהן NP-קשות נהוג למצוא פתרונות מקורבים. יש תחום מחקרי שלם (ומרתק) על "עד כמה טוב אפשר לקרב בעיה מסויימת בלי לקבל ש-P=NP". מסתבר שבעיות NP-שלמות נבדלות זו מזו באופן דרסטי במידת הקירוב האפשרית שלהן. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |