ট্রাভেলিং সেলসম্যান সমস্যা

ডায়ানামিক প্রোগ্রামিং () একটি খুবই গুরুত্বপূর্ণ বিষয় এবং বলা যায় প্রোগ্রামিং প্রতিযোগিতায় সব থেকে কঠিন বিষয়। এটিকে আমি কঠিন বলছি, এর কারন হলো এতে ভালো করার একটি মাত্র উপায়ম আর তা হলো অনুশীলন করা এবং বেশি বেশি করে এই জাতীয় সমস্যা দেখা ও সমাধান করা। ডায়ানামিক প্রোগ্রামিং এ আসলে শেখানোর কিছু নেই।

ডায়ানামিক প্রোগ্রামিং এর উপর যতগুলো টপিক্স আছে, তার মধ্যে ট্রাভেলিং সেলসম্যান অনেক সহজ এবং মজার একটি অ্যালগরিদম। তোমার কাছে ট্রাভেলিং সেলসম্যান অ্যালগরিদম অনেক কমপ্লেক্স মনে হতে পারে, কিন্তু এই লাইনের পর প্রতিটি লাইন খুব মনোযোগ দিয়ে পড়লে এই অ্যালগরিদম নিয়ে আর কোন সমস্যা থাকবে না।

মনেকরো তুমি একদিন যশোর থেকে মাগুরা বেড়াতে গেছো। সেখানে তোমার n জন বন্ধুর বাড়ি আছে। তুমি একে একে তাদের সবার বাড়ি যেতে চাও। তাদের সবার বাড়ির দূরত্ব তুমি জানো। তুমি প্রথমে তোমার সবচেয়ে ভালো বন্ধু ১ এর বাসায় গেছো, তারপর একে একে সবার বাসা ঘুরে আবারও তোমার জিগার বন্ধু ১ এর বাসায় ফিরে আসবে। সব থেকে কম মোট কত দূরত্ব অতিক্রম করে তুমি সবার বাসা ঘুরতে পারবে। এটিই হলো ট্রাভেলিং সেলসম্যান সমস্যা (Travelling Salesman Problem)।

এর আগে হয়তো তোমরা DP উপায়ে একপ্টি সমস্যা সমাধানের জন্য বড় একটি সমস্যাকে ছোট সমস্যা দিয়ে সমাধান করেছো। DP ছাড়া আরেকটি উওয়ায় আছে, আর তা হলো একই রকম জিনিস খুজে বের করা। যেমন একটী আগে বলা সমস্যার ক্ষেত্রে খেয়াল করো, তুমি  ১ - ২ -৩ - ৪, এভাবে ৪ জন বন্ধুর বাসায় ঘুরেছো, আর বাকি আছে ৫…n বন্ধুরা। এই বাকি বন্ধুদের বাসা ঘুরতে তোমার যেই সবচেয়ে কম খরচ হচ্ছে ১ -৩ - ২ - ৪ ঘোরার পর বাকি বন্ধুদের বাসা ঘুরে ফেলার জন্য সবচেয়ে কম খরচের সমান। অর্থাৎ, কোন এক সময় তোমাকে শুধু জানতে হবে তুমি কোন কোন বন্ধুর বাসা ঘুরে ফেলছো এবং এখন তুমি কোথায় আছো।

বিভিবনভাবে আমরা একই দশা বা স্টেট (state) এ আসতে পারি, যেমন উপরের উদাহরণে আমরা ৪ জন বন্ধুর বাসা দুভাবে ঘুরে এখন ৪ এর বাসায় আছি। অর্থাৎ তোমার স্টেট হলো তুমি কার কার বাসায় ঘুরে ফেলছো (১,২,৩,৪) আর এখন কোথায় আছো (৪)। এখন কোথায় আছো সেটি শুধু একটি সংখ্যা, কিন্তু তুমি কোথায় কোথায় ঘুরে ফেলেছো এই জিনিস অনেকগুলো সংখ্যার সেট।

আমরা DP এর সময় স্টেটকে অ্যারের প্যারামিটার হিসেবে লিখি। এক্ষেত্রে আমরা একটি সেটকে কিভাবে সংখ্যা আকারে লিখতে পারি? আচ্ছা, এখটূ খেয়াল করে দেখো, আমাদের মোট n জন বন্ধু আছে, কার কার বাসায় গিয়েছি তাদের ১ আর কার কার বাসায় এখনো যাওয়া হয়নি তাদের ০ দিয়ে লিখতে পারি। তাহলে n টি ০-১ দিয়ে আমরা কার কার বাসায় গিয়েছি সেটি বানিয়ে ফেলতে পারি। কিন্তু তুমি যদি অ্যারের মাত্রা বা ডাইমেনশন (Dimension) n নিতে চাও তাহলে নিশ্চয়ই কোড করা খুব একটা সুখকর হবে না?

এখানে একটি মজার চালাকি আছে, আর তা হলো তুমি এই ০-১ সংখাকে বাইনারি ফর্মে ভাবতে পারো। যেমনঃ তোমার যদি ১,২,৪ নাম্বার বন্ধুর বাসা ঘোরা হয়ে থাকে তাহলে তোমার নাম্বার হবেঃ ০০০০…১০১১ = ৭.  এখন এই সংখ্যা কত বড় হতে পারে? 2n কারন একটি বন্ধু থাকতে পারে নাও পারে। যেহেতু আমাদের মোট ন জন বন্ধু তাই এই সংখ্যা 2n রকম হতে পারে। তাহলে আমাদের পুরো স্টেট কত বড়? nx2n এবং প্রতি স্টেটে গিয়ে তুমি অন্যান্য সবার বাসায় যাওয়ার চেষ্টা করবে (n ভাবে)। সুতরাং আমাদের টাইম কমপ্লেক্সিটি হবে O(n22n).

এতক্ষণ যা জানলে তা উপরে ছবিটা দেখে আরো বেশি স্পস্ট হওয়ার কথা, কিন্তু যদি ন হয় তবে ইমপ্লিমেন্টেশন দেখলে পুরোপুরি ক্লিয়ার হয়ে যাবে।

যেহেতু শুরুতেই বলেছি যে ডায়ানামিক প্রোগ্রামিং বেশ কঠিন এবং বেশি বেশি অনুশীলন না করলে ভালো করা যায় না, বলা যায় বোঝাও যায় না।

//Assuming that there are 20 friends
int dp[1<<20][20];
//mask=frinds I already visited
//at=last visited friend
int Dp(int mask, int at)
{
  //I used reference. It helps me not
  //writing dp[mask] [at] again and again.
  int& ret = dp[mask] [at];
  //Assume that we initilized dp with -1
  if (ret !=-1) return ret;

  //initialize ret with infinity
  ret = 1000000000;
  //n = number of friend
  //dist contains distance between every two nodes
  for (int i = 0; i<n; i++)
    inf (!(mask & (1<<i)))
    //mask | (1<<i) turns on i th bit in mask.
    ret = MIN(re,
      DP(mask | (1<<i), i) + dist[at][i]);
  return ret;
}

আমার বিশ্বাস ট্রাভেলিং সেলসম্যান সমস্যা এখন আর আগের মত কঠিন লাগবে না। সবার জন্য শুভ কামনা।।