|
|
עמוד:328
ברור כי התרשימים ( bj- 1 ( a ) מציגים עצים פורשים של הגרף הנתון . תרשים ( a ) מציג עץ טוב יותר מתרשים [ b ) משום שבתרשים ( a ) ניתן לראות כי סך ההוצאות שווה , ( 2 + 5 + 1 + 1 + 1 = ) 10 ואילו בתרשים (&) סך ההוצאות שווה . ( 5 + 2 + 1 + 10 + 1 = ) 19 קל לבדוק שלא ניתן למצוא עץ טוב יותר מזה שבתרשים ( a ) מבחינת סך ההוצאות למימון סלילת כבישים המחברים את כל היישובים לרשת . פתרון כזה מכונה בשם פתרון אופטימלי . לבעיית העץ הפורש המינימלי יכולים להיות פתרונות אפשריים רבים . («)) (&) -ו הם פתרונות אפשריים כי בשניהם כל היישובים מחוברים למערכת הכבישים ( . לכל פתרון יש ערך ( בבעיה שלנו הערך הוא סך ההוצאות לסלילת מערכת הכבישים , ( ואנו רוצים למצוא את הפתרון בעל הערך האופטימלי - המקסימלי או המינימלי ( בבעיה שלנו סך ההוצאות לסלילת מערכת הכבישים צריך להיות מינימלי . ( פתרון אופטימלי אינו בהכרח הפתרון האופטימלי , שכן ייתכנו מספר פתרונות שערכם אופטימלי . כפי שראינו , ia ) הוא פתרון אופטימלי . התרשים שבאיור הבא מציג פתרון אופטימלי נוסף לבעיה . סך ההוצאות ברשת זו גם כן שווה . ( 2 + 1 + 1 + 1 + 5 = ) 10 ערך הפתרון הזה אינו טוב ואינו גרוע מערך הפתרון . («) קל לראות שאי-אפשר לשפר את ערך הפתרון שבתרשימים ( a ) ( £ ) -ו והפתרון ( a ) או ( c ) הוא פתרון אופטימלי . התרשימים { c ) - ~ \ ia ) , { b ) מייצגים עצים פורשים , וקל לראות שניתן למצוא עצים פורשים נוספים עבור הרשת הנתונה . אך מבין כל העצים הפורשים רק ( 0 ) ( 0 ) -ו הם עצים פורשים מינימליים ( בדקו . (!
|
|