مسئله توریست منهتن

مسئله ی توریست منهتن (به انگلیسی : Manhattan Tourist Problem به اختصار MTP) یکی از مسائل مطرح در زمینه برنامه نویسی پویا است که در زمینه ی هم تراز کردن توالی ها بخصوص در بیوانفورماتیک کاربرد دارد. به طور خلاصه، هدف این مسئله یافتن مسیری از یک گره آغازین $S$به یک گره مقصد $D$در یک گراف توری (Grid) است به شکلی که از هرگره و یا یال حداکثر یکبار بگذریم و وزن مسیر حداکثر شود.

صورت مسئله

نقشه ی بخشی از محله ی منهتن

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

در این مسئله منظور از منهتن، یک گراف توری شکل است که مانند جدولی n در m است و نقطه ی $(0,0)$محل شروع مسیر و $(n,m)$نقطه ی پایان است. با توجه به شکل حرکت روی مسیر، می توان گفت که یال ها جهت دار و به سمت راست و یا پایین هستند و هر یال وزنی دارد که نشانگر تعداد جاذبه ها در خیابان نظیر آن است.

در شکل زیر یک نمونه مسئله ی توریست منهتن 4 در 3 مطرح شده و تعدادی از مسیر های ممکن، به علاوه ی مسیر جواب آورده شده:

الف) یک نمونه گراف توریست منهتن 4 در3 ب) یک مسیر غیر بهینه برای مسئله با امتیاز 11 ج) یک مسیر بهینه برای مسئله با امتیاز 23

راه حل

الگوریتم حریسانه

حل مثال پیشین به روش حریسانه، در گرهی که پررنگ شده انتخاب اشتباهی صورت گرفته و برای بهینه شدن مسیر، باید به راست رفته می شد

در این روش، در هر مرحله، سنگین ترین یال را انتخاب می کنیم و مسیر را ادامه می دهیم. واضح است که چنین روشی همواره به جواب بهینه با جمع یال های حداکثر نمی رسد چرا که در بعضی گره ها، انتخاب یال با وزن کمتر در نهایت به وزن کلی بیشتری می رسد. با توجه به اینکه در مسیر توریست منهتن n در m از $m+n$گره عبور می کنیم، چنین الگوریتمی نیز از $O(n+m)$خواهد بود اما به جواب درستی نخواهد رسید.

الگوریتم بازگشتی

در این روش برای پیدا کردن بهترین مسیر به نقطه ی $(x,y)$باید بهترین مسیر به نقاط $(x-1,y)$و $(x,y-1)$را یافت و وزن هر کدام را با یالی که آن را به نقطه ی $(x,y)$جمع زد تا از بین آن دو بزرگترین مقدار به عنوان بهترین مسیر به $(x,y)$معرفی شود.

این الگوریتم اگرچه به یک جواب بهینه می رسد اما از نظر زمان الگوریتم مناسبی نیست چرا که وزن مسیر بهینه از مبدا تا یک نقطه، به دفعات زیاد محاسبه می شود. در واقع وزن مسیر از مبدا به $(x,y)$به ازای تمام نقاطی طول و عرضی بزرگتر از آن دارند نیز محاسبه می شود و این زمان اجرای الگوریتم را طولانی می کند. کد چنین روشی به زبان پایتون به شکل زیر است:

def score(x,y , a,b):
    #weight of the edge connecting (x,y) to (a,b)
def MTP(n , m):
    if n==0 and m==0:
        return 0
    x , y = 0
    if n > 0:
        x = MTP(n-1 , m) + score(n-1,m , n,m)  
    if m > 0:
        y = MTP(n , m-1) + score(n,m-1 , n,m) 
    return max(x , y)

برنامه نویسی پویا

حل مسال قبلی با برنامه نویسی پویا: ابتدا مسیر به گره های سبز حساب می شود، سپس به گره های زرد، سپس به گره های قرمز، سپس آبی و بعد از آن نارنجی، و در نهایت بنفش و خاکستری

این روش از تکنیک های برنامه نویسی پویا استفاده می کند و به جای اینکه وزن مسیر از مقصد به مبدا حساب کنیم، از مبدا شروع می کنیم و مسیر بهینه را به هر گره حساب می کنیم بدین صورت که ابتدا مسیر بهینه به گره هایی که در فاصله ی 1 از مبدا قرار دارند حساب می شود، سپس گره هایی که در فاصله ی 2 هستند و الی آخر.

البته واضح است که نیازمند نگه داری وزن مسیر بهینه به هر گره در حافظه هستیم. بدین منظور می توان از یک ماتریس $(n+1)\times (m+1)$ استفاده کرد. از آن جایی که به همین تعداد باید محاسبه ی زیر انجام شود، این راه حل برای یک جدول n در m ، از $O((n+1)(m+1))$خواهد بود.

وزن مسیر بهینه به هر گره مانند روش بازگشتی از رابطه زیر بدست می آید:

$MTP(i,j)=\max {\begin{cases}MTP(i-1,j)+W(i-1,j,i,j)\\MTP(i,j-1)+W(i,j-,i,j)\end{cases}}$

در این رابطه منظور از MTP همان وزن مسیر بهینه و منظور از $W(i,j,t,k)$وزن یال بین $(i,j)$و $(t,k)$است.

جستارهای وابسته

• نظریهٔ گراف
• مسئله فروشنده دوره‌گرد
• توابع بازگشتی
• برنامه‌نویسی پویا