ট্রাভেলিং সেলসম্যান মূলত একটি NP-complete ক্লাসিকাল প্রবলেম। uva 10702 মূল প্রবলেমের পরিবর্তিত রূপ যা ডাইনামিক প্রোগ্রামিং এর মাধ্যমে সমাধান করা সম্ভব। একজন ফেরিওয়ালা এক শহর থেকে অন্য শহরে ঘুরে জিনিসপত্র বিক্রি করে। সে কোনো শহরে একাধিক বার যেতে পারে(ক্লাসিক tsp প্রবলেমে একটি নোড একবারের বেশি ভিজিট করা যায়না)। একটি শহর থেকে আরেকটি শহরে গেলে নির্দিষ্ট পরিমাণ লাভ হয়। ফেরিওয়ালা নির্দিষ্ট কিছু শহরে তার যাত্রা শেষ করে এবং যাত্রা শেষ করার আগে নির্দিষ্ট সংখ্যক বার বিভিন্ন শহরে ভ্রমণ করে(inter-city travel)। বলতে হবে সে সর্বোচ্চ কত লাভ করতে পারবে। এই প্রবলেমে গ্রাফটি complete,সব শহর থেকে সব শহরে যাওয়া যায়।
sample ইনপুটে ফেরিওয়ালা সর্বোচ্চ ২বার ভ্রমণ করতে পারবে, ভ্রমণের পথ হবে ১-৩,৩-২,এতে লাভ হবে ৫+২=৭ যা এই গ্রাফের জন্য সর্বোচ্চ।
ডাইনামিক প্রোগ্রামিং এর সাহায্যে সমস্যাটি সমাধান করা যায়। ধরি F(n,d) হলো আমাদের ফাংশন। ধরা যাক আমি এখন n তম শহরে আছি এবং আমি আর d সংখ্যক ভ্রমণ করতে পারব, f(n,d) রিটার্ণ করবে এ অবস্থায় আমার পক্ষে সর্বোচ্চ যত লাভ করা সম্ভব সেটা। কিন্তু সর্বোচ্চ লাভ পাব কি করে? মনে করি n তম শহর থেকে a,b তম শহরে যাওয়া যায়। তাহলে:
f(n,d)=max( w[n][a]+ ‘a তম শহর থেকে d-1 বার ভ্রমন করে গন্তব্য পৌছানোর পর অর্জিত মুনাফা’ , w[n][b]+ ‘b তম শহর থেকে d-1 বার ভ্রমন করে গন্তব্য পৌছানোর পর অর্জিত মুনাফা’ )
বা,f(n,d)=max( w[n][a]+F(a,d-1) , w[n][b]+F(b,d-1) )
এই ফাংশনটি ভালো ভাবে বুঝলেই সমস্যা সমাধান হয়ে যাবে। এখন আমাদের দরকার একটি base case। যখন d==1 তখন অবশ্যই আমাদেরকে কোনো একটি “গন্তব্য শহর” এ ভ্রমণ করতে হবে কারণ তারপর আর ভ্রমণ করা সম্ভব নয়। যেখানে গেলে সর্বোচ্চ লাভ হবে সেটা রিটার্ন করে দিতে হবে এ ক্ষেত্রে। আমি ফাংশনটি লিখেছি এভাবে:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
i64 call(i64 u,i64 d) { if(d==0) return 0; if(!vis[u][d]) { vis[u][d]=1; i64 MX=-1*1e16; if(d==1) { for(int i=1;i<=N;i++) if(last[i]) MX=max(MX,mat[u][i]); return dp[u][d]=MX; } for(int i=1;i<=N;i++) { i64 ret=mat[u][i]+call(i,d-1); MX=max(ret,MX); } return dp[u][d]=MX; } return dp[u][d]; } |
এ ধরণের আরেকটি প্রবলেম হলো 10681,ওটায় গ্রাফটি complete না এবং কন্ডিশনগুলো কিছুটা অন্যরকম।
ক্লাসিক travelling salesman প্রবলেম নিয়ে জানতে দেখো: http://en.wikipedia.org/wiki/Travelling_salesman_problem ,এছাড়া IIT এর Prof. G.Srinivasan এর লেকচার দেখতে ক্লিক করো এখানে।
http://uva.onlinejudge.org/external/109/10944.html এই প্রবলেমটি ক্লাসিক travelling salesman প্রবলেমের বেশ কাছাকাছি,নোড কম থাকায় বিটমাস্কিং করে সলভ করা যায়।
ফেসবুকে মন্তব্য
Powered by Facebook Comments
“for(int i=1;i<=N;i++)” এখানে লুপের ভিতরে কন্ডিশনটা কিভাবে চেক করা হচ্ছে বুঝলাম না।
লুপের মধ্যে প্রতিবার নতুন একটা শহরে যাচ্ছি , i তম শহরে যাবার কস্ট mat[u][i], এবং সেখানে যাবার পর নতুন স্টেট হবে (i,d-1) । ম্যাক্সিমামটা রিটার্ণ করবো।
আর d==1 হলে শুধু টেস্ট করতেসি ফাইনাল শহরগুলোতে পৌছানো সম্ভব নাকি এবং কত কম কস্ট এ।