בעיית איש מכירות נוסע
הבעיות של איש המכירות הנודדות עולות על ידי איש מכירות וקבוצת ערים. המוכר צריך לבקר בכל אחת מהערים החל מערים מסוימות (למשל, עיר הולדתו) ולחזור לאותה עיר. האתגר של הבעיה הוא שהמוכר הנוסע צריך למזער את אורך הטיול הכולל.
נניח שהערים הן x 1 איקס 2 ..... איקס נ שבו עלות ג ij מציין את עלות הנסיעה מעיר x אני ל-x י . הבעיה של איש המכירות הנוסע היא למצוא מסלול שמתחיל ומסתיים ב-x 1 שייקח את כל הערים בעלות המינימלית.
דוגמא: סוכן עיתונים מוציא מדי יום את העיתון לאזור שהוקצה בצורה כזו שהוא צריך לכסות את כל הבתים באזור המתאים בעלות נסיעה מינימלית. חשב את עלות הנסיעה המינימלית.
האזור שהוקצה לסוכן שבו עליו להטיל את העיתון מוצג באיור:
פתרון: מטריצת העלות-סמיכות של גרף G היא כדלקמן:
עֲלוּת ij =
הסיור מתחיל מאזור H 1 ולאחר מכן בחר את אזור העלות המינימלי שניתן להגיע אליו מ-H 1 .
סמן אזור H 6 מכיוון שזהו אזור העלות המינימלי שניתן להגיע אליו מ-H 1 ולאחר מכן בחר אזור עלות מינימלית שניתן להגיע אליה מ-H 6 .
סמן אזור H 7 מכיוון שזהו אזור העלות המינימלי שניתן להגיע אליו מ-H 6 ולאחר מכן בחר אזור עלות מינימלית שניתן להגיע אליה מ-H 7 .
סמן אזור H 8 מכיוון שזהו אזור העלות המינימלי שניתן להגיע אליו מ-H 8 .
סמן אזור H 5 מכיוון שזהו אזור העלות המינימלי שניתן להגיע אליו מ-H 5 .
סמן אזור H 2 מכיוון שזהו אזור העלות המינימלי שניתן להגיע אליו מ-H 2 .
סמן אזור H 3 מכיוון שזהו אזור העלות המינימלי שניתן להגיע אליו מ-H 3 .
סמן אזור H 4 ולאחר מכן בחר את אזור העלות המינימלי שניתן להגיע אליו מ-H 4 זה H 1 .אז, באמצעות האסטרטגיה החמדנית, אנו מקבלים את הדברים הבאים.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
לפיכך עלות הנסיעה המינימלית = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
מטרואידים:
מטרואיד הוא זוג מסודר M(S,I) המקיים את התנאים הבאים:
- S הוא קבוצה סופית.
- I היא משפחה לא ריקה של תת-קבוצות של S, הנקראות תת-קבוצות עצמאיות של S, כך שאם B ∈ I ו-A ∈ I. אנו אומרים שאני תורשתי אם הוא עונה על תכונה זו. שימו לב שהקבוצה הריקה ∅ היא בהכרח איבר ב-I.
- אם A ∈ I, B ∈ I ו- |A| <|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property. < li>
אנו אומרים שמטרויד M (S, I) משוקלל אם יש פונקציית משקל משויכת w המקצה משקל חיובי בהחלט w (x) לכל אלמנט x ∈ S. פונקציית המשקל w משתרעת על תת-קבוצה של S על ידי סיכום :
w (A) = ∑<sub>x∈A</sub> w(x)
עבור כל A ∈ S.
