הצפנת תרמיל גב – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שורה 19:
אפשר לראות ב[[ניסוי וטעייה]] שהפתרון הוא [[תת-סדרה|תת-הסדרה]] <math>\{2,9,14\}</math> וקל לראות שזהו הפתרון היחיד במקרה זה. דרך אחרת להציג את הפתרון היא ה[[מרחב וקטורי|ווקטור]] <math>\mathbf{e}=(0,0,1,1,1,0)</math> (כלומר הוקטור מכיל אחדים בכניסות המתאימות לאיברים הנכללים בסכום התרמיל ובכל היתר אפסים).
 
אפשר לפתור את הבעיה ב[[כוח גס]], פשוט על ידי ניסוי כל האפשרויות של הווקטור <math>\mathbf{e}</math> עד שנמצאלמציאת אחדהוקטור שעונה על התנאי האמורהנכון. סיבוכיות הפתרון היא מסדר גודל של <math>O(2^n)</math>, אולם אפשר לחתוך את סיבוכיות הפתרון בפקטור של חצי על ידי אלגוריתם ההתנגשות הבא.
 
===אלגוריתם התנגשות לפתרון בעיית התרמיל הכללית===