עבור לתוכן

בעיית הסוכן הנוסע

Featured Replies

פורסם

אחת הבעיות המפורסמות ( ראו למשל ויקיפדיה) ממשפחת NP והסיבוכיות לפתרונה היא 

(!O(n

 

השאלה שלי היא האם ידוע אלגוריתם בסיבוכיות נמוכה יותר לבדיקת נכונותו של פיתרון נתון

פורסם

הבעיה בדרך כלל מנוסחת כבעיית החלטה, דהיינו לא "מהו המסלול הקצר ביותר" אלא "האם קיים מסלול שאורכו קצר מ-L כלשהו".

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

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים