מערכים ב-PASCAL או ב- C++/C
- פותח הנושא urn
- פורסם בתאריך
הבעייה היא ב NPC
ידידי הבעייה שהצגת שייכת לסוג מיוחד של בעיות שאין להם פתרון יעיל
הפתרון הכי יעיל שקיים לוקח זמן אקספוננציאלי (2 בחזקת N כש N גודל הקלט) הבעיה NP-COMPLETE ולכן אין פתרון יעיל לבעיה (אם תמצא כזה תהיה איש עשיר מאוד
). בכל אופן האלגוריתם הנאיבי הוא לקחת את כל הצירופים של איברים במערך אם גודל המערך הוא N יש 2 בחזקת N כאלה ועבור כל צירוף לבדוק האם הוא מסתכם ל X
ידידי הבעייה שהצגת שייכת לסוג מיוחד של בעיות שאין להם פתרון יעיל
בבקשה ... (סוף סוף דיון מעניין )
בעיות NPC נוספות : בעיית כיסוי מינימלי ע"י קודקודים - בהינתן גרף צריך למצוא את קבוצת הקודקודים המינימלית כך שלכל צלע בגרף לפחות אחד הקודקודים יהיה בקבוצה . בעיית המעגל ההמילטוני מציאת מעגל פשוט בגרף המכיל את כל הקודקודים בגרף . ואולי המפורסמת מבעיות ה NPC - בעיית הוכן הנוסע - סוכן צריך לבקר ב X ערים . נתון לו גרף עם כבישים המחברים בין הערים ואת אורך כל כביש - משימתו , למצוא את המסלול הקצר ביותר שעובר בין כל הערים . יש בעיות רבות אחרות ( 3 SAT , בעיית הקליקה והמקבילה לה , בעיית "הקבוצה העצמאית " ) . אם מישהו מתעניין , יש תכונות מעניינות לבעיות מהקבוצה הזו . אשמח לכוון אתכם . בהצלחה
בעיות NPC נוספות : בעיית כיסוי מינימלי ע"י קודקודים - בהינתן גרף צריך למצוא את קבוצת הקודקודים המינימלית כך שלכל צלע בגרף לפחות אחד הקודקודים יהיה בקבוצה . בעיית המעגל ההמילטוני מציאת מעגל פשוט בגרף המכיל את כל הקודקודים בגרף . ואולי המפורסמת מבעיות ה NPC - בעיית הוכן הנוסע - סוכן צריך לבקר ב X ערים . נתון לו גרף עם כבישים המחברים בין הערים ואת אורך כל כביש - משימתו , למצוא את המסלול הקצר ביותר שעובר בין כל הערים . יש בעיות רבות אחרות ( 3 SAT , בעיית הקליקה והמקבילה לה , בעיית "הקבוצה העצמאית " ) . אם מישהו מתעניין , יש תכונות מעניינות לבעיות מהקבוצה הזו . אשמח לכוון אתכם . בהצלחה
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.