ریاضی کاربردی - مسیر های هنرمندانه

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