🚚 مسئله فروشنده دورهگرد (TSP) چیست؟فرض کنید یک فروشنده باید از چندین شهر بازدید کند. چطور میتواند…
انتشار: 2026/08/12 15:14 UTCدریافت: 2026/08/15 03:13 UTCآخرین مشاهده: 2026/08/15 03:13 UTC
🚚 مسئله فروشنده دورهگرد (TSP) چیست؟فرض کنید یک فروشنده باید از چندین شهر بازدید کند. چطور میتواند کوتاهترین مسیر را پیدا کند؟ 🤔هدف TSP این است که از یک شهر شروع کنیم، دقیقاً یکبار از تمام شهرها بگذریم، به شهر اول برگردیم و مجموع مسافت را حداقل کنیم.📍 مطابق ویدیو (مثال برای ۵ شهر A تا E):1️⃣ مسیر اول: A ➔ B ➔ D ➔ E ➔ C ➔ A (مسافت: ۵۳)2️⃣ مسیر دوم: A ➔ C ➔ D ➔ E ➔ B ➔ A (مسافت: ۳۴)همانطور که در ویدیو میبینید، مسیر دوم بسیار بهینهتر است.💡 چرا TSP مهم است؟بررسی همه حالتها با افزایش شهرها انفجاری رشد میکند؛ مثلاً برای ۲۰ شهر حدود ۶۰ کوادریلیون مسیر وجود دارد! 🤯🧠 راهکار: الگوریتمهای تقریبیاینجاست که الگوریتم کریستوفیدس (Christofides) وارد میشود؛ روشی که با ترکیب درخت پوشای کمینه (MST) و تطبیق کمینه (Matching)، در زمانی کوتاه تور بهینهای میسازد.🎯 تضمین ریاضی:جواب بدست آمده حداکثر 1.5 برابر جواب بهینه سرتاسری (مطلق) است.یعنی مجموع مسافت بدست آمده در این مسیر ارائه شده توسط الگوریتم حداکثر 1.5 برابر مسافت بهترین مسیر ممکن است.
پستهای تلگرام — انجمن علمی مهندسی صنایع دانشگاه ارومیه
🔴 دانشجویان گرامی دانشکده فنی و مهندسیبا سلام و احترام،به اطلاع میرساند اداره آموزش دانشکده فنی و مهندسی، بهمنظور تسهیل دسترسی دانشجویان به اطلاعیهها و اطلاعات آموزشی، کانال رسمی اطلاعرسانی آموزش دانشکده را راهاندازی کرده است.🔺کلیه اخبار، اطلاعیهها، بخشنامهها، تقویمهای آموزشی و موارد مرتبط با امور آموزشی از طریق این کانال منتشر خواهد شد.🔺از تمامی دانشجویان در مقاطع کارشناسی، کارشناسی ارشد و دکتری و تمامی ورودیها درخواست میشود برای دریافت بهموقع اطلاعیهها، نسبت به عضویت در این کانال اقدام فرمایند.🔹تلگرام: t.me/UU_ENG%F0%9F%94%B8%D8%A7%DB%8C%D8%AA… eitaa.com/UU_ENG%F0%9F%9F%A1 توجه: از این پس، اطلاعیههای اداره آموزش دانشکده صرفاً از طریق این کانال رسمی منتشر میشود و در کانالهای انجمنهای علمی، گروههای دانشجویی یا سایر رسانههای غیررسمی منتشر نخواهد شد.با سپاس از همکاری شمااداره آموزش دانشکده فنی و مهندسی
🚚 مسئله فروشنده دورهگرد (TSP) چیست؟ فرض کنید یک فروشنده باید از چندین شهر بازدید کند. چطور میتواند کوتاهترین مسیر را پیدا کند؟ 🤔 هدف TSP این است که از یک شهر شروع کنیم، دقیقاً یکبار از تمام شهرها بگذریم، به شهر اول برگردیم و مجموع مسافت را حداقل کنیم.…🧠راه حل استاد ایرانی دانشگاه واشنگتن برای مسئله فروشنده ی دوره گرد🧠بعد از گذشت حدود ۵۰ سال از الگوریتم کریستوفیدس برای TSP، راه حل جدیدی توسط دکتر شایان اویس قرن ارائه شد.🔹 دستاورد دکتر شایان اویسقرن چه بود؟شایان اویسقَرَن ، پژوهشگر ایرانیتبار و استاد دانشگاه واشینگتن، به همراه همکارانش روی این مسئله کار کرد. آنها با استفاده از ترکیبی از مفاهیم بهینهسازی، نظریه گراف و روشهای احتمالاتی، رویکردهای جدیدی برای حل مسئله فروشنده دورهگرد توسعه دادند. 🔹راه حل شایان اویس قرن چه بود؟اگر بخواهیم ایده کار را خیلی ساده بیان کنیم، بهجای اینکه برای ساخت مسیر تنها به یک انتخاب مشخص و ثابت متکی باشیم، میتوان از میان مجموعهای از ساختارهای مناسب، انتخابهای هوشمندانهتر و احتمالاتی انجام داد و سپس آنها را به یک مسیر مناسب تبدیل کرد. این دیدگاه باعث شد پژوهشگران بتوانند از مرزی عبور کنند که برای دههها در روشهای تقریبی TSP پابرجا مانده بود.دستاوردهای او در حوزه الگوریتمها و بهینهسازی، از جمله پژوهشهای مرتبط با TSP، در نهایت به کسب مدال Abacus اتحادیه بینالمللی ریاضیات (IMU) در سال ۲۰۲۶ منجر شد.
📌 سلسله وبینارهای « ایستگاه حکمرانی » انجمن علمی مدیریت دانشگاه ارومیه با همکاری سایر انجمن های سراسر کشور برگزار میکند:💥 وبینار اول « بحران انرژی ؛ کمبود منابع یا ضعف مدیریت؟ »🔸 محورهای سخنرانی: اقتصاد انرژی و حکمرانی منابع ابعاد فنی و اجرایی بحران انرژی با سخنرانی🔹 دکتر رحمان سعادت ؛ دکتری اقتصاد بینالملل و منابع و هیئت علمی مدیریت دانشگاه سمنان 🔹 دکتر توحید غنی زاده ؛ مشاور و عضو کمیته تحقیقات شرکت توزیع برق آذربایجان غربی ٬ مدیرعامل شرکت دانش بنیان پویان انرژی گستران نوین طلوع 📅 تاریخ برگزاری: چهارشنبه ۲۸ مرداد ⏰ ساعت ۱۹:۳۰🔻 لینک برگزاری :skyroom.online/ch/urmia.university/aedmo%… ارتباطی انجمن علمی دانشجویی مدیریت دانشگاه ارومیه:🌐 zil.ink/management_uu%F0%9F%86%94 @management_uu
🚚 مسئله فروشنده دورهگرد (TSP) چیست؟ فرض کنید یک فروشنده باید از چندین شهر بازدید کند. چطور میتواند کوتاهترین مسیر را پیدا کند؟ 🤔 هدف TSP این است که از یک شهر شروع کنیم، دقیقاً یکبار از تمام شهرها بگذریم، به شهر اول برگردیم و مجموع مسافت را حداقل کنیم.…💡 فکت جالبجالبه که بدونید الگوریتم کریستوفیدس در سال ۱۹۷۶ ارائه شد و نزدیک به ۵۰ سال بود که هیچکس نتوانست الگوریتم عمومی بهتری جایگزین آن کند! یعنی با تمام پیشرفتهای عظیم ابرکامپیوترها و هوش مصنوعی در این نیمقرن، هیچ روش منطقی بهتری پیدا نشده بود که بتواند ضریب ۱.۵ این الگوریتم را در حالت کلی شکست دهد و این ضریب همچنان دستنخورده باقی مانده بود! 🤯
دانشجویانی که ترم تابستان کارآموزی برداشتن بایستی این فرم ها رو پرینت و در حین کار آموزی هم خودشان هم شرکت مورد نظر پر کنن و در آخر به همراه نامه برگشتی از شرکت این فرم ها رو ضمیمه کنن و به استاد مربوطه ارسال یا تحویل فیزیکی دهند.@uu_industrial1
تقویم آموزشی دانشگاه ارومیه برای دانشجویان در سال تحصیلی 1405-1406 براساس پیشنهاد شورای آموزشی و تصویب هیئت رئیسه دانشگاه