עם הופעתו של תכנות ליניארי, שיטות אלו יושמו על בעיות כולל הקצאה, זרימה מקסימלית ותחבורה. בעידן המודרני, אופטימיזציה קומבינטורית היא שימושית לחקר אלגוריתמים, עם רלוונטיות מיוחדת לבינה מלאכותית, למידת מכונה ומחקר תפעול.
למה משמש אופטימיזציה קומבינטורית?
אופטימיזציה קומבינטורית היא תהליך של חיפוש מקסימום (או מינימה) של פונקציה אובייקטיבית F שהתחום שלה הוא מרחב תצורה בדיד אך גדול (בניגוד ל-N-ממדי רווח רציף).
למה קשה אופטימיזציה קומבינטורית?
הקושי נובע מהעובדה ש בניגוד לתכנות ליניארי, האזור האפשרי של הבעיה הקומבינטורית אינו קבוצה קמורה.לפיכך, עלינו, במקום זאת, לחפש סריג של נקודות אפשריות, או במקרה של המקרה של מספר שלם מעורב, קבוצה של חצאי קווים או קטעי קו מפורקים כדי למצוא פתרון אופטימלי.
מהי בעיית האופטימיזציה הקומבינטורית?
אופטימיזציה קומבינטורית היא נושא המורכב ממציאת אובייקט אופטימלי מקבוצה סופית של אובייקטים … הוא פועל בתחום של אותן בעיות אופטימיזציה שבהן מכלול הפתרונות האפשריים הוא דיסקרטי או שניתן לצמצם לדיסקרטי, ובו המטרה היא למצוא את הפתרון הטוב ביותר.
האם אופטימיזציה קומבינטורית היא NP-קשה?
כאשר הוכח שגרסת החלטה של בעיית אופטימיזציה קומבינטורית שייכת למחלקה של בעיות NP-complete, אז גרסת האופטימיזציה היא NP-hard … בעיית האופטימיזציה, כלומר, מציאת המספר המינימלי (ק' לפחות) של מצולעים בצורת כוכב שהאיחוד שלהם שווה למצולע פשוט נתון, הוא NP-קשה.