בעיית הסוכן הנוסע - תכנות - HWzone פורומים
עבור לתוכן
  • צור חשבון

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


Aviyaari

Recommended Posts

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

(!O(n

 

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

קישור לתוכן
שתף באתרים אחרים

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

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

קישור לתוכן
שתף באתרים אחרים

ארכיון

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

×
  • צור חדש...