שיחה:האלגוריתם של פרים

חמדני או אופטימלי

תגובה אחרונה: לפני 14 שניםתגובה אחתאדם אחד בשיחה

האם אכן מדובר באלגוריתם חמדני (היוריסטי) או אופטימלי? זה לא ברור מהמידע.

חמדני לא שווה להיוריסטי. יש הרבה אלגוריתמים חמדנים שהם אופטימאליים. חמדני = בכל שלב עושה את הפעולה שמביאה לאופטימום הלוקאלי. יש הרבה בעיות בהן האופטימום הלוקאלי הוא גם הגלובאלי. אלגוריתם היוריסטי או שמשתמש בהיוריסטיקות למציאת פתרון מקורב (למשל עץ שהוא כבד לכל היותר ב10% מעץ פורש מינימלי) או שמשתמש בהיוריסטיקות כדי לפתור את הבעייה בזמן אסימפטוטי קטן יותר במקרה ממוצע (למשל אלגוריתם שמוצא עץ פורש מינימלי בO(N)‎ בממוצע). בכל מקרה כתוב בערך שהוא מוצא את העץ המינימלי, משמע הוא אופטימלי. בונגלו - שיחה 12:22, 1 באוקטובר 2009 (IST)תגובה

השוואה לאלגוריתם דייקסטרה

האלגוריתם שונה מהותית מהאלגוריתם של דייקסטרה. בעוד שדייקסטרה, בעת בחירת הצומת הבא, מתחשב באורך (משקל) של כל המסלול משורש העץ לצומת, פרים בוחר לפי הקשת האחרונה בדרך אליו בלבד!

משוב מ-21 בספטמבר 2011

תגובה אחרונה: לפני שנתיים2 תגובות2 אנשים בשיחה

אלגוריתם פרים וקרוסקל תמיד יחזירו את אותו עץ פורש? 212.235.89.188 13:55, 21 בספטמבר 2011 (IDT)תגובה

כן Maromblu - שיחה 17:57, 24 בינואר 2022 (IST)תגובה

דיווח על טעות

תגובה אחרונה: לפני 7 שנים2 תגובות2 אנשים בשיחה

פרטי הדיווח

"מרק רחמן" מפנה לעמודים לא קשורים דווח על ידי: 176.228.158.40 01:25, 9 במאי 2017 (IDT)תגובה

ההשחתה תוקנה. אביהו - שיחה 20:12, 9 במאי 2017 (IDT)תגובה

הוספת נושא