בעיית הסוכן הנוסע
בעיית הסוכן הנוסע שואלת: יש רשימת ערים. מהו המסלול הכי קצר שעובר בכל עיר פעם אחת וחוזר להתחלה? זו בעיה קשה למחשב לפתור בדיוק. הבעיה ידועה כבר מהמאה ה-19. מדענים המשיכו לחקור אותה במאה ה-20. ב-1991 נבנתה ספרייה של דוגמאות בשם TSPLIB. את הבעיה אפשר לראות כרשת. כל עיר היא נקודה. הקווים בין נקודות מרא...
אלגוריתם חמדן
אלגוריתם חמדן זה דרך לפתור בעיות. אלגוריתם = סדרת חוקים לפתרון. חמדן = בוחר את מה שנראה הכי טוב עכשיו. זה בדרך כלל מהיר. לפעמים הוא נותן פתרון טוב. לפעמים לא. חמדנים עוזרים כשאין זמן לחשוב הרבה. יש בעיות שקשה מאוד לפתור מהר. לפעמים הבחירה החמדנית גם היא הכי טובה. - סוכן נוסע: כל פעם נוסעים ליישוב ...
אלגוריתם קירוב
אלגוריתם קירוב הוא דרך למצוא פתרון קרוב לטוב ביותר. זה שימושי כשהפתרון הטוב קשה למצוא. במדע המחשב יש בעיות שקשה מאוד לפתור בדיוק. קוראים להן NP-קשות (בעיות קשות). יש בעיות שאפשר רק לקרב, לא לפתור בדיוק. יש אלגוריתמים שנותנים תשובה קרובה בקבוע מסוים. יש גם סכמות שקוראות לפרמטר קטן ε, ומשפרות את הקר...
גרף (תורת הגרפים)
גרף הוא ציור של נקודות וקווים שמחברים אותן. הנקודות נקראות קודקודים או צמתים. הקווים נקראים צלעות או קשתות. צלע מחברת שתי נקודות. גרף בנוי משתי רשימות: רשימת נקודות ורשימת קווים. אפשר להשתמש בגרף כדי לפתור בעיות. למשל בעיית הסוכן הנוסע. שם צריך לעבור בכל עיר פעם אחת. בערים האלה הנקודות הן הערים, ...