راجع به مسئله فروشنده دوره گرد قبلا هم نوشته بودم این بار می خواهم یکی از راه حل هایی که نه جواب اصلی(اپتیمال) بلکه جواب بهینه ای را بدست میدهد مطرح کنم .
مسئله:
فروشنده دوره گردی می خواهد از شهر های متعددی دیدن کند و سپس به نقطه شروعش برگردد در صورتی که زمانهای مسافرت بین شهر ها(یا اینکه طول مسیرها) داده شده باشد، چطور او خط سیرش را طراحی کند که از هر شهر دقیقا یک بار عبور کند و کوتاه ترین زمان ممکن را برای مسافرت صرف کند ؟
بصورت نموداری هدف یافتن دور همیلتنی با وزن مینیمم در یک گراف کامل وزندار است . چنین دوری را یک دور اپتیمال می نامند.تا کنون الگوریتم موثری برای یافتن جواب اصلی یافت نشده بنابراین مطلوب است روشی برای یافتن جواب خوب و معقولانه .
یک روش نسبی:
یک رهیافت ممکن آن است که اول دور همیلتنی C را بیابیم ، و سپس با اصلاحات مناسب C یک دور همیلتنی دیگر با وزن کمتر جستجو کنیم.شاید ساده ترین اصلاح بصورت زیر باشد .
فرض کنیدC=V1,V2,….Vn باشد در این صورت برای همه مقادیر i وj به طوری که n>j>i+1 >1 ، می توانیم دور همیلتنی جدید
Cij=V1,V2….Vi,Vj,Vj-1,….Vi+1,Vj+1,Vj+2….Vn,V1
را با حذف یالهای Vi,Vi+1 و Vj,Vj+1 و اضافه کردن یالهای Vi,Vj وVi+1,Vj+1 به صورتی که در شکل نشان داده شده به دست بیاوریم.
شکل (1)
اگر برای مقداری از i و j داشته باشیم( (w(Vi,Vj منظور وزن یال Vi,Vj است):
W(Vi,Vj)+W(Vi+1,Vj+1) < W(Vi,Vi+1)+W(Vj,Vj+1)
دور Cij دور اصلاح شده ای از C خواهد بود.
بعد از اجرای دنباله ای از اصلاحات بالا ، دوری باقی می ماند که نمی توان آن را به وسیله این روش بیشتر اصلاح کرد.این دور نهایی تقریبا بصورت مطمئن اپتیمال نیست ، اما فرض معقولانه آن است که این دور نسبتا خوب است ، برای دقت بیشتر می توان این شیوه را به دفعات تکرار کرد ، و هر بار با دور جدیدی آغاز کرد.
مثلا گراف وزندار شکل 2 را در نظر بگیرید :
شکل (2)
با دورL MC NY PA PE T Lشروع می کنیم دنباله ای از 3 اصلاح را می توانیم به کار ببریم ، وبادورL NY MC T PE PA L به وزن 192 کار را خاتمه می دهیم(شکل 3).
شکل (3)
دلیل درستی این روش را میتوان به زبان ساده چنین توضیح داد:
اگر راس V را با دو یالی که از آن عبور می کند از دور اپتیمال حذف کنیم مسیری بدست می آید که 2 خصوصیت دارد 1. اینکه همبند و با حداقل یال است (درخت) 2. اینکه کمترین وزن را دارد.
حال اگر شرط مسیری بودن این درخت را هم حذف کنیم لا اقل این باقیمانده درختی با کمترین وزن است این درخت برای مثال زده شده در شکل4 نشان داده شده.
شکل (4)
وزن این درخت122است حال اگر با کمال خوش شانسی این درخت حالت مسیری هم داشته باشد ما برای اینکه به یک دور همیلتنی برسیم نیاز به اضافه کردن راس V با 2 یال که ازV عبور می کنند به مسیر موجود هستیم اگر این یالها را هم از یالهای با کمترین وزن انتخاب کنیم به عدد 122+21+35=178 می رسیم . و چون وزن دوری که پیدا کرده بودیم لا اقل کران بالایی برای دور اپتیمال است پس داریم.
178 < W(C) < 192
و این اختلاف ناچیز بین دو کران خود گویای کار آمدی روش ماست.
روشی که در اینجا شرح دادیم بعدا به وسیله لین (1965) و هلد وکارپ(1970،1971) بسط یافت . بخصوص لین دریافت که شیوه اصلاح دور را می توان با قرار دادن 3 یال در یک زمان به جای دو یال موثر تر ساخت ، اما نکته شگفت آور اینکه بسط دادن بیشتر این ایده سودمند نیست.
مرجع : باندی ، مورتی ، نظریه گراف و کاربردهای آن، ترجمه دارا معظمی
