158

خانه رياضيات اصفهان

نزديك به يك قرن است كه پژوهش هايي در مورد مسئله درخت پوشاي مينيمم صورت مي گيرد . هر چند تا امروز هيچ اثباتي درباره پيچيدگي اين مسئله پيدا نشده است . ليكن تاريخ نسبتا كوتاه اين مسئله با ندازه در تاريخ علم برجسته و پر شكوه بوده است و منجر به حل مسائل بسيار و پيشرفت در حوزه الگويتم ها شده است . اهميت اين مسئله چنان است كه به قول ( :lirtesenمسئله درخت پوشاي مينيمم يك مسئله بنيادي در بهينه سازي تركيبي است و احساس مي شود مهد اصلي مسائل بهينه سازي تركيبي است ). به طور دقيقتر مسئله اينكه ، آيا الگوريتم قطعي وجود دارد كه در زمان خطي نسبت به تعداد يال ها اجرا شود ، همچنان مسئله اي باز در علم كامپيوتر است . در اين بررسي سعي شده است در ابتدا شرح مختصري را بر الگوريتم هاي كلاسيك درباره اين مسئله بدهيم و در ادامه به بحث و بررسي شيوه هاي جديد حمله به اين مسئله در طي دو دهه اخير بپردازيم . هر چند بررسي الگوريتم هاي قطعي درباره اين مسئله ، اهميت بسياري دارد ، ليكن روشهاي جديدتري چون روش هاي تصادفي ، احتمالي و الگوريتم هاي موازي براي اين مسئله ، در عمل توانسته اند نتايج بسياربهتري را فراهم سازند و به پيچيدگي خطي و يا حتي زير خطي نسبت به تعداد يال ها برسند . از اين رو در اين مقاله ما به بررسي يكي از اين الگوريتم ها كه توسط najrat , nielk, regrakانجام شده است و از جايگاه ويژه اي ، در شيوه هاي مدرن برخورد بامسئله درخت پوشاي مينيمم ، برخوردار است ، مس پردازيم . درادامه نيز گزارشي از پيشرفت هاي صورت گرفته در الگوريتم هاي قطعي ارائه ميدهيم . همچنين در اين سمينار سعي مي كنيم به بررسي مسائل مرتبط بامسئله درخت پوشاي مينيمم بپردازيم .

13/08/1386

290ل