PLS (סיבוכיות)

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת הסיבוכיות, מחלקת הסיבוכיות ( PLS (Polynomial Local Search היא תת-מחלקה סינטקטית של מחלקת הסיבוכיות TFNP. המחלקה הוגדרה על ידי כריסטוס פפדימטריו (Christos Papadimitriou) ב-1988 והבעיות הכלולות בה הן בעיות מקסימיזציה או מינימיזציה אשר מובטח כי יש להן פתרון. כשמה, מתארת המחלקה PLS בעיות חיפוש אשר בהינתן קלט, מוגדרת לו קבוצה של פתרונות אפשריים – לכל פתרון יש מחיר, והמטרה היא מציאת פתרון במחיר אופטימלי מקומי. על פי הגדרת הבעיה, לכל פתרון מוגדרת "סביבה" ("Neighborhood"). פתרון יחשב אופטימאלי באופן מקומי אם אין אף פתרון בסביבה שלו עם עלות טובה יותר.

מוטיבציה[עריכת קוד מקור | עריכה]

על אף שבאנליזת המקרה הגרוע בעיות PLS מתנהגות בצורה גרועה (זמן ריצה אקספוננציאלי), בפועל האלגוריתמים הם יעילים למדי.

בעיית PLS כללית[עריכת קוד מקור | עריכה]

תהי בעיה L (לדוגמה, בעיית הסוכן הנוסע – בעיית מינימיזציה). L נתונה על ידי קבוצת איברים D (ערים בהן יש לעבור), לכל איבר x \in D קיים סט סופי F(x) \ של פתרונות (מסלולים אפשריים העוברים בכל הערים) כל אחד מהם חסום פולינומית. לכל פתרוןs \in F(X), קיימת עלות אי שלילית c(s) \ (עלות הנסיעה במסלול) ורשימת שכנים N(s)\subseteq F(x) אשר תקרא הסביבה של פתרון s (תלוי בהגדרת יחס השכנות, לדוגמה עבור מסלול s נגדיר כי מסלול s' הוא שכן מסדר k אם בהצגת s ו – s' כמחרוזות, מרחק העריכה מ – s ל– s' הוא 2k). על האלגוריתם למצוא פתרון אופטימאלי מקומי, כלומר בהינתן L על האלגוריתם למצוא פתרון s אשר לא קיים לו שכן s' מסדר 1 אשר עלותו נמוכה יותר (כלומר שלכל  s'\in N(s) מתקיים (\ C(s)\leq C(s') ).

פתרון כללי לבעיית PLS[עריכת קוד מקור | עריכה]

ראשית נשים לב שכיוון שלכל x הדרישה היא כי הקבוצות D וכן  F(x) | (x \in D) הינן סופיות אזי קבוצת הפתרונות חסומה ולכן בהכרח קיים לה מקסימום, כלומר לבעיית PLS קיים תמיד פתרון. על מנת לפתור את הבעיה נניח קיום של 3 אלגוריתמים שזמן ריצתם פולינומי באורך הקלט.

A – בהינתן x \in D (רשימת ערים), A מחזיר פתרון כלשהו ל – x (מסלול כלשהו אשר עובר בכל הערים).

B – בהינתן x (רשימת ערים בהן יש לעבור) ומחרוזת s (סדר כלשהו של מעבר בין ערים) B יבדוק האם s הנו פתרון ל – x (האם s מתאר מעבר חוקי על כל הערים ב – x) ואם כן יחזיר את עלותו \ c(x).

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


PLSSolver(A,C,D)                  // A,C algorithms as described and the group D
 s = A(x)                         // Let s be some arbitraty initial solution
 While C(s) != local optimum      // If s is still not a local optimum
    s = C(x)                      // Generate a better solution from s's neighbors or state it is a local optimum


רדוקציות ב – PLS ו שלמות ב – PLS[עריכת קוד מקור | עריכה]

בעיה – L ב - PLS הינה PLS שלמה (PLS-Complete) אם לכל בעיה ב – PLS קיימת רדוקציה ל – L.

בעיה L ב – PLS ניתנת לרדוקציית PLS לבעיה K נוספת (PLS-reducible) אם קיימות פונקציות f,g בעלות זמן ריצה פולינומי המקיימות :

1. f ממפה איברים מ – L לאיברים של K.

2. בהינתן  x \in L ופתרון ל – \ f(x), הפונקציה g ממפה את הזוג((x, solution of f(x) לפתרון של x.

3. לכל איבר  x \in L , אם s הינו אופטימום מקומי עבור \ f(x), אזי \ g(s,x) הינו אופטימום מקומי עבור x.

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]