شناسایی کوتاهترین دور همیلتونی در یک گراف کامل با اکسل

شرح پروژه

با سلام 

کوتاهرین دور همیلتونی در یگ گراف کامل مد نظرم هست. در واقع میخوام از یک گره شروع و از تمام گره ها فقط و فقط یک بار عبور کنم و به نقطه شرع برگردم. نمیخوام از نزدیک ترین همسایه شروع کنم چون جواب اشتباه به من میده. به عبارتی میخوام تمام مسیرها ایجاد بشه و min آن انتخاب بشه.

در واقع این مسئله، مسئله فروشنده دوره گرد هست، با این تفاوت که شما فقط از یک نقطه خاص شروع به حرکت میکنی و تمام دورهای همیلتونی را برای این نقطه یا گره بدست میاری و در نهایت هرکدوم کمتر بود انتخاب میشه.

به طور مثال طبق عکسی که فرستادم وقتی 4 تا گره داریم،6 تا یال داریم و 24 تا مسیر که هرکدوم از یک نقطه شروع و مجدد به خودش برمیگرده. ولی من نیاز به نقاط دیگر ندارم فرض کنید که من میخوام از نقطه a تمام این مسیرها رو بدست بیارم که تو این مثال تمام مسیرها اگر بخواد از a شروع بشه 6 حالت داره، فرض کنید انبار من a هست و باقی قسمت ها مغازه هستند. بنابراین تمام مسیرهای همیلتونی از انبار به مغازه ها رو میخوام که در انتها باید کوتاه ترین انتهاب بشه

میدونم وقتی سایز مسئله زیاد بشه تعداد حالات خیلی سریع زیاد میشه، که در واقع n فاکتوریل هست. یعنی برای 10 گره شما 3628800 مسیر داری که چون من فقط از یک گره میخوام شروع کنم 362880 مسیر داری که باید نرم افزار برای این تعداد مسیر مقادیر رو محاسبه کنه. حالا از شما تقاضا دارم که برای حداقل 50 گره این کار رو انجام بدید. یعنی نیاز داری به یک ماتریس متقارن 50 در 50 که خیلی ساده میشه تو اکسل این ماتریس رو ایجاد کرد.

اگر با فرمول نویسی انجام بشه که عالی میشه ولی اگر نشد با کد نویسی انجام بدید.

با تشکر طاهری

این پروژه شامل 1 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.

مهارت ها و تخصص های مورد نیاز

درباره کارفرما

aliscot

عضویت سه سال پیش

18 پروژه ثبت شده ،

0 پروژه در حال انجام ،

0 پروژه آماده دریافت پیشنهاد ،

نرخ پذیرش پیشنهاد 56%