אלגוריתם קירוב
ויקיפדיה האנציקלופדיה encyclopedia
אלגוריתם קירוב (באנגלית: approximation algorithm) הוא אלגוריתם שמוצא פתרון שאינו בהכרח פתרון אופטימלי לבעיה נתונה, אלא פתרון שקרוב לפתרון אופטימלי. אלגוריתמים אלו שימושיים במיוחד בבעיות שהאלגוריתמים הידועים לפיתרונן הם בסיבוכיות גבוהה, ובפרט בבעיות NP קשות[1], קבוצת הבעיות NP קשות שקיים להם אלגוריתם קירוב נקראת APX, ניתן להוכיח שיש בעיות שאין להם אלגוריתם קירוב אלא אם כן P=NP.
על פי רוב מודדים קירוב של אלגוריתם בהתאם ליחס בין הפתרון שנמצא על ידי האלגוריתם לבין הפתרון האופטימלי. נאמר כי אלגוריתם קירוב לבעיה משיג יחס קירוב של (לפעמים נאמר גם אלגוריתם -מקרב) אם הפתרון המושג על ידי האלגוריתם קטן מ- פעמים הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מינימיזציה) או גדול מהחלק ה- של הפתרון האופטימלי לבעיה (אם הבעיה היא בעיית מקסימיזציה).