הצגת המקור של הדף "אלגוריתם קירוב"

'''אלגוריתם קירוב''' (ב[[אנגלית]]: '''approximation algorithm''') הוא [[אלגוריתם]] שמוצא פתרון שאינו בהכרח פתרון אופטימלי לבעיה נתונה, אלא פתרון שקרוב לפתרון אופטימלי. אלגוריתמים אלו שימושיים במיוחד בבעיות שהאלגוריתמים הידועים לפתרונן הם בסיבוכיות גבוהה, ובפרט ב[[NP-קשיות|בעיות NP קשות]]{{הערה|שם=Bernard. 2011|{{Cite book|url=https://www.worldcat.org/oclc/671709856|title=The design of approximation algorithms|last=Bernard.|first=Shmoys, David|date=2011|publisher=Cambridge University Press|isbn=9780521195270|oclc=671709856}}}}, קבוצת הבעיות NP קשות שקיים להם אלגוריתם קירוב נקראת [[APX]], ניתן להוכיח שיש בעיות שאין להם אלגוריתם קירוב אלא אם כן [[P=NP]].

על פי רוב מודדים קירוב של אלגוריתם בהתאם ליחס בין הפתרון שנמצא על ידי האלגוריתם לבין הפתרון האופטימלי. נאמר כי אלגוריתם קירוב לבעיה משיג [[יחס קירוב]] של <math>c</math> (לפעמים נאמר גם אלגוריתם <math>c</math>-מקרב) אם הפתרון המושג על ידי האלגוריתם קטן מ-<math>c</math> פעמים הפתרון האופטימלי לבעיה (אם הבעיה היא [[בעיית מינימיזציה]]) או גדול מהחלק ה-<math>c</math> של הפתרון האופטימלי לבעיה (אם הבעיה היא [[בעיית מקסימיזציה]]).

== סוגי אלגוריתמי קירוב==

ישנם כמה סוגים של אלגוריתמי קירוב, שנבדלים ביניהם בסוג הקירוב שהם מציעים ובסיבוכיות שלהם:

===קירוב באמצעות קבוע===

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

===סכמת קירוב פולינומית (PTAS)===

אלגוריתמי קירוב מסוג [[סכמת קירוב פולינומית]]{{הערה|Petra Schuurman, Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/papers/ptas.pdf Approximation Schemes – A Tutorial]|כיוון=שמאל}} מקבלים <math>\varepsilon</math> כלשהו כקלט ומתייחסים אליו כקבוע, ומציעים קירוב של מכפלה של <math>1 - \varepsilon</math> מהערך האופטימלי (או <math>1+\varepsilon</math> בבעיות מינימום). כל זה בזמן פולינומי לגודל הקלט, זה עלול להיות אקספוננציאלי ביחס ל-<math>1/\varepsilon</math> (הוא יכול להיות החזקה).

תת קבוצה של אלגוריתמים אלו היא סכמת קירוב פולינומית מלאה ('''FPTAS'''). באלגוריתמים אלו הסיבוכיות פולינומית גם בגודל הקלט וגם ב-<math>1/\varepsilon</math>. קירוב כזה קיים לבעיית תרמיל הגב למשל.

== דוגמה לאלגוריתם קירוב ==

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

בעיה זו היא [[NP-קשה]], אולם ניתן לקרב אותה באופן הבא (האלגוריתם של קריסטופידס{{הערה|1=Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.|כיוון=שמאל}}):

'''אלגוריתם''':
מוצאים [[עץ פורש מינימלי]] בגרף. בוחרים צומת כלשהו כשורש, ומטיילים לעומקו של העץ, ב[[מסלול (תורת הגרפים)|מסלול]] ששקול ל[[DFS|חיפוש לעומק]]. כאשר אנו מגלים שאנו חוזרים לצומת בו כבר היינו, נבצע "קיצור דרך", דהיינו, נמשיך ישירות לצומת הבא ברשימה - וזאת עד שביקרנו בכל הצמתים ונחזור לצומת שממנו התחלנו.

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

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

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

לפיכך, האלגוריתם שתואר הוא אלגוריתם קירוב עם [[יחס קירוב]] של 2.

==ראו גם==
*[[שיטות חלוקה]]
*[[בעיית כיסוי קבוצות]]
*[[בעיית תרמיל הגב]]

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{בקרת זהויות}}

[[קטגוריה:אלגוריתמים|קירוב]]