ریاضی کاربردی

1:38دوشنبه دهم بهمن 1384

روزبه ابرازی

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

مسئله:
فروشنده دوره گردی می خواهد از شهر های متعددی دیدن کند و سپس به نقطه شروعش برگردد در صورتی که زمانهای مسافرت بین شهر ها(یا اینکه طول مسیرها) داده شده باشد، چطور او خط سیرش را طراحی کند که از هر شهر دقیقا یک بار عبور کند و کوتاه ترین زمان ممکن را برای مسافرت صرف کند ؟

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

یک روش نسبی:
یک رهیافت ممکن آن است که اول دور همیلتنی 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 یال در یک زمان به جای دو یال موثر تر ساخت ، اما نکته شگفت آور اینکه بسط دادن بیشتر این ایده سودمند نیست.

مرجع : باندی ، مورتی ، نظریه گراف و کاربردهای آن، ترجمه دارا معظمی

12:55شنبه سوم دی 1384

مسیر های هنرمندانه

روزبه ابرازی

مسیر های هنرمندانه

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

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

مسیر بهینه برای 10 شهر

بعنوان مثال ،برای پیدا کردن کوتاه ترین مسیر ممکن برای 10 شهر یک کامپیوتر مجبور به ارزیابی 362،880(!9) امکان است.همین طور که شمار شهر ها افزایش می یابد ، شمار مسیر ها با سرعت موشک رشد می کند!

این نقشه ی یک مسیر بهینه شده از میان 13،509 شهر در آمریکا است.
طراح : Courtesy of William Cook, Georgia Tech

با این وجود ، محققان روش هایی را برای محاسبه مسیری بهینه برای شمار قابل توجهی از شهرها یافته اند.رکورد کنونی که در سال 2004 محاسبه شده ، گشتی است که از هر 24،978 شهر ، شهرک و روستای سوئد عبور می کند.(اینجا را ببینیدhttp://www.tsp.gatech.edu/sweden/index.html).این مسیر 72،500 کیلومتر طول دارد و هیچ مسیر کوتاهتری وجود ندارد.

این رکورد توسط David Applegate از آزمایشگاه تحقیقاتی شرکت تلگراف و تلفن آمریکا AT&T ،Robert Bixby از دانشگاه Rice ، Vašek Chvátal از دانشگاه Rutgers ،William Cook ازGeorgia Tech و Keld Helsgaun از دانشگاه Roskilde.

Robert Bosch ریاضیدان و Adrianne Herman دانشجوی کالج Oberlin در اوهایو در حال حاضر برنامه کامپیوتری ای را ساخته اند که مسئله فروشنده دوره گرد را به دنیای هنر می آورد. آنها از مسیرهایی استفاده می کنند که حاصل پاسخگویی به مسئله طراحی با خط ممتد(بدون برداشتن قلم از کاغذ) است.

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

Bosch و Herman با یک تصویر سیاه و سفید دیجیتالی شروع کردند. هر نقطه از تصویر درجه خاکستری ای بین 0(یعنی سیاه کامل ) و 255 (کاملا سفید) دارد. سپس تصویر به مربع هایی تقسیم شد ، هر مربع شامل یک بلوک از نقاط تصویری است.سپس متوسط تیرگی در هر کدام از مربع ها محاسبه می شود.

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

برای یافتن راه حلی متناظر با مسئله فروشنده دوره گرد ، Bosch وHerman شیوه ای مشابه با روشی را به کار بردند که گروه مشابه آنها در پیدا کردن رکورد گشت در سوئد به کار برده بودند.نتیجه این گشت یک طراحی با خطوط پیوسته از تصویر مورد نظر است.

را ه حل تقریبی مسئله فروشنده گرد برای مجموعه ای از 27،486 شهر با دقت جایگذاری شد ه تصویری مشابه و گیرا از مونالیزا را تولید می کند.
طراح :اهدا شده ی Robert Bosch

منظره ای بزرگ شده از مسیر لازم برای ایجاد نقاشی ای با خطوط پیوسته از مونالیزا
طراح :اهدا شده ی Robert Bosch

Bosch از همین تکنیک برای ایجاد شماری از نقاشی ها با خطوط پیوسته استفاده کرد این مسیرهای هنرمندانه در پاره ای از اوقات شامل 100،000 شهر می شود.

بنابراین تکنیک های رایج در حل مسائل بهینه سازی ( مسائلی که در محدوده مسیریابی تماس های تلفنی و زمانبندی ساخت و ساز برای تخصیص منابع و طراحی شبکه قرار دارند) همچنین می توانند در خلق آثار هنری ابتکاری نقش بازی کنند.

نویسنده: Ivars Peterson

لینک اصلی مقاله :

http://www.maa.org/mathland/mathtrek_01_03_05.html

منابع:

Becker, T.J. 2004. No accidental tourist. Research Horizons (Fall). Available at http://gtresearchnews.gatech.edu/reshor/rh-f04/tsp.html.

Bosch, R., and A. Herman. 2004. Continuous line drawings via the traveling salesman problem. Operations Research Letters 32(July):302-303. Preprint available at http://www.oberlin.edu/math/faculty/bosch/tspart.pdf.

Fowler, Y.G. 2004. One continuous line. Oberlin Alumni Magazine (Spring). Available at http://www.oberlin.edu/alummag/spring2004/ats.html.

Peterson, I. 2003. Constructing domino portraits. MAA Online (April 14).

______. 2000. Calculating swarms. Science News 158(Nov. 11):314-316. Available at http://www.sciencenews.org/articles/20001111/bob10.asp.

______. 1997. The traveling monkey. MAA Online (July 7).

Robert Bosch has a Web page at http://www.oberlin.edu/math/faculty/bosch.html. His domino artwork is featured at http://www.dominoartwork.com/.

Information about the traveling salesman problem is available at http://www.tsp.gatech.edu